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

Riordan (numeri di)

Matematica combinatoria  Sequenze 

Si chiamano “numeri di Riordan”, in onore di J. Riordan che per primo li studiò nel 1975, i numeri 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, ma senza passi orizzontali al linello base e senza scendere sotto il livello base.

La definizione è simile a quella dei numeri di Motzkin e a quelli di Catalan; la differenza rispetto ai primi è che non vanno considerati i cammini che comprendono passi orizzontali al livello base, rispetto ai secondi è che vanno considerati anche i cammini con tratti orizzontali.

 

La figura seguente mostra i 6 cammini di questo genere su una griglia 5 × 5.

 

Cammini in una griglia 5 × 5

 

 

I numeri di Riordan sono comunemente indicati con γn.

 

Il numero di cammini dal vertice in basso a sinistra a quello in alto a destra in una griglia 4n × 4n, utilizzando solo passi verso destra in diagonale, salendo o scendendo, ma senza passi orizzontali, con tutti i passi in salita di lunghezza 2, nessun passo in discesa di lunghezza 2 e senza scendere sotto il livello base è γn.

La figura seguente mostra i 3 cammini di questo genere su una griglia 16 × 16.

 

Cammini in una griglia 16 × 16

 

 

Il numero di alberi ordinati con n nodi (radice inclusa), nei quali ogni nodo intermedio ha almeno 2 figli è il numero di Riordan γn – 1 (v. numeri di alberi).

La figura seguente mostra gli alberi di questo tipo fino a 6 nodi.

 

Gli alberi ordinati fino a 6 nodi, nei quali nessun nodo ha un solo figlio

 

 

Una partizione di Catalan di ordine n è una suddivisione dei numeri naturali da 1 a n in sottoinsiemi disgiunti con le seguenti proprietà:

  • ogni sottoinsieme contiene almeno 2 numeri;

  • se si numerano n punti su una circonferenza da 1 a n in senso orario e si uniscono i punti corrispondenti ai numeri di un sottoinsieme ciascuno con quello di numero immediatamente superiore e il massimo col minimo a formare un poligono (che si riduce a un segmento per i sottoinsiemi di due soli numeri), i poligoni corrispondenti ai vari sottoinsiemi non si intersecano.

La figura seguente mostra i poligoni corrispondenti alla partizione di Catalan { { 1, 2, 5 }, { 3, 4 }, { 6, 10 }, { 7, 8, 9 } } di ordine 10.

 

Raffigurazione di una partizione di Catalan di ordine 10

 

 

Il numero di Riordan γn è il numero di partizioni di Catalan di ordine n.

Per esempio, le 6 partizioni di Catalan di ordine 5 sono: { { 1, 2, 3, 4, 5 } }, { { 1, 2, 5 }, { 3, 4 } }, { { 1, 4, 5 }, { 2, 3 } }, { { 1, 2, 3 }, { 4, 5 } }, { { 1, 2 }, { 3, 4, 5 } } e { { 1, 5 }, { 2, 3, 4 } }; la figura seguente mostra i poligoni corrispondenti.

 

Raffigurazione delle partizioni di Catalan di ordine 5

 

 

Il numero di Riordan γn è il numero modi per tracciare archi che non si intersechino tra n punti su una circonferenza, in modo che ogni punto sia connesso al massimo a un arco e che non vi siano archi tra due punti consecutivi.

La figura seguente mostra i 6 modi di tracciare archi tra 5 punti.

 

Raffigurazione dei modi di tracciare archi tra 5 punti

 

 

Una permutazione di Riordan di ordine n è una permutazione dei numeri naturali da 1 a n tale che:

  • non esistano tre elementi an, am, ak tali che an, > am > ak e k > m > n;

  • ogni nuovo massimo (cioè un numero maggiore di tutti i precedenti) sia seguito da un numero inferiore.

La seconda condizione in particolare implica che il primo elemento, essendo un nuovo massimo, sia seguito da un numero minore.

Il numero di Riordan γn è il numero di permutazioni di Riordan di ordine n.

Per esempio, le permutazioni di Riordan dei numeri da 1 a 5 sono: { 2, 1, 5, 3, 4 }, { 3, 1, 2, 5, 4 }, { 3, 1, 5, 2, 4 }, { 4, 1, 2, 5, 3 }, { 4, 1, 5, 2, 3 }, { 5, 1, 2, 3, 4 }. La permutazione { 5, 1, 3, 2, 4 } viola la prima condizione, per i numeri 5, 3 e 2, la permutazione { 2, 1, 4, 5, 3 } la seconda, perché il massimo 4 è seguito da un numero maggiore, la permutazione { 4, 3, 2, 1, 5 } la seconda, perché il massimo 5 non è seguito da nulla.

 

I numeri di Riordan si possono calcolare tramite la ricorrenza γ0 = 1, γ1 = 0, Ricorrenza per il calcolo dei numeri di Riordan.

 

Alcune formule per il calcolo dei numeri di Riordan:

Formula per il calcolo dei numeri di Riordan, dove Coefficiente trinomiale centrale T(n, k) è un coefficiente trinomiale centrale.

Formula per il calcolo dei numeri di Riordan (Frank R. Bernhart, 1999);

Formula per il calcolo dei numeri di Riordan (Frank R. Bernhart, 1999);

Formula per il calcolo dei numeri di Riordan (Paul Barry, 2005);

Formula per il calcolo dei numeri di Riordan;

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

Formula per il calcolo dei numeri di Riordan (Andrew V. Sutherland, 2007).

 

Asintoticamente γn tende a Limite asintotico cui tende γ(n) (Vaclav Kotesovec, 2012).

 

Sia S l’insieme degli interi positivi tali che la massima potenza di 2 che li divide 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.); γn è pari se e solo se n = 2m – 1, con m appartenente a S (Emeric Deutsch e Bruce E. Sagan, 2004). Per esempio, 3 appartiene al’insieme S e γ5 è pari.

 

Emeric Deutsch e Bruce E. Sagan dimostrarono nel 2004 che γn ≡ 1 mod 3, se n = 3k – 1 e k si rappresenta in base 3 senza cifre 2; γn ≡ 0 mod 3 altrimenti.

 

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

 

Ogni numero di Riordan γn è multiplo di n – 1, per n pari, o di (n – 1) / 2, per n dispari, quindi l’unico numero di Riordan primo è γ4 = 3.

 

La tabella seguente mostra i numeri di Riordan fino a γ1000.

n

γn

0

1

1

0

2

1

3

1

4

3

5

6

6

15

7

36

8

91

9

232

10

603

11

1585

12

4213

13

11298

14

30537

15

83097

16

227475

17

625992

18

1730787

19

4805595

20

13393689

 

Contattami

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