Numero di Schröder-Ipparco

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-Ipparco, $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$ o abbia passi che corrono lungo di essa. I numeri di Schröder-Ipparco sono detti anche piccoli numeri di Schröder e differiscono dai "grandi numeri di Schröder" per il fatto che questi ultimi tengono anche conto dei cammini che non aderiscono all'ultima delle condizioni sopra elencate.

I percorsi di Schröder per n=2.

I percorsi di Schröder-Ipparco per n=2.

La successione di tali numeri interi, che prendono il nome dal matematico tedesco Ernst Schröder e dall'antico matematico greco Ipparco di Nicea, che ci è noto conoscesse tali numeri, per $n=0,1,\dots$, ha come primi elementi:

1, 1, 3, 11, 45, 197, 903, 4 279, 20 793, 103 049, ...

Applicazioni in combinatoria

Le undici suddivisioni di un pentagono.

In combinatoria la successione dei numeri di Schröder-Ipparco può essere utilizzata in diversi oggetti relativi a tale branca della matematica:

Equivalenza combinatoria tra suddivisioni di un poligono, alberi ordinati e parentesizzazioni.

• L'$n$-simo numero della successione rappresenta il numero di modi diversi in cui si può suddividere un poligono di $n+1$ lati in poligoni più piccoli utilizzando le diagonali del poligono stesso.
• L'$n$-simo numero della successione rappresenta il numero di alberi ordinati con $n$ foglie e con tutti i nodi interni aventi due o più figli.
• L'$n$-simo numero della successione rappresenta il numero di modi diversi in cui si può inserire delle parentesi all'interno di una successione di $n+1$ simboli, con ogni coppia di parentesi che circonda due o più simboli o gruppi già fra parentesi, e senza alcuna parentesi posta attorno alla successione intera.
• L'$n$-simo numero della successione rappresenta il numero di facce di tutte le dimensioni di un associaedro $K_{n+1}$ di dimensione $n-1$, includendo l'associaedro stesso come faccia ma non includendo l'insieme vuoto. Per esempio, l'associaedro bidimensionale $K_{4}$ è un pentagono; ha cinque vertici, cinque facce, più l'associaedro intero, per un totale di 11 facce.

Come mostrato in figura, c'è una semplice equivalenza combinatoria tra questi oggetti: la suddivisione di un poligono ha un albero ordinato come forma del proprio grafo duale, e in tale albero, le foglie corrispondono ai simboli in una successione parentesizzata mentre i nodi interni, ma non la radice, corrispondono ai gruppi parentesizzati. La successione parentesizzata stessa può essere scritta lungo il perimetro del poligono con i suoi simboli lungo i lati del poligono e le parentesi agli estremi delle diagonali scelte. Ciò equivale a dare una dimostrazione mediante biiezione del fatto che tutti questi generi di oggetti possono essere conteggiati attraverso un'unica successione di interi.

La successione enumera poi anche il numero di permutazioni doppie, ossia successioni di numeri che vanno da $1$ a $n$, in cui ogni numero appare due volte e in cui la prima apparizione di ogni numero avviene in ordine crescente, che evitano gli schemi 12312 e 121323.

Successioni correlate

I numeri della già citata successione dei numeri grandi di Schröder sono pari a due volte i numeri di Schröder-Ipparco, e possono anch'essi essere utilizzati per conteggiare diversi oggetti trattati in combinatoria, essi rappresentano ad esempio 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. Un'altra successione di interi correlata ai numeri di Schröder-Ipparco è quella dei numeri di Catalan, che rappresentano, tra le altre cose, il numero di modi in cui un poligono convesso con $n+2$ lati può essere suddiviso in triangoli e il numero di modi in cui si possono inserire coppie di parentesi in una successione di simboli in modo tale che ogni coppia circondi esattamente due simboli o due gruppi già circondati da parentesi.

Data una successione di operatori lineari naturalmente definiti su successioni di interi, se viste come vettori riga di dimensione infinita, la successione dei numeri di Catalan e quella dei numeri di Schröder-Ipparco sono gli unici autovettori dei primi due elementi di tale successione. Più in generale la $k$-sima successione in questa successione di successioni di interi è $(x_{1},\,x_{2},\,x_{3},\,\ldots )$, dove i numeri $x_{n}$ sono calcolati come somme di numeri di Narayana moltiplicati per potenze di $k$. Ciò può essere espresso come una funzione ipergeometrica:

$x_{n}=\sum _{i=1}^{n}N(n,i)\,k^{i-1}=\sum _{i=1}^{n}{\frac {1}{n}}{n \choose i}{n \choose i-1}k^{i-1}={}_{2}F_{1}(1-n,-n;2;k).$

Ponendo $k=1$ in tale equazione si ottiene la successione dei numeri di Catalan, mentre ponendo $k=2$ si ottiene la successione dei numeri di Schröder-Ipparco.

Ricorrenza

Così come la sommatoria precedentemente citata, la successione dei numeri di Schröder-Ipparco può essere definita da una relazione di ricorrenza:

$S(n)={\frac {1}{n}}\left((6n-9)S(n-1)-(n-3)S(n-2)\right).$

Ciò è stato dimostrato da Richard P. Stanley utilizzando delle funzioni generatrici mentre Dominique Foata e Doron Zeilberger hanno fornito una diretta prova combinatoria.

Storia

Nei Moralia di Plutarco, l'autore racconta di un dialogo avvenuto tra il filosofo Stoico Crisippo di Soli, che sosteneva che le proposizioni composte che si potevano fare con solo 10 proposizioni fossero più di un milione, e l'astronomo Ipparco di Nicea, suo contemporaneo. In particolare il brano recita:

"Crisippo dice che il numero di proposizioni composte che possono essere formate a partire da dieci sole proposizioni supera il milione. Ipparco dimostrò però che tale numero è 103049 in senso affermativo (ossia utilizzando solo i connettivi "e" e "o") e 310952 in senso negativo (ossia ammettendo anche l’uso della negazione)".

Tale scritto rimase senza spiegazione fino al 1994, quando David Hough, della George Washington University, osservò che c'erano 103 049 modi di inserire parentesi in una successione di 10 elementi, essendo in effetti il decimo numero della successione di Schröder-Ipparco. Per quanto riguarda il numero 310 952, la sua interpretazione resta oscura, tuttavia sebbene tale numero non appaia nelle sequenze di numeri legate alla matematica combinatoria note, lo storico della matematica Fabio Acerbi (CNRS) ha mostrato come esso sia pari alla media del decimo e dell'undicesimo numero di Schröder-Ipparco meno due, ed è pari al numero di modi in cui si possono inserire due parentesi in una successione di dieci termini assieme a una particella negativa.

Nel 2011 la filosofa Susanne Bobzien ha obiettato che, sulla base della logica Stoica, un sistema di logica proposizionale sviluppato dagli Stoici, fosse il calcolo di Crisippo ad essere quello giusto. Ricostruendo i calcoli fatti da Ipparco e da Crisippo, la Bobzien sostiene che l'aver mostrato l'esattezza matematica del calcolo di Ipparco ma la sua inesattezza logica potrebbe gettare nuova luce sulle nozioni stoiche di congiunzioni e asseribili.

Voci correlate

• Numero di Delannoy
• Numero di Motzkin

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su numero di Schröder-Ipparco

Collegamenti esterni

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