Numero di Schröder

In matematica, data una griglia quadrata di dimensione $n\times n$ nel 1° quadrante di un sistema di riferimento cartesiano, il numero di Schröder, $S_{n}$, descrive il numero di cammini possibili per arrivare dal punto di coordinate (0, 0) al punto di coordinate (n, n), ammettendo di potersi muovere soltanto in verticale e in orizzontale o in diagonale verso destra e senza che il cammino oltrepassi mai la diagonale data dalla retta di equazione $y=x$.

La successione di tali numeri interi, che prendono il nome dal matematico tedesco Ernst Schröder, per $n=0,1,\dots$, ha come primi elementi:

1, 2, 6, 22, 90, 394, 1 806, 8 558, ...

Esempi

La figura seguente mostra i 6 cammini che, rispettando le sopraccitate condizioni, è possibile fare per raggiungere il punto di coordinate (2,2) partendo dal punto di coordinate (0,0).

Costruzioni correlate

Un cammino di Schröder di lunghezza $n$ è un cammino reticolare dal punto $(0,0)$ al punto $(2n,0)$ con passi orientati verso nord-est, $(1,1);$ est, $(2,0);$ e sud-est, $(1,-1),$ che non va al di sotto dell'asse delle ascisse. Il numero di Schröder ennesimo è il di numero di cammini di Schröder di lunghezza $n$. La figura seguente mostra i 6 cammini di Schröder di lunghezza pari a 2.

Similmente, i numeri di Schröder rappresentano il numero di modi in cui si può dividere un rettangolo in $n+1$ rettangoli più piccoli usando $n$ segmenti passanti per $n$ punti disposti in maniera casuale nel rettangolo, con ogni segmento che interseca uno solo dei suddetti punti e divide solo un singolo rettangolo in due più piccoli, in un processo simile a quello della triangolazione, in cui una forma è divisa in triangoli non sovrapposti invece in rettangoli. La figura seguente mostra le 6 possibili divisioni di un rettangolo in 3 rettangoli più piccoli usando 2 segmenti:

Nella sottostante figura sono invece mostrate le 22 divisioni di un rettangolo in 4 rettangoli più piccoli usando 3 segmenti:

Il numero di Schröder $S_{n}$ rappresenta anche le permutazioni separabili di lunghezza $n-1$.

Successioni correlate

I numeri Schröder sono talvolta chiamati "grandi numeri Schröder" poiché esiste un'altra successione di Schröder, ossia quella dei "piccoli numeri di Schröder", chiamati anche "numeri di Schröder-Ipparco". Le connessioni tra i cammini rappresentati da questi due numeri possono essere viste in diversi modi:

• Considerando i cammini dal punto $(0,0)$ al punto $(n,n)$ con passi $(1,1),$ $(2,0),$ e $(1,-1)$ che non salgono al di sopra della diagonale principale, si può vedere che ci sono due tipi di cammini: quelli che, anche solo in alcuni tratti, si estendono lungo la suddetta diagonale e quelli che non lo fanno mai. I grandi numeri di Schröder includono entrambi i tipi di cammino, mentre i piccoli numeri di Schröder tengono conto solo dei cammini che al massimo toccano la diagonale ma non hanno alcun tratto che si estende lungo di essa.
• Se $S_{n}$ è l'$n$-simo grande numero di Schröder e $s_{n}$ è l'$n$-simo piccolo numero di Schröder, allora $S_{n}=2s_{n}$ per $n>0$ $(S_{0}=s_{0}=1).$

I cammini di Schröder sono simili ai cammini di Dick ma permettono anche il passo diagonale invece che solamente orizzontale e verticale. Un altro cammino simile è quello rappresentato dai numeri di Motzkin; i cammini di Motzkin permettono anch'essi i passi diagonali ma ammettono solo un singolo passo orizzontale (1,0), e rappresentano i cammini da $(0,0)$ a $(n,0)$.

Esiste anche una disposizione triangolare associata con i numeri di Schröder che fornisce una relazione di ricorrenza (sebbene non solo con i numeri di Schröder). I primi termini sono:

1, 1, 2, 1, 4, 6, 1, 6, 16, 22, ...

Risulta più facile vedere la connessione tra i numeri di Schröder quando la sequenza viene disposta in modo triangolare:

k n	0	1	2	3	4	5	6
0	1
1	1	2
2	1	4	6
3	1	6	16	22
4	1	8	30	68	90
5	1	10	48	146	304	394
6	1	12	70	264	714	1 412	1 806

I numeri di Schröder sono quindi quelli disposti sulla diagonale, ossia $S_{n}=T(n,n)$ dove $T(n,k)$ è il numero alla riga $n$ e alla colonna $k$. La relazione di ricorrenza data da questa disposizione è:

$T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)$

con $T(1,k)=1$ e $T(n,k)=0$ per $k>n$. Un'altra osservazione da fare è che la somma dei numeri sull'$n$-sima riga è il $(n+1)$-esimo piccolo numero di Schröder (o numero di Schröder-Ipparco), ossia:

$\sum _{k=0}^{n}T(n,k)=s_{n+1}$.

Relazione di ricorrenza

$S_{n}=3S_{n-1}+\sum _{k=1}^{n-2}S_{k}S_{n-k-1}$ per $n\geq 2$ con $S_{0}=1$, $S_{1}=2$.

Funzione generatrice

La funzione generatrice $G(x)$ di $(S_{n})$ è

$G(x)={\frac {1-x-{\sqrt {x^{2}-6x+1}}}{2x}}=\sum _{n=0}^{\infty }S_{n}x^{n}$.

Utilizzi

Uno degli argomenti trattati dalla combinatoria è la tassellatura delle forme, e un esempio particolare di questa è la tassellatura con tasselli a domino, che cerca di trovare quanti domino (cioè rettangoli di dimensioni $1\times 2$ o $2\times 1$) si possono disporre su una qualunque superficie facendo in modo che la superficie sia completamente coperta e che i domino non si sovrappongano e non escano fuori dal perimetro della superficie.

La tassellatura con tasselli a domino di un diamante Azteco di ordine 4.

Quello che risulta è che esiste una connessione tra i numeri di Schröder e la tassellatura con tasselli a domino della superficie nota come diamante Azteco. Il determinante di una matrice di Hankel di dimensione $(2n-1)\times (2n-1)$ dei numeri di Schröder, ossia la matrice quadrata in cui il $(i,j)$-esimo elemento è $S_{i+j-1},$ è il numero di modi in cui si può tassellare un diamante Azteco di ordine $n$ utilizzando tasselli a forma di domino, vale a dire $2^{n(n+1)/2}$. Quindi, data la generica matrice,

${\begin{vmatrix}S_{1}&S_{2}&\cdots &S_{n}\\S_{2}&S_{3}&\cdots &S_{n+1}\\\vdots &\vdots &\ddots &\vdots \\S_{n}&S_{n+1}&\cdots &S_{2n-1}\end{vmatrix}}=2^{n(n+1)/2}.$

Si ha ad esempio:

• ${\begin{vmatrix}2\end{vmatrix}}=2=2^{1(2)/2}$

• ${\begin{vmatrix}2&6\\6&22\end{vmatrix}}=8=2^{2(3)/2}$

• ${\begin{vmatrix}2&6&22\\6&22&90\\22&90&394\end{vmatrix}}=64=2^{3(4)/2}$

Voci correlate

• Numero di Delannoy
• Numero di Narayana

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Numero di Schröder

Collegamenti esterni

• (EN) Eric W. Weisstein, Numero di Schröder, su MathWorld, Wolfram Research.