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

Indice

  1. 1. Pagina principale
  2. 2. Piccoli numeri di Schröder

I piccoli numeri di di Schröder sn sono la metà dei numeri di Schröder per n > 0, mentre s0 = S0 = 1.

I piccoli numeri di Schröder sono detti anche “super numeri di Catalan”.

 

Il numero di cammini dal vertice in basso a sinistra a quello in alto a destra di una griglia n × n, utilizzando solo passi di tipo (0, 1), (1, 0) e (1, 1), ovvero a destra, verso l’alto e in diagonale vesto l’alto e a destra, senza mai salire al di sopra della diagonale che congiunge partenza e arrivo e senza passi lungo la diagonale stessa è sn.

Per esempio, esistono s2 = 3 cammini del genere in una griglia 2 × 2, come mostra la figura.

 

I 3 cammini in una griglia 2 × 2

 

 

Il numero di cammini diversi 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 e colorando con due colori diversi i passi in salita e con 3 quelli in orizzontale è sn + 1 (v. numeri di Motzkin).

La figura mostra gli 11 cammini su una griglia 2×2.

 

Gli 11 cammini in una griglia 2 × 2

 

 

Il numero di modi per inserire coppie di parentesi in una stringa di n + 1 simboli, in modo che ogni parentesi contenga almeno 2 simboli è sn. Per esempio, con n = 3 abbiamo s3 = 11 modi: abcd, (ab)cd, a(bc)cd, ab(cd), (abc)d, a(bcd), (ab)(cd), (a(bc))d, ((ab)c)d, a((bc)d), a(b(cd)).

In questa forma, se interpretiamo ogni simbolo come un’affermazione, abbiamo il numero di modi di combinare n affermazioni tra loro tramite i connettivi logici “e” e “o”: già Ipparco calcolò che con 10 affermazioni le combinazioni sono 103049 (v. numeri di Plutarco), ma non sappiamo esattamente come ci sia arrivato.

 

Il numero di alberi con n foglie e senza nodi con un solo figlio è sn – 1.La figura mostra gli alberi del genere sino a 4 foglie.

 

Gli alberi fino a 4 foglie

 

 

Il numero di modi di tracciare diagonali non intersecantesi in un poligono convesso di n lati è sn – 2. Per esempio, la figura seguente mostra gli 11 modi di tracciare diagonali in un pentagono.

 

Gli 11 modi di tracciare diagonali in un pentagono

 

 

I piccoli numeri di Schröder possono essere ottenuti con la ricorrenza s0 = 1, s1 = 1, Ricorrenza per il calcolo dei piccoli numeri di Schröder.

 

sn = sn(1), dove sn(x) è l’n-esimo piccolo polinomio di Schröder.

Bibliografia

  • Odifreddi, Piergiorgio;  "Hip, hip, Ipparco" in Le Scienze, Milano, n. 433, settembre 2004, pag. 104.

Contattami

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