Număr Schröder–Hiparh

Număr Schröder–Hiparh

Numit după	Ernst Schröder, Hiparh, Eugène Charles Catalan
Anul publicării	1870 (Schröder)
Nr. de termeni cunoscuți	infinit
Formula	${\displaystyle x_{n}=\sum _{i=1}^{n}{\frac {1}{n}}{n \choose i}{n \choose i-1}k^{i-1}}$
Primii termeni	1, 1, 3, 11, 45, 197, 903
Index OEIS	A001003 Little Schroeder numbers, Super Catalan

Unsprezece subdiviziuni ale unui pentagon

În combinatorică, numerele Schröder–Hiparh formează un șir de numere întregi care poate fi folosit pentru a enumera arborii planari cu un număr dat de noduri terminale (frunze), numărul de paranteze inserate într-o succesiune de caractere și numărul de moduri de împărțire a unui poligon convex în poligoane mai mici prin trasarea coardelor. Mai sunt numite numere super Catalan, numere Schröder mici sau numere Hiparh,^[1] după numerele Catalan ale lui Eugène Charles Catalan, numerele Schröder asemănătoare ale lui Ernst Schröder și matematicianul Hiparh din Grecia antică, despre care Plutarh afirmă că le cunoștea.

Primii termeni ai acestui șir sunt:^[2]

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963, 1618362158587, 8759309660445, 47574827600981, 259215937709463, 1416461675464871, ...

Aplicații în combinatorică

Echivalența combinatorică între subdiviziunile unui poligon, arbori planari și perechi de paranteze

Numerele Schröder–Hiparh pot fi utilizate pentru a indica numărul elementelor din obiecte combinatorice strâns legate:^[3][4][5][6]

• Al n-lea număr din șir indică numărul de posibilități de divizare a unui poligon cu n + 1 laturi în poligoane mai mici prin trasarea de coarde în poligonul inițial.

• Al n-lea număr din șir indică numărul de arbori planari diferiți cu n frunze și cu toate nodurile interne având doi sau mai mulți fii.

• Al n-lea număr din șir indică numărul de perechi de paranteze care pot fi inserate într-un șir de n + 1 simboluri, între parantezele fiecărei perechi fiind alte simboluri sau grupuri de paranteze care conțin simboluri, însă fără parantezele care conțin întregul șir.

• Al n-lea număr din șir indică numărul de fețe din toate dimensiunile ale unui asociaedru K_n + 1 de dimensiunea n − 1, incluzând asociaedrul însuși ca față, dar fără a include [[mulțime vidă |mulțimea vidă. De exemplu, asociaedrul bidimensional K₄ este un pentagon; are cinci vârfuri, cinci fețe și poligonul însuși, în total 11 fețe.

Așa cum se vede în figură, există o echivalență combinatorie simplă între aceste obiecte: o subdiviziune a poligonului are un arbore planar ca formă a grafului dual al acestuia, frunzele arborelui corespund simbolurilor dintr-o secvență dintre paranteze iar nodurile interne ale arborelui, altele decât rădăcina, corespund grupurilor dintre paranteze. Secvența dintre paranteze însăși poate fi înscrisă în jurul perimetrului poligonului cu simbolurile sale pe laturile poligonului și cu parantezele la capetele coardelor selectate. Această echivalență oferă o demonstrație bijectivă că toate aceste tipuri de obiecte sunt contorizate de un singur șir de întregi.^[4]

Aceleași numere indică și numărul de permutari duble (secvențe ale numerelor de la 1 la n, fiecare număr apărând de două ori, cu primele apariții ale fiecărui număr în ordine sortată) care evită modelele de permutare 12312 și 121323.^[7]

Șiruri asemănătoare

Asemănătoarele numere Schröder mari sunt egale cu dublul numerelor Schröder–Hiparh și pot fi, de asemenea, utilizate pentru a număra mai multe tipuri de obiecte combinatorice, inclusiv anumite tipuri de căi de rețea, partiții ale unui dreptunghi în dreptunghiuri mai mici prin divizare recursivă și paranteze în care este permisă și o pereche de paranteze care înconjoară o întreagă secvență de elemente. Numerele Catalan numără, de asemenea, mulțimi asemănătoare de obiecte, inclusiv subdivizări ale unui poligon în triunghiuri, arbori planari în care toate nodurile interne au exact doi fii și paranteze în care fiecare pereche de paranteze înconjoară exact două simboluri sau perechi de paranteze.^[5]

Succesiunea numerelor Catalan și șirul numerelor Schröder–Hiparh, privite ca vectori infinit dimensionali, sunt vectorii proprii unici pentru primele două într-o secvență de operatori liniari definiți natural pe secvențe numerice.^[8][9] Mai general, secvența k a acestui șir de întregi este (x₁, x₂, x₃, ...) unde numerele x_n sunt calculate ca sumele ale numerelor Narayana înmulțite cu puterile lui k. Aceasta poate fi exprimată ca o funcție hipergeometrică:

${\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).}$

Înlocuind k = 1 în această formulă se obțin numerele Catalan și înlocuind k = 2 în această formulă se dau numerele Schröder–Hiparh.^[9]

În legătură cu proprietatea numerelor Schröder–Hiparh de a indica numărul fețelor unui asociaedru, numărul vârfurilor asociaedrului este dat de numerele Catalan. Numerele corespunzătoare pentru permutoedru sunt respectiv numerele Bell ordonate și factorialii.

Recurență

Pe lângă formula de însumare de mai sus, numerele Schröder–Hiparh pot fi definite printr-o relație de recurență:

${\displaystyle S_{n}={\frac {1}{n}}\left[(6n-9)S_{n-1}-(n-3)S_{n-2}\right].}$

Stanley demonstrează acest fapt folosind funcțiile generatoare^[10] în timp ce Foata și Zeilberger dau o demonstrație combinatorie directă.^[11]

Istoric

Moralia lui Plutarh conține linia:^[10]

Chrysippus spune că numărul propozițiilor compuse care pot fi făcute din doar zece propoziții simple depășește un milion. (Hiparh, cu siguranță, a respins acest lucru arătând că pentru forma afirmativă există 103049 enunțuri compuse, iar în forma negativă 310952.)

Această afirmație a rămas neexplicată până în 1994, când David Hough, absolvent al Universității George Washington, a observat că există 103049 de moduri de a insera paranteze într-o secvență de zece termeni.^[3][10][12] Istoricul matematicii Fabio Acerbi (CNRS) a arătat că se poate oferi o explicație similară pentru celălalt număr: este foarte aproape de media numărului al zecelea și al unsprezecelea Schröder–Hiparh, 310954, și numără parantezele dintre zece termeni împreună cu o particulă de negare.^[12]

Relatarea lui Plutarh a celor două numere ale lui Hiparh consemnează un dezacord între Hiparh și filosoful stoic anterior Chrysippus, care susținuse că numărul propozițiilor compuse care pot fi făcute din 10 propoziții simple depășește un milion. Filosoful contemporan Format:Harvs a susținut că calculul lui Chrysippus a fost cel corect, pe baza analizei făcute de ea a logicii stoice. Bobzien reconstruiește calculele atât ale lui Chrysippus, cât și ale lui Hiparh și spune că modul de calcul al lui Hiparh a fost corect, dar logica sa greșită din punct de vedere stoic. Asta poate arunca o nouă lumină asupra noțiunilor de conjuncții și afirmații din logica stoică.^[13]

Problema numărării parantezelor a fost introdusă în matematica modernă de către Schröder (1870).^[14]

Note

1. Marius Coman, Enciclopedia matematică a claselor de numere întregi, Columbus, Ohio: Education Publishing, 2013, ISBN: 978-1-59973-237-4, p. 77
2. Șirul A001003 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
3. ^ en Stanley, Richard P. (1997, 1999), Enumerative Combinatorics, Cambridge University Press. Exercise 1.45, vol. I, p. 51; vol. II, pp. 176–178 and p. 213.
4. ^ en Shapiro, Louis W.; Sulanke, Robert A. (2000), „Bijections for the Schröder numbers”, Mathematics Magazine, 73 (5): 369–376, doi:10.2307/2690814, JSTOR 2690814, MR 1805263 .
5. ^ en Etherington, I. M. H. (1940), „Some problems of non-associative combinations (I)”, Edinburgh Mathematical Notes, 32: 1–6, doi:10.1017/S0950184300002639  .
6. en Holtkamp, Ralf (2006), „On Hopf algebra structures over free operads”, Advances in Mathematics, 207 (2): 544–565, arXiv:math/0407074 , doi:10.1016/j.aim.2005.12.004, MR 2271016 .
7. en Chen, William Y. C.; Mansour, Toufik; Yan, Sherry H. F. (2006), „Matchings avoiding partial patterns”, Electronic Journal of Combinatorics, 13 (1): Research Paper 112, 17 pp. (electronic), doi:10.37236/1138 , MR 2274327 .
8. en Bernstein, M.; Sloane, N. J. A. (1995), „Some canonical sequences of integers”, Linear Algebra and Its Applications, 226/228: 57–72, arXiv:math/0205301 , doi:10.1016/0024-3795(94)00245-9, MR 1344554 .
9. ^ Coker, Curtis (2004), „A family of eigensequences”, Discrete Mathematics, 282 (1–3): 249–250, doi:10.1016/j.disc.2003.12.008, MR 2059525 .
10. ^ en Stanley, Richard P. (1997), „Hipparchus, Plutarch, Schröder, and Hough” (PDF), American Mathematical Monthly, 104 (4): 344–350, doi:10.2307/2974582, JSTOR 2974582, MR 1450667 
11. en Foata, Dominique; Zeilberger, Doron (1997), „A classic proof of a recurrence for a very classical sequence”, Journal of Combinatorial Theory, Series A, 80 (2): 380–384, arXiv:math/9805015 , doi:10.1006/jcta.1997.2814, MR 1485153 .
12. ^ en Acerbi, F. (2003), „On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics” (PDF), Archive for History of Exact Sciences, 57: 465–502, doi:10.1007/s00407-003-0067-0, arhivat din original (PDF) la 21 iulie 2011 .
13. en Bobzien, Susanne (2011), „The Combinatorics of Stoic Conjunction: Hipparchus refuted, Chrysippus vindicated” (PDF), Oxford Studies in Ancient Philosophy, XL: 157–188 .
14. de Schröder, Ernst (1870), „Vier kombinatorische Probleme”, Zeitschrift für Mathematik und Physik, 15: 361–376 .

Vezi și

• Număr Delannoy
• Număr Motzkin
• Număr Narayana
• Număr Schröder
• Număr Catalan

Legături externe

• en Eric W. Weisstein, Super Catalan Number la MathWorld.
• en The Hipparchus Operad, The n-Category Café, April 1, 2013