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

Delannoy centrali (numeri di)

Matematica combinatoria 

Si chiama “numero di Delannoy centrale” il numero di Delannoy D(n, m) con n = m, ovvero il numero di cammini da un vertice a quello opposto in una griglia n × n, utilizzando anche passi in diagonale, ma senza mai tornare verso il vertice di partenza.

 

La figura mostra i 13 cammini su una griglia 2 × 2.

 

I 13 cammini su una griglia 2 × 2

 

 

Il numero di cammini che non salgono mai al di sopra della diagonale è un numero di Schröder.

 

I numeri di Delannoy centrali possono essere calcolati con la ricorrenza D(0) = 1, D(1) = 3, Formula per i numeri di Delannoy centrali, con la formula Formula per i numeri di Delannoy centrali oppure come D(n) = Ln(3), dove Ln è un polinomio di Legendre.

 

I numeri di Delannoy centrali sono tutti dispari: anche senza ricorrere alla dimostrazione generale per i numeri di Delannoy, basta considerare che per ogni cammino ve ne è uno simmetrico rispetto alla diagonale, tranne per quello lungo la diagonale.

 

Emeric Deutsch e Bruce E. Sagan dimostrarono nel 2004 che D(n) ≡ 1 mod 3, se n si rappresenta in base 3 senza cifre 1; D(n) ≡ 0 mod 3 altrimenti.

 

Nel 2013 Florian Luca e Pantelimon Stănică dimostrarono che Formula che coinvolge i numeri di Delannoy centrali è strettamente decrescente per n abbastanza grande.

 

La funzione generatrice è Funzione generatrice dei numeri di Delannoy centrali.

 

I numeri di Delannoy centrali primi noti sono pochissimi: D(1) = 3, D(2) = 13 e D(8) = 265729. Se ne esiste un altro, è maggiore di 10300.

 

Nel 2014 Zhi-Wei Sun avanzò la congettura che ogni numero di Delannoy centrale abbia un fattore primo primitivo, ossia sia divisibile per un primo che non divide nessuno dei precedenti.

 

La tabella seguente riporta i numeri di Delannoy centrali fino a D(20).

n

D(n)

0

1

1

3

2

13

3

63

4

321

5

1683

6

8989

7

48639

8

265729

9

1462563

10

8097453

11

45046719

12

251595969

13

1409933619

14

7923848253

15

44642381823

16

252055236609

17

1425834724419

18

8079317057869

19

45849429914943

20

260543813797441

 

I numeri di cammini strutturalmente differenti, ossia escludendo quelli che coincidono per rotazione o riflessione, è Formula per il numero di cammini strutturalmente differenti, dove Pn è l’n-esimo numero di Pell (M. Fiorentini, 2017).

La tabella seguente riporta i numeri di cammini strutturalmente differenti per n fino a 20.

n

Cammini strutturalmente differenti

0

1

1

2

2

6

3

21

4

94

5

449

6

2323

7

12320

8

66861

9

366562

10

2026814

11

11267001

12

62913070

13

352514213

14

1981043175

15

11160774080

16

63014277465

17

356459717762

18

2019831972438

19

11462363499261

20

65135969125822

 

Contattami

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