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

Narayana (numeri di) (II)

Matematica combinatoria 

Sono chiamati “numeri di Narayana”, dal nome del matematico indiano T.V. Narayana (1930 – 1987), i numeri naturali definiti come Formula per la definizione dei numeri di Narayana.

 

Dalla definizione segue che N(n, 1) = n(n, n) = 1 e N(n, k) = N(n, n + 1 – k).

 

Il numero di cammini lungo diagonali da un vertice a quello adiacente di una griglia di lato 2n, che non scendono al di sotto dell’asse x (detti cammini di Dyck) e con k picchi è N(n, k). La figura illustra il caso N(4, 3) = 6.

 

Cammini in una griglia di lunghezza 8 con 3 picchi

 

 

Il numero di modi di disporre n coppie di parentesi, in modo che vi siano esattamente k coppie all’interno di altre e che a loro volta non contengano parentesi, è N(n, k). Per esempio, N(4, 2) = 6 e vi sono 6 modi di disporre le parentesi: ()((())), (())(()), (()(())), ((()())), ((())()) e ((()))().

 

N(n, k) è il numero di partizioni non incrociate di un insieme di n elementi in k sottoinsiemi.

Per esempio, vi sono 14 partizioni non incrociate di un insieme di 4 elementi { A, B, C, D }, corrispondenti ai numeri di Narayana da N(4, 1) a N(4, 4).

N(4, 1) = 1 partizioni in un sottoinsieme: { A, B, C, D };

N(4, 2) = 6 partizioni in due sottoinsiemi:

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

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

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

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

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

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

N(4, 3) = 6 partizioni in tre sottoinsiemi:

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

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

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

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

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

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

N(4, 4) = 1 partizioni in 4 sottoinsiemi: { A }, { B } { C }, { D }.

E’ esclusa la partizione { A, C } { B, D }, perché contiene un “incrocio”.

 

Sono legati ai numeri di Catalan dalla relazione Formula che lega i numeri di Narayana ai numeri di Catalan, dove Cn è un numero di Catalan.

 

Formula che coinvolge i numeri di Narayana e in particolare N(n, k + 1)N(n + 1, k)N(n + 2, k + 2) = N(n, k)N(n + 1, k + 2)N(n + 2, k + 1) (Nelson Y. Li e Toufik Mansour).

 

Nel 2013 Sara Checcoli e Michele d’Adderio dimostrarono che esistono infiniti valori di n tali che N(n, k) sia un quadrato; in particolare:

  • per qualsiasi valore di n N(n2(n2 + 1), n2 + 1) è un quadrato;

  • se n è pari, Numero di Narayana che è un quadrato è un quadrato;

  • se n è dispari, Numero di Narayana che è un quadrato è un quadrato.

 

E’ opinione comune che a parte 1 nessun numero di Narayana sia un cubo o una potenza superiore, ma non è stato dimostrato. Nel 2013 Sara Checcoli e Michele d’Adderio dimostrarono che N(n, k) non può essere un cubo o una potenza superiore se vale una delle seguenti condizioni:

  • k = 2;

  • n è il quadrato di un primo;

  • Condizione sufficiente perché un numero di Narayana non sia una potenza superiore alla seconda, dove p è il massimo primo minore di n;

  • Condizione sufficiente perché un numero di Narayana non sia una potenza superiore alla seconda;

Inoltre se la congettura di Pillai è vera, esiste al massimo un numero finito di valori N(n, 3) che sia un cubo o una potenza superiore.

 

Miklós Bóna e Bruce E. Sagan dimostrarono nel 2013 che, per p primo, chiamando rispettivamente nm e km le cifre delle rappresentazioni di n e k in base p, p non divide N(n, k) se:

  • quando p divide n, kmnm per tutti i valori di m e kj < nj, dove j è il minimo indice per il quale kj < p – 1;

  • quando p non divide n, kmnm per m > j, kj < nj e km è 0, se p divide k, p – 1 altrimenti, per m > j, dove j è il numero di riporti che si hanno nell’eseguire l’addizione tra k e nk in base p.

Come conseguenza, se p è primo:

  • se n = pm – 1, p non divide N(n, k); in particolare, se n = 2m – 1, N(n, k) è dispari.; se n = pm, p divide N(n, k) per 1 < k < n; in particolare, se n = 2m, N(n, k) è pari per 1 < k < n.

 

Le tabelle seguenti mostrano i valori di N(n, k) per n e k da 1 a 20..

n \ k

1

2

3

4

5

6

7

1

1

 

 

 

 

 

 

2

1

1

 

 

 

 

 

3

1

3

1

 

 

 

 

4

1

6

6

1

 

 

 

5

1

10

20

10

1

 

 

6

1

15

50

50

15

1

 

7

1

21

105

175

105

21

1

8

1

28

196

490

490

196

28

9

1

36

336

1176

1764

1176

336

10

1

45

540

2520

5292

5292

2520

11

1

55

825

4950

13860

19404

13860

12

1

66

1210

9075

32670

60984

60984

13

1

78

1716

15730

70785

169884

226512

14

1

91

2366

26026

143143

429429

736164

15

1

105

3185

41405

273273

1002001

2147145

16

1

120

4200

63700

496860

2186184

5725720

17

1

136

5440

95200

866320

4504864

14158144

18

1

153

6936

138720

1456560

8836464

32821152

19

1

171

8721

197676

2372112

16604784

71954064

20

1

190

10830

276165

3755844

30046752

150233760

 

n \ k

8

9

10

11

12

13

14

8

1

 

 

 

 

 

 

9

36

1

 

 

 

 

 

10

540

45

1

 

 

 

 

11

4950

825

55

1

 

 

 

12

32670

9075

1210

66

1

 

 

13

169884

70785

15730

1716

78

1

 

14

736164

429429

143143

26026

2366

91

1

15

2760615

2147145

1002001

273273

41405

3185

105

16

9202050

9202050

5725720

2186184

496860

63700

4200

17

27810640

34763300

27810640

14158144

4504864

866320

95200

18

77364144

118195220

118195220

77364144

32821152

8836464

1456560

19

200443464

367479684

449141836

367479684

200443464

71954064

16604784

20

488259720

1057896060

1551580888

1551580888

1057896060

488259720

150233760

 

n \ k

15

16

17

18

19

20

15

1

 

 

 

 

 

16

120

1

 

 

 

 

17

5440

136

1

 

 

 

18

138720

6936

153

1

 

 

19

2372112

197676

8721

171

1

 

20

30046752

3755844

276165

10830

190

1

 

Contattami

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