Numero di Schröder-Ipparco

I percorsi di Schröder per n=2.

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

In matematica, data una griglia quadrata di dimensione ${\displaystyle n\times n}$ nel 1° quadrante di un sistema di riferimento cartesiano, il numero di Schröder-Ipparco, ${\displaystyle S_{n}}$, descrive il numero di cammini possibili per arrivare dal punto di coordinate ${\displaystyle (0,0)}$ al punto di coordinate ${\displaystyle (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 ${\displaystyle 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.

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 ${\displaystyle n=0,1,\dots }$, ha come primi elementi:

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

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:^[2][3][4]

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

• L'${\displaystyle n}$-simo numero della successione rappresenta il numero di modi diversi in cui si può suddividere un poligono di ${\displaystyle n+1}$ lati in poligoni più piccoli utilizzando le diagonali del poligono stesso.
• L'${\displaystyle n}$-simo numero della successione rappresenta il numero di alberi ordinati con ${\displaystyle n}$ foglie e con tutti i nodi interni aventi due o più figli.
• L'${\displaystyle n}$-simo numero della successione rappresenta il numero di modi diversi in cui si può inserire delle parentesi all'interno di una successione di ${\displaystyle 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'${\displaystyle n}$-simo numero della successione rappresenta il numero di facce di tutte le dimensioni di un associaedro ${\displaystyle K_{n+1}}$ di dimensione ${\displaystyle n-1}$, includendo l'associaedro stesso come faccia ma non includendo l'insieme vuoto. Per esempio, l'associaedro bidimensionale ${\displaystyle 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.^[2]

La successione enumera poi anche il numero di permutazioni doppie, ossia successioni di numeri che vanno da ${\displaystyle 1}$ a ${\displaystyle 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.^[5]

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 ${\displaystyle n+1}$ rettangoli più piccoli usando ${\displaystyle n}$ segmenti passanti per ${\displaystyle 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 ${\displaystyle 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.^[3]

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.^[6][7] Più in generale la ${\displaystyle k}$-sima successione in questa successione di successioni di interi è ${\displaystyle (x_{1},\,x_{2},\,x_{3},\,\ldots )}$, dove i numeri ${\displaystyle x_{n}}$ sono calcolati come somme di numeri di Narayana moltiplicati per potenze di ${\displaystyle k}$. Ciò può essere espresso come una funzione ipergeometrica:

${\displaystyle 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 ${\displaystyle k=1}$ in tale equazione si ottiene la successione dei numeri di Catalan, mentre ponendo ${\displaystyle k=2}$ si ottiene la successione dei numeri di Schröder-Ipparco.^[7]

Ricorrenza

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

${\displaystyle 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^[8] mentre Dominique Foata e Doron Zeilberger hanno fornito una diretta prova combinatoria.^[9]

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:^[10]

"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.^[11] 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.^[11]

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

Note

1. (EN) Sequenza A001003, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
2. (EN) Louis W. Shapiro e Robert A. Sulanke, Bijections for the Schröder numbers, in Mathematics Magazine, vol. 73, n. 5, 2000, pp. 369-376, DOI:10.2307/2690814.
3. (EN) I. M. H. Etherington, Some problems of non-associative combinations (I), in Edinburgh Mathematical Notes, vol. 32, 1940, pp. 1-6, DOI:10.1017/S0950184300002639.
4. (EN) Ralf Holtkamp, On Hopf algebra structures over free operads, in Advances in Mathematics, vol. 207, n. 2, 2006, pp. 544-565, DOI:10.1016/j.aim.2005.12.004, arXiv:math/0407074.
5. (EN) William Y. C. Chen, Toufik Mansour e Sherry H. F. Yan, Matchings avoiding partial patterns, in Electronic Journal of Combinatorics, vol. 13, n. 1, 2006, pp. Research Paper 112, 17 pp. (electronic). URL consultato il 4 maggio 2021.
6. (EN) M. Bernstein e N. J. A. Sloane, Some canonical sequences of integers, in Linear Algebra and its Applications, vol. 226/228, 1995, pp. 57-72, DOI:10.1016/0024-3795(94)00245-9, arXiv:math/0205301.
7. (EN) Curtis Coker, A family of eigensequences, in Discrete Mathematics, vol. 282, n. 1-3, 2004, pp. 249-250, DOI:10.1016/j.disc.2003.12.008.
8. (EN) Richard P. Stanley, Hipparchus, Plutarch, Schröder, and Hough (PDF), in American Mathematical Monthly, vol. 104, n. 4, 1997, pp. 344-350, DOI:10.2307/2974582. URL consultato il 5 maggio 2021.
9. (EN) Dominique Foata e Doron Zeilberger, A classic proof of a recurrence for a very classical sequence, in Journal of Combinatorial Theory, vol. 80, n. 2, 1997, pp. 380-384, DOI:10.1006/jcta.1997.2814, arXiv:math/9805015.
10. Mauro Fiorentini, Plutarco (numeri di), su bitman.name, Mauro Fiorentini. URL consultato il 5 maggio 2021.
11. (EN) F. Acerbi, On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics (PDF), in Archive for History of Exact Sciences, vol. 57, 2003, pp. 465-502, DOI:10.1007/s00407-003-0067-0. URL consultato il 5 maggio 2021 (archiviato dall'url originale il 21 luglio 2011).
12. (EN) Susanne Bobzien, The Combinatorics of Stoic Conjunction: Hipparchus refuted, Chrysippus vindicated (PDF), in Oxford Studies in Ancient Philosophy, XL, Estate 2011, pp. 157-188. URL consultato il 5 maggio 2021.

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.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica