Numerele Schroeder-Hipparchus

Numerele Schroeder-Hipparchus formează o secvență de numere întregi care poate fi folosită pentru a număra numărul de platani cu un număr dat de frunze , numărul de moduri de a introduce paranteze în secvență și numărul de moduri de a împărți o poligon convex în poligoane mai mici prin trasarea diagonalelor. Această secvență începe cu

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... secvența OEIS A001003 .

Aceste numere sunt numite și numere supercatalane , numere Schroeder mici sau numere lui Hipparchus ( Eugene Charles Catalan și numerele sale catalane , Ernst Schroeder și numerele strâns legate de Schroeder , matematicianul grec antic Hipparchus , care, conform lui Plutarh , cunoștea aceste numere).

Aplicații pentru enumerații combinatorii

Numerele Schroeder-Hipparchus pot fi folosite pentru a număra unele obiecte combinatorii strâns legate [1] [2] [3] [4] :

După cum arată figura, există o echivalență combinatorie simplă între aceste obiecte - o partiție poligonală are un arbore plan ca grafic dublu , frunzele acestui arbore corespund caracterelor din secvența parantezelor și vârfurile interne ale arborelui, altele decât rădăcina corespund grupurilor de paranteze. O secvență între paranteze poate fi scrisă în jurul perimetrului unui poligon cu simboluri pe laturi și paranteze la capetele diagonalelor alese. Această echivalență oferă o dovadă bijectivă că toate aceste tipuri de obiecte sunt numărate printr-o succesiune întreagă [2] .

Aceleași numere numără și numărul de permutări duble (secvențe de numere de la 1 la n , fiecare număr apărând de două ori, fiecare număr apărând pentru prima dată în ordine sortată), care evită modelele de permutare 12312 și 121323 [5] ] .

Secvențe înrudite

Numerele mari Schroeder strâns legate sunt egale cu dublul numerelor Schroeder-Hipparchus și pot fi, de asemenea, folosite pentru a număra unele tipuri de obiecte combinatorii, inclusiv unele tipuri de căi într-o rețea, împărțirea unui dreptunghi în dreptunghiuri mai mici prin diviziune recursivă și paranteze atunci când este permisă și o pereche de paranteze, inclusiv întreaga secvență de elemente. Numerele catalane numără , de asemenea, seturi de obiecte strâns legate, inclusiv subdiviziunile unui poligon în triunghiuri, platane în care toate vârfurile interioare au exact doi copii și spațierea între paranteze în care fiecare pereche de paranteze înconjoară exact două caractere sau grupuri de paranteze [3] .

Secvența de numere catalane și succesiunea de numere Schroeder-Hipparchus, atunci când sunt considerate ca vectori cu dimensiuni infinite, sunt singurii vectori proprii pentru primii doi din secvența de operatori liniari definiți în mod natural pe secvențe de numere [6] [7] . Mai general, k - a secvență din această secvență de secvențe întregi este , unde numerele x n sunt calculate ca sume ale numerelor Narayana înmulțite cu puterile lui k . Aceasta poate fi reprezentată ca o funcție hipergeometrică :

Înlocuirea k  = 1 în această formulă dă numerele catalane, iar înlocuirea k  = 2 în această formulă dă numerele Schroeder-Hipparchus [7] .

Dacă numărul fețelor asociaedrului este dat de numerele Schroeder-Hipparchus, atunci numărul de vârfuri ale asociaedrului este dat de numerele catalane. Numerele corespunzătoare pentru poliedrul de permutare sunt, respectiv, numerele Bell ordonate și factorialii .

Recursiune

Ca și în formula de însumare de mai sus, numerele Schroeder-Hipparchus pot fi determinate prin formula recursivă :

Stanley a demonstrat acest fapt folosind secvențe generatoare de funcții [8] , în timp ce Foata și Zeilberger au dat o demonstrație combinatorie directă [9] .

Istorie

Dialogul lui Plutarh (din Table Talk) conține rândul:

Chrysippus spune că numărul de afirmații compuse care pot fi făcute din doar zece afirmații simple ajunge la un milion. (Hipparchus a infirmat fără îndoială acest lucru, arătând că există 103.049 afirmații complexe afirmative și 310.952 negative) [8] .

Această afirmație a rămas neexplicată până în 1994, când David Hough, student la master la Universitatea George Washington , a observat că există 103.049 de moduri de a introduce paranteze într-un șir de zece elemente [1] [8] [10] . O explicație similară poate fi dată pentru un alt număr - este foarte aproape de media celor zece numere Schroeder-Hipparchus 310954 și enumeră toate aranjamentele parantezelor pentru cele zece elemente împreună cu particula negativă [10] .

Problema numărării parantezelor a fost introdusă în matematica modernă de către Schroeder [11] .

Calculul lui Plutarh a două numere lui Hiparh dezvăluie un dezacord între Hiparh și filozoful grec anterior Crisip , care a susținut că numărul de afirmații complexe care ar putea fi făcute din zece afirmații simple a fost de până la un milion. Suzanne Bobzin [12] , un reprezentant al filozofiei moderne , a obiectat că calculul lui Chrysippus era corect, bazat pe o analiză a logicii stoice . Susanna Bobzin a reconstituit calculele atât ale lui Hrisip cât și ale lui Hipparh și a declarat că metoda prin care Hiparh și-a obținut rezultatele corecte din punct de vedere matematic din logica sa stoică defectuoasă aruncă o lumină nouă asupra noțiunilor stoice de conjuncție și aserțiune [13] .


Note

  1. ↑ 12 Stanley , 1999 , p. Exerciţiul 1.45, vI/51; vII, /176–178, 213.
  2. ↑ 1 2 Shapiro, Sulanke, 2000 , p. 369–376.
  3. ↑ 12 Etherington , 1940 , p. 1–6.
  4. ↑ Holtkamp, ​​​​2006 , p. 544–565.
  5. ↑ Chen, Mansour, Yan, 2006 , p. Lucrare de cercetare 112, 17 p.
  6. ↑ Bernstein și Sloane 1995 , p. 57–72.
  7. ↑ 12 Coker , 2004 , p. 249–250.
  8. ↑ 1 2 3 Stanley, 1997 , p. 344–350.
  9. ↑ Foata, Zeilberger, 1997 , p. 380–384.
  10. ↑ 1 2 Acerbi, 2003 , p. 465–502.
  11. ↑ Schröder, 1870 , p. 361–376.
  12. ↑ Bobzen, 2011 .
  13. ↑ Bobzien, 2011 , p. 157–188.

Literatură

Link -uri