Vizualizare sursă pentru „Număr Schröder–Hiparh”

{{Infocaseta Șiruri de numere întregi
| named_after = [[Ernst Schröder]], [[Hiparh]], [[Eugène Charles Catalan]]
| publication_year = 1870 (Schröder)
| terms_number = [[infinit]]
| formula = <math>x_n = \sum_{i=1}^n \frac{1}{n}{n\choose i}{n\choose i-1} k^{i-1}</math>
| first_terms = [[1 (cifră)|1]], [[1 (cifră)|1]], [[3 (cifră)|3]], [[11 (număr)|11]], [[45 (număr)|45]], [[197 (număr)|197]], 903
| OEIS = A001003
| OEIS_name = Little Schroeder numbers,<br/>Super Catalan
}}
[[Fișier:Pentagon subdivisions.svg|thumb|260px|Unsprezece subdiviziuni ale unui pentagon]]
În [[combinatorică]], '''numerele Schröder–Hiparh''' formează un șir de numere întregi care poate fi folosit pentru a enumera [[Arbore (teoria grafurilor) |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''',<ref name=C77>Marius Coman, ''Enciclopedia matematică a claselor de numere întregi'', Columbus, Ohio: Education Publishing, 2013, {{ISBN|978-1-59973-237-4}}, p.&nbsp;77</ref> după [[număr Catalan |numerele Catalan]] ale lui [[Eugène Charles Catalan]], [[număr Schröder |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:<ref>{{OEIS|A001003}}</ref>
:[[1 (cifră)|1]], [[1 (cifră)|1]], [[3 (cifră)|3]], [[11 (număr)|11]], [[45 (număr)|45]], [[197 (număr)|197]], 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963, 1618362158587, 8759309660445, 47574827600981, 259215937709463, 1416461675464871, ...

== Aplicații în combinatorică ==
[[Fișier:Tree-polygon-paren equivalence.svg|thumb|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:<ref name="stan-ec">{{en icon}} [[Richard P. Stanley|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.</ref><ref name="ss">{{en icon}} {{citation
 | last1 = Shapiro | first1 = Louis W. |authorlink1=Louis Shapiro (mathematician)
 | last2 = Sulanke | first2 = Robert A.
 | doi = 10.2307/2690814
 | issue = 5
 | journal = Mathematics Magazine
 | mr = 1805263
 | pages = 369–376
 | title = Bijections for the Schröder numbers
 | volume = 73
 | year = 2000| jstor = 2690814 }}.</ref><ref name="eth">{{en icon}} {{citation
 | last = Etherington | first = I. M. H. | author-link = Ivor Malcolm Haddon Etherington
 | doi = 10.1017/S0950184300002639
 | journal = Edinburgh Mathematical Notes
 | pages = 1–6
 | title = Some problems of non-associative combinations (I)
 | volume = 32
 | year = 1940| doi-access = free
 }}.</ref><ref>{{en icon}} {{citation
 | last = Holtkamp | first = Ralf
 | arxiv = math/0407074
 | doi = 10.1016/j.aim.2005.12.004
 | issue = 2
 | journal = Advances in Mathematics
 | mr = 2271016
 | pages = 544–565
 | title = On Hopf algebra structures over free operads
 | volume = 207
 | year = 2006}}.</ref>
* Al ''n''-lea număr din șir indică numărul de posibilități de divizare a unui poligon cu ''n''&nbsp;+&nbsp;1 [[latură (geometrie)|laturi]] în poligoane mai mici prin trasarea de coarde în poligonul inițial.

* Al ''n''-lea număr din șir indică numărul de [[Arbore (teoria grafurilor) |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''&nbsp;+&nbsp;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 [[față (geometrie)|fețe]] din toate dimensiunile ale unui [[asociaedru]] ''K''<sub>''n''&nbsp;+&nbsp;1</sub> de dimensiunea ''n''&nbsp;&minus;&nbsp;1, incluzând asociaedrul însuși ca față, dar fără a include [[mulțime vidă |mulțimea vidă. De exemplu, asociaedrul bidimensional ''K''<sub>4</sub> este un [[pentagon]]; are cinci [[vârf (geometrie)|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 [[graf]]ului [[dualitate (matematică)|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.<ref name="ss"/>

Aceleași numere indică și numărul de [[permutare dublă |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.<ref>{{en icon}} {{citation
 | last1 = Chen | first1 = William Y. C.
 | last2 = Mansour | first2 = Toufik
 | last3 = Yan | first3 = Sherry H. F.
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 2274327
 | page = Research Paper 112, 17 pp. (electronic)
 | title = Matchings avoiding partial patterns
 | url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1r112.html
 | volume = 13
 | year = 2006| doi = 10.37236/1138
 | doi-access = free
 }}.</ref>

== Șiruri asemănătoare ==
Asemănătoarele [[număr Schröder |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. [[Număr Catalan |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.<ref name="eth"/>

Succesiunea numerelor Catalan și șirul numerelor Schröder–Hiparh, privite ca [[vector]]i infinit dimensionali, sunt [[vector propriu |vectorii proprii]] unici pentru primele două într-o secvență de [[transformare liniară|operatori liniari]] definiți natural pe secvențe numerice.<ref name="bs">{{en icon}} {{citation
 | last1 = Bernstein | first1 = M.
 | last2 = Sloane | first2 = N. J. A. | author2-link = Neil Sloane
 | doi = 10.1016/0024-3795(94)00245-9
 | journal = Linear Algebra and Its Applications
 | mr = 1344554
 | pages = 57–72
 | title = Some canonical sequences of integers
 | volume = 226/228
 | year = 1995| arxiv = math/0205301
 }}.</ref><ref name="coker">{{citation
 | last = Coker | first = Curtis
 | doi = 10.1016/j.disc.2003.12.008
 | issue = 1–3
 | journal = Discrete Mathematics
 | mr = 2059525
 | pages = 249–250
 | title = A family of eigensequences
 | volume = 282
 | year = 2004}}.</ref> Mai general, secvența ''k'' a acestui șir de întregi este (''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ...) unde numerele ''x<sub>n</sub>'' sunt calculate ca sumele ale [[număr Narayana |numerelor Narayana]] înmulțite cu puterile lui&nbsp;''k''. Aceasta poate fi exprimată ca o [[funcție hipergeometrică]]:
:<math>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}={}_2F_1(1-n,-n;2;k).</math>
Înlocuind ''k''&nbsp;=&nbsp;1 în această formulă se obțin numerele Catalan și înlocuind ''k''&nbsp;=&nbsp;2 în această formulă se dau numerele Schröder–Hiparh.<ref name="coker"/>

Î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 [[număr Bell ordonat |numerele Bell ordonate]] și [[factorial]]ii.

== Recurență ==
Pe lângă formula de însumare de mai sus, numerele Schröder–Hiparh pot fi definite printr-o [[relație de recurență]]:
:<math>S_n=\frac{1}{n}\left[(6n-9)S_{n-1}-(n-3)S_{n-2}\right].</math>
Stanley demonstrează acest fapt folosind [[funcție generatoare |funcțiile generatoare]]<ref name="stan-amm">{{en icon}} {{citation
 | last = Stanley | first = Richard P.
 | doi = 10.2307/2974582
 | issue = 4
 | journal = American Mathematical Monthly
 | mr = 1450667
 | pages = 344–350
 | title = Hipparchus, Plutarch, Schröder, and Hough
 | url = http://www-math.mit.edu/~rstan/papers/hip.pdf
 | volume = 104
 | year = 1997| jstor = 2974582 }}</ref> în timp ce Foata și Zeilberger dau o demonstrație combinatorie directă.<ref>{{en icon}} {{citation
 | last1 = Foata | first1 = Dominique | author1-link = Dominique Foata
 | last2 = Zeilberger | first2 = Doron | author2-link = Doron Zeilberger
 | arxiv = math/9805015
 | doi = 10.1006/jcta.1997.2814
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series A
 | mr = 1485153
 | pages = 380–384
 | title = A classic proof of a recurrence for a very classical sequence
 | volume = 80
 | year = 1997}}.</ref>

== Istoric ==
''[[Moralia]]'' lui [[Plutarh]] conține linia:<ref name=stan-amm/>
: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 [[Universitatea George Washington |Universității George Washington]], a observat că există 103049 de moduri de a insera paranteze într-o secvență de zece termeni.<ref name="stan-ec"/><ref name="stan-amm"/><ref name="acerbi">{{en icon}} {{citation
 |last        = Acerbi
 |first       = F.
 |journal     = Archive for History of Exact Sciences
 |pages       = 465–502
 |title       = On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics
 |url         = http://stl.recherche.univ-lille3.fr/sitespersonnels/acerbi/acerbipub5.pdf
 |volume      = 57
 |year        = 2003
 |doi         = 10.1007/s00407-003-0067-0
 |url-status     = dead
 |archiveurl  = https://web.archive.org/web/20110721023220/http://stl.recherche.univ-lille3.fr/sitespersonnels/acerbi/acerbipub5.pdf
 |archivedate = 2011-07-21
}}.</ref> 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.<ref name="acerbi"/>

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 {{harvs|first=Susanne|last=Bobzien|year=2011|txt}} a susținut că calculul lui Chrysippus a fost cel corect, pe baza analizei făcute de ea a [[logică|logicii]] [[stoicism|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ă.<ref name=Bobzien>{{en icon}} {{citation
 | last = Bobzien | first = Susanne
 | title = The Combinatorics of Stoic Conjunction: Hipparchus refuted, Chrysippus vindicated
 | journal = Oxford Studies in Ancient Philosophy
 | volume = XL
 | date = Summer 2011
 | url = http://ancphil.lsa.umich.edu/-/downloads/osap/40-Bobzien.pdf
 | pages = 157–188}}.</ref>

Problema numărării parantezelor a fost introdusă în matematica modernă de către {{harvtxt|Schröder|1870}}.<ref>{{de icon}} {{citation
 | last = Schröder | first = Ernst
 | journal = Zeitschrift für Mathematik und Physik
 | pages = 361–376
 | title = Vier kombinatorische Probleme
 | volume = 15
 | year = 1870}}.</ref>

== Note ==
{{listănote|2}}

== Vezi și ==
*[[Număr Delannoy]]
*[[Număr Motzkin]]
*[[Număr Narayana]]
*[[Număr Schröder]]
*[[Număr Catalan]]

== Legături externe ==
*{{en icon}} {{mathworld|title=Super Catalan Number|urlname=SuperCatalanNumber}}
*{{en icon}} [http://golem.ph.utexas.edu/category/2013/04/permutations_polynomials_and_p.html The Hipparchus Operad], The n-Category Café, April 1, 2013

[[Categorie:Șiruri de numere întregi|Schroder-Hiparh]]
[[Categorie:Combinatorică]]