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, ...^[1]

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$ .^[2] 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.^[3]
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).$ ^[4]

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)$ .^[5]

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

1, 1, 2, 1, 4, 6, 1, 6, 16, 22, ...^[6]

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$ .^[6] 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

.^[7]

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}

.^[7]

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.

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}$ .^[8] 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}$

Note

^ (EN) N. J. A. Sloane, Sequenza A006318, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation. URL consultato il 3 maggio 2021.
^ Federico Ardila, Algebraic and geometric methods in enumerative combinatorics, in Handbook of enumerative combinatorics, CRC Press, 2015.
^ (EN) N. J. A. Sloane, Sequenza A001003, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation. URL consultato il 3 maggio 2021.
^ Dan Drake, Bijections from weighted Dyck paths to Schröder paths (PDF), 2010. URL consultato il 2 maggio 2021.
^ Eva Y. P. Deng e Wei-Jun Yan, Some identities on the Catalan, Motzkin, and Schröder numbers, in Discrete Applied Mathematics, vol. 156, 166-218X, 2008, pp. 2781-2789, DOI:10.1016/j.dam.2007.11.014.
^ ^a ^b ^c N. J. A. Sloane, Triangular array associated with Schroeder numbers, su oeis.org, The On-Line Encyclopedia of Integer Sequences.
^ ^a ^b Feng Oi e Bai-Ni Guo, Some explicit and recursive formulas of the large and little Schröder numbers, in Arab Journal of Mathematical Sciences, vol. 23, n. 1319-5166, 2017, pp. 141-147, DOI:10.1016/j.ajmsc.2016.06.002.
^ Sen-Peng Eu e Tung-Shan Fu, A simple proof of the Aztec diamond theorem, in Electronic Journal of Combinatorics, vol. 12, n. 1077-8926, 2005, pp. Research Paper 18, 8.