Don't take life too seriously: it's just a temporary situation

Motzkin (numeri di)

Matematica combinatoria  Sequenze 

Si chiama “numero di Motzkin”, in onore di Theodore Samuel Motzkin (Berlino, 26/3/1908 – 15/10/1970) il numero Mn di cammini dal vertice in basso a sinistra a quello in basso a destra in una griglia n × n, utilizzando solo passi verso destra, anche in diagonale, salendo o scendendo.

La figura mostra i 9 cammini su una griglia 4 × 4.

 

Cammini in una griglia 4 × 4

 

 

I numeri di Motzkin sono strettamente legati ai numeri di Catalan; per esempio, se non si ammettono tratti orizzontali, il numero di cammini è il numero di Catalan Numero di Catalan C(n / 2).

Se invece si permette ai cammini di estendersi anche al di sotto della linea di partenza, il numero è dato dal coefficiente trinomiale centrale Coefficiente trinomiale centrale T(n, 0).

 

Un problema equivalente è contare il numero di ordini diversi in cui possono essere scrutinati n voti in un ballottaggio tra due candidati A e B, in modo tale finiscano alla pari, ma in nessun momento dello scrutinio B sia in testa, ammettendo che vi siano schede bianche.

 

Il numero di Motzkin Mn è anche il numero di modi di tracciare corde che non si intersecano tra n punti disposti su una circonferenza. La figura seguente illustra il caso n = 4.

 

Modi di tracciare corde che non si intersecano tra 4 punti

 

Se tutti i punti devono essere connessi da una corda il numero di modi è Numero di Catalan C(n / 2).

 

Il numero di alberi con n nodi (radice esclusa) nei quali nessun nodo, a parte eventualmente la radice, ha grado 2 (ossia ha un solo nodo figlio) è Mn – 1. La figura seguente mostra i 9 alberi del genere con 5 nodi.

 

Alberi con 5 nodi

 

 

Il numero di alberi con n foglie, nei quali ogni nodo, interno ha almeno 2 figli, dei quali quello più a sinistra e quello più a destra sono foglie è Mn – 2. La figura seguente mostra i 4 alberi del genere con 5 foglie.

 

Alberi con 5 foglie

 

 

Il numero di partizioni non incrociate di un insieme di n elementi, nelle quali elementi consecutivi appartengono a sottoinsiemi diversi è Mn – 1.

Per esempio, vi sono M4 = 9 partizioni del genere di un insieme di 5 elementi { A, B, C, D, E }:

  • { A }, { B }, { C }, { D }, { E };

  • { A }, { B }, { C, E }, { D };

  • { A }, { B, D }, { C }, { E };

  • { A }, { B, E }, { C }, { D };

  • { A, C }, { B }, { D }, { E };

  • { A, D }, { B, } { C }, { E };

  • { A, E }, { B }, { C }, { D };

  • { A, E }, { B, D }, { C };

  • { A, B, E }, { C }, { D }.

 

Una matrice di Hankel è una matrice che ha tutti gli elementi su ogni diagonale perpendicolare alla diagonale principale uguali tra loro; se si prende Mm + n – 2 come elemento di indici m e n, si ottiene una matrice che ha determinante 1, indipendentemente dalla dimensione (Aigner, 1998). Per esempio, Determinante di una matrice di Hankel contenente numeri di Motkin.

Se come elemento di indici m e n di una matrice di ordine k si prende Mm + n – 1, il determinante è (Aigner, 1998):

  • –1, se k ≡ 3 o 4 mod 6;

  • 0, se k ≡ 2 o 5 mod 6;

  • 1, se k ≡ 0 o 1 mod 6.

Per esempio, Determinante di una matrice di Hankel contenente numeri di Motkin.

 

Alcune formule per il calcolo dei numeri di Motzkin:

Mn = γn + γn + 1, dove γn è un numero di Riordan;

Formula per il calcolo dei numeri di Motzkin, con M0 = M1 = 1;

Formula per il calcolo dei numeri di Motzkin, con M0 = 1;

Formula per il calcolo dei numeri di Motzkin, dove Coefficiente trinomiale centrale T(n, 0) è un coefficiente trinomiale centrale (E. Barcucci, R. Pinzani e R. Sprugnoli, 1991);

Formula per il calcolo dei numeri di Motzkin, dove Cn è un numero di Catalan;

Formula per il calcolo dei numeri di Motzkin, dove Cn è un numero di Catalan;

Formula per il calcolo dei numeri di Motzkin;

Formula per il calcolo dei numeri di Motzkin;

Formula per il calcolo dei numeri di Motzkin;

Formula per il calcolo dei numeri di Motzkin (Dan Romik);

Formula per il calcolo dei numeri di Motzkin, dove Pn(x) è l’n-esimo polinomio di Legendre.

 

Gli unici numeri di Motzkin primi noti sono M2 = 2, M7 = 127, M12 = 15511 è M36 = 953467954114363; se ve ne sono altri, l’indice è maggiore di 263000 (Eric Weisstein 2008).

 

Nessun numero di Motzkin è multiplo di 8, 25 o 169.

 

Sia S l’insieme degli interi positivi tali che la massima potenza di 2 per la quale sono divisibili abbia esponente pari (quindi l’insieme contiene gli interi dispari, quelli divisibili per 4, ma non per 8, quelli divisibili per 16, ma non per 32 ecc.); Mn è pari se e solo se n = 4m – 1 o n = 4m – 2, con m appartenente a S (Emeric Deutsch e Bruce E. Sagan, 2004). Per esempio, 3 appartiene al’insieme S e M10 e M11 sono pari.

 

Emeric Deutsch e Bruce E. Sagan dimostrarono nel 2004 che:

  • Mn ≡ –1 mod 3, se n = 3k – 1 e k si rappresenta in base 3 senza cifre 2;

  • Mn ≡ 1 mod 3, se n = 3k o n = 3k – 2 e k si rappresenta in base 3 senza cifre 2;

  • Mn ≡ 0 mod 3 altrimenti.

Gli stessi matematici dimostrarono anche Mn è multiplo di 5 se e solo se n è della forma 52m(5k + 1) – 2, 52m – 1(5k + 2) – 1, 52m – 1(5k + 3) – 2 o 52m(5k + 4) – 1.

 

Se p è un primo dispari, Mn – 1 è multiplo di p.

 

Tewodros Amdeberhan avanzò la congettura che Mn sia multiplo di 4 se e solo se n è della forma (4m + 1)4k + 1 o (4m + 3)4k + 1 – 2, tuttora in attesa di dimostrazione.

 

I numeri di Motzkin soddisfano la disuguaglianza Disuguaglianza soddisfatta dai numeri di Motzkin (M. Aigner, 1998).

 

La funzione generatrice dei numeri di Motzkin è Funzione generatrice dei numeri di Motzkin.

 

La tabella seguente mostra i numeri di Motzkin sino a M20.

n

Mn

0

1

1

1

2

2

3

4

4

9

5

21

6

51

7

127

8

323

9

835

10

2188

11

5798

12

15511

13

41835

14

113634

15

310572

16

853467

17

2356779

18

6536382

19

18199284

20

50852019

 

Nel 2012 Zhi-Wei Sun propose le congetture che Formula che coinvolge i numeri di Motzkin sia strettamente crescente e che Formula che coinvolge i numeri di Motzkin sia strettamente decrescente.

Nel 2013 Florian Luca e Pantelimon Stănică dimostrarono che le congetture sono vere per n abbastanza grande.

Yi Wang e Bao-Xuan Zhu dimostrarono nel 2013 la prima congettura per tutti i valori di n.

 

Se nel problema del disegno delle corde non si contano le configurazioni che differiscono solo per rotazioni, il numero di modi è dato dai numeri chiamati “numeri di Motzkin ciclici” Numero di Motzkin ciclico MC(n). In questo caso non si conosce una formula generale, ma solo una formula valida per n primo dispari: Formula per il calcolo dei numeri di Motzkin ciclici.

 

La tabella seguente mostra i primi numeri di Motzkin ciclici (Max Alekseyev, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Numero di Motzkin ciclico MC(n)

0

1

1

1

2

2

3

2

4

4

5

5

6

12

7

19

8

46

9

95

10

230

11

528

12

1320

13

3219

14

8172

15

20714

16

53478

17

138635

18

363486

19

957858

20

2543476

21

6788019

22

18218772

23

49120019

24

133036406

25

361736109

26

987316658

27

2703991820

28

7429445752

29

20473889133

30

56579632732

31

156766505691

 

Se nel problema del disegno delle corde non si contano le configurazioni che differiscono per rotazioni o riflessioni, il numero di modi è dato dai “numeri di Motzkin diedri” Numero di Motzkin diedro MC(n).

 

La tabella seguente mostra i primi numeri di Motzkin diedri (Max Alekseyev, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Numero di Motzkin diedro MC(n)

0

1

1

1

2

2

3

2

4

4

5

5

6

11

7

16

8

36

9

65

10

150

11

312

12

756

13

1743

14

4353

15

10732

16

27489

17

70379

18

183866

19

481952

20

1277784

21

3402661

22

9126689

23

24584870

24

66567924

25

180939737

26

493801694

27

1352203202

28

3715137460

29

10237545525

30

28291018283

31

78384998904

32

217715672036

33

606103034821

34

1691020991782

35

4727601528674

36

13242641322252

37

37162431389051

38

104469244613429

 

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.