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

Delannoy (numeri di)

Matematica combinatoria 

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

 

La figura mostra i 25 cammini su una griglia 2 × 3.

 

I 25 cammini su una griglia 2 × 3

 

 

I numeri di Delannoy possono essere calcolati con la ricorrenza D(n, m) = D(n – 1, m) + D(n, m – 1) + D(n – 1, m – 1), dove D(0, 0) = 1 o con le formule:

Formula per i numeri di Delannoy, per m > n;

Formula per i numeri di Delannoy, per m > n;

Formula per i numeri di Delannoy, dove n-esimo numero ipertetraedrico a k dimensioni è l’n-esimo numero ipertetraedrico a k dimensioni.

 

La seconda formula permette di dimostrare che tutti i numeri di Delannoy sono dispari, perché nella somma solo l’addendo corrispondente a k = 0 è dispari.

 

Dalla simmetria dei cammini si ricava che D(n, m) = D(m, n).

 

Formula che coinvolge i numeri di Delannoy, dove Pn è l’n-esimo numero di Pell.

 

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

 

Le tabelle seguenti riportano i primi valori.

n \ m

0

1

2

3

4

5

6

7

8

0

1

1

1

1

1

1

1

1

1

1

1

3

5

7

9

11

13

15

17

2

1

5

13

25

41

61

85

113

145

3

1

7

25

63

129

231

377

575

833

4

1

9

41

129

321

681

1289

2241

3649

5

1

11

61

231

681

1683

3653

7183

13073

6

1

13

85

377

1289

3653

8989

19825

40081

7

1

15

113

575

2241

7183

19825

48639

108545

8

1

17

145

833

3649

13073

40081

108545

265729

9

1

19

181

1159

5641

22363

75517

224143

598417

10

1

21

221

1561

8361

36365

134245

433905

1256465

11

1

23

265

2047

11969

56695

227305

795455

2485825

12

1

25

313

2625

16641

85305

369305

1392065

4673345

13

1

27

365

3303

22569

124515

579125

2340495

8405905

14

1

29

421

4089

29961

177045

880685

3800305

14546705

15

1

31

481

4991

39041

246047

1303777

5984767

24331777

16

1

33

545

6017

50049

335137

1884961

9173505

39490049

17

1

35

613

7175

63241

448427

2668525

13726991

62390545

18

1

37

685

8473

78889

590557

3707509

20103025

96220561

19

1

39

761

9919

97281

766727

5064793

28875327

145198913

20

1

41

841

11521

118721

982729

6814249

40754369

214828609

 

n \ m

9

10

11

12

13

14

15

0

1

1

1

1

1

1

1

1

19

21

23

25

27

29

31

2

181

221

265

313

365

421

481

3

1159

1561

2047

2625

3303

4089

4991

4

5641

8361

11969

16641

22569

29961

39041

5

22363

36365

56695

85305

124515

177045

246047

6

75517

134245

227305

369305

579125

880685

1303777

7

224143

433905

795455

1392065

2340495

3800305

5984767

8

598417

1256465

2485825

4673345

8405905

14546705

24331777

9

1462563

3317445

7059735

14218905

27298155

50250765

89129247

10

3317445

8097453

18474633

39753273

81270333

158819253

298199265

11

7059735

18474633

45046719

103274625

224298231

464387817

921406335

12

14218905

39753273

103274625

251595969

579168825

1267854873

2653649025

13

27298155

81270333

224298231

579168825

1409933619

3256957317

7178461215

14

50250765

158819253

464387817

1267854873

3256957317

7923848253

18359266785

15

89129247

298199265

921406335

2653649025

7178461215

18359266785

44642381823

16

152951073

540279585

1759885185

5334940545

15167050785

40704778785

103706427393

17

254831667

948062325

3248227095

10343052825

30845044155

86716873725

231128079903

18

413442773

1616336765

5812626185

19403906105

60592003085

178153920965

495998874593

19

654862247

2684641785

10113604735

35330137025

115326046215

354071970265

1028224765823

20

1014889769

4354393801

17152640321

62596382081

213252565321

682650581801

2064947317889

 

n \ m

16

17

18

19

20

0

1

1

1

1

1

1

33

35

37

39

41

2

545

613

685

761

841

3

6017

7175

8473

9919

11521

4

50049

63241

78889

97281

118721

5

335137

448427

590557

766727

982729

6

1884961

2668525

3707509

5064793

6814249

7

9173505

13726991

20103025

28875327

40754369

8

39490049

62390545

96220561

145198913

214828609

9

152951073

254831667

413442773

654862247

1014889769

10

540279585

948062325

1616336765

2684641785

4354393801

11

1759885185

3248227095

5812626185

10113604735

17152640321

12

5334940545

10343052825

19403906105

35330137025

62596382081

13

15167050785

30845044155

60592003085

115326046215

213252565321

14

40704778785

86716873725

178153920965

354071970265

682650581801

15

103706427393

231128079903

495998874593

1028224765823

2064947317889

16

252055236609

586889743905

1314016698401

2838240338817

5931412422529

17

586889743905

1425834724419

3326741166725

7478998203943

16248650965289

18

1314016698401

3326741166725

8079317057869

18885056428537

42612705597769

19

2838240338817

7478998203943

18885056428537

45849429914943

107347191941249

20

5931412422529

16248650965289

42612705597769

107347191941249

260543813797441

 

Contattami

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