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 numeri di Schröder prendono il nome dal matematico tedesco Friedrick Wilhelm Karl Ernst Schröder (Mannheim, Germania, 25/11/1841 – Karlsruhe, Germania, 16/6/1902).

L’n-esimo numero di Schröder Sn è 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..

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

I 6 cammini in una griglia 2 × 2

Se si ammette di oltrepassare la diagonale, il numero di cammini è dato dal numero di Delannoy centrale Dn.

 

Dati n punti in un rettangolo, tali che non ve ne siano due allineati lungo una parallela ai lati, il numero di modi per dividere il rettangolo in n + 1 rettangoli, con n segmenti paralleli ai lati, passanti per i punti e ciascuno dei quali separi due rettangoli è Sn – 1.

Per esempio, vi sono S2 = 6 modi di dividere un rettangolo del genere in 3 parti, come mostra la figura seguente.

I 3 modi per dividere un rettangolo in 3 parti

 

Il numero di modi per suddividere un poligono convesso di n lati tramite diagonali che non si incrociano e non toccano un lato designato è Sn – 4. La figura seguente mostra le 6 suddivisioni del genere di un esagono.

I 6 modi per suddividere un esagono

 

Il numero di partizioni non incrociate di un insieme in n sottoinsiemi, nelle quali elementi consecutivi appartengono a sottoinsiemi diversi è Sn – 1.

Per esempio, vi sono S3 = 6 partizioni del genere di un insieme di caratteri alfabetici a partire da A in 3 sottoinsiemi:

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

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

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

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

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

  • { A, B, E }, { C }, { D }.

 

Prendiamo una matrice quadrata contenente solo 0 e 1 e sostituiamo ogni 0 che sia adiacente (in senso verticale od orizzontale) a due o più 1 con 1, ripetendo il processo finché possibile: il numero di matrici di ordine n che alla fine contengono solo 1 è Sn (Louis Shapiro e A.B. Stephens, 1989).

 

Una matrice di Hankel è una matrice che ha tutti gli elementi su ogni diagonale perpendicolare alla diagonale principale uguali tra loro; se in una matrice di ordine k si prende Sm + n – 2 come elemento di indici m e n, la matrice risultante ha determinante Determinante di una matrice di Hankel contenente numeri di Schröder. Per esempio, Determinante di una matrice di Hankel contenente numeri di Schröder.

Se si prende Sm + n – 1 come elemento di indici m e n, la matrice risultante ha determinante Determinante di una matrice di Hankel contenente numeri di Schröder. Per esempio, Determinante di una matrice di Hankel contenente numeri di Schröder.

Se si prende Sm + n come elemento di indici m e n, la matrice risultante ha determinante Determinante di una matrice di Hankel contenente numeri di Schröder. Per esempio, Determinante di una matrice di Hankel contenente numeri di Schröder.

 

Questi numeri sono anche detti “grandi numeri di Schröder”, per distinguerli da quelli “piccoli”, ottenuti dividendo ogni termine, tranne S0, per 2.

 

I numeri di Schröder si possono ottenere tramite la ricorrenza S0 = 1, Ricorrenza per il calcolo dei numeri di Schröder.

 

Alcune formule per il calcolo dei numeri di Schröder:

Formula per il calcolo dei numeri di Schröder, dove Dn è un numero di Delannoy centrale;

Sn = Sn(1), dove Sn(x) è l’n-esimo grande polinomio di Schröder;

Formula per il calcolo dei numeri di Schröder, dove Ln(x) è l’n-esimo polinomio di Legendre;

Formula per il calcolo dei numeri di Schröder;

Formula per il calcolo dei numeri di Schröder;

Formula per il calcolo dei numeri di Schröder;

Formula per il calcolo dei numeri di Schröder;

Formula per il calcolo dei numeri di Schröder;

Formula per il calcolo dei numeri di Schröder;

Formula per il calcolo dei numeri di Schröder, dove Cn è un numero di Catalan;

Formula per il calcolo dei numeri di Schröder, dove Cn è un numero di Catalan;

Formula per il calcolo dei numeri di Schröder;

Formula per il calcolo dei numeri di Schröder, dove N(n, k) è un numero di Narayana (II).

 

La funzione generatrice dei numeri di Schröder è Funzione generatrice dei numeri di Schröder.

 

Asintoticamente Sn tende a Limite asintotico cui tende S(n).

 

La tabella seguente mostra i numeri di Schröder fino a S20.

n

Sn

0

1

1

2

2

6

3

22

4

90

5

394

6

1806

7

8558

8

41586

9

206098

10

1037718

11

5293446

12

27297738

13

142078746

14

745387038

15

3937603038

16

20927156706

17

111818026018

18

600318853926

19

3236724317174

20

17518619320890

 

I numeri di Schröder sono tutti pari, tranne S0 = 1, quindi l’unico numero di Schröder primo è S1 = 2.

I numeri di Schröder noti uguali al prodotto di due primi sono:

  • S2 = 6 = 2 • 3,

  • S3 = 22 = 2 • 11,

  • S5 = 394 = 2 • 197,

  • S9 = 206098 = 2 • 103049,

  • S215 = 100230848462699458124592305808243311397012730058312634536528677863284457023909350493531030272029011989982416182384224900941678726412654887326862318556212270282702 = 2 · 50115424231349729062296152904121655698506365029156317268264338931642228511954675246765515136014505994991208091192112450470839363206327443663431159278106135141351.

I numeri di Schröder noti uguali al prodotto di tre primi sono:

  • S7 = 8558 = 2 • 11 • 389,

  • S11 = 5293446 = 2 • 3 • 882241,

  • S17 = 111818026018 = 2 • 41263 • 1354943,

  • S19 = 3236724317174 = 2 • 24413 • 66290999,

  • S21 = 95149655201962 = 2 • 3253 • 14624908577.

 

Nel 2012 Zhi-Wei Sun propose due congetture sui numeri di Schröder:

  • Formula che coinvolge i numeri di Schröder è strettamente crescente;

  • Formula che coinvolge i numeri di Schröder è strettamente decrescente.

 

Nel 2013 Florian Luca e Pantelimon Stănică dimostrarono che le congetture sono vere per n abbastanza grande.

Yi Wang e Bao-Xuan Zhu dimostrarono nel 2013 che la prima congettura è vera per tutti i valori di n.

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.