Schroeder-Hipparkhosz számok

A Schroeder-Hipparkhosz- számok egész számok sorozatát alkotják [ , amellyel megszámolható az adott számú levelű platánfák száma , hány módja van zárójelek beszúrásának a sorozatba, és hány módon lehet felosztani egy konvex sokszöget átlók rajzolásával kisebb sokszögekké alakítani. Ez a sorozat azzal kezdődik

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... OEIS sorozat A001003 .

Ezeket a számokat szuperkatalán számoknak , kis Schroeder-számoknak vagy Hipparkhosz-számoknak is nevezik ( Eugene Charles Catalan és katalán számai , Ernst Schroeder és a vele szorosan összefüggő Schroeder-számok , az ókori görög matematikus , Hipparkhosz , aki Plutarkhosz szerint ismerte ezeket a számokat).

Alkalmazások kombinatorikus felsoroláshoz

A Schroeder-Hipparkhosz-számok felhasználhatók néhány szorosan összefüggő kombinatorikus objektum megszámlálására [1] [2] [3] [4] :

Amint az ábra mutatja, van egy egyszerű kombinatorikus ekvivalencia ezen objektumok között – egy sokszögpartíció kettős gráfja egy síkfa , ennek a fa levelei a zárójelben szereplő karaktereknek felelnek meg, a fa belső csúcsai pedig nem a gyökér zárójelcsoportoknak felel meg. Egy sokszög kerülete mentén zárójeles sorozatot írhatunk úgy, hogy a kiválasztott átlók oldalain szimbólumok, a végein pedig zárójelek találhatók. Ez az ekvivalencia bijektív bizonyítékot ad arra , hogy az összes ilyen típusú objektumot egyetlen egész sorozat számítja [2] .

Ugyanezek a számok a kettős permutációk számát is számolják (1-től n -ig tartó számsorok , minden szám kétszer jelenik meg, minden szám először jelenik meg rendezett sorrendben), amelyek elkerülik a 12312 és 121323 permutációs mintákat [5 ] .

Kapcsolódó sorozatok

A szorosan összefüggő nagy Schroeder-számok megegyeznek a Schroeder-Hipparkhosz-számok kétszeresével, és bizonyos típusú kombinatorikus objektumok megszámlálására is használhatók, beleértve a rácsban lévő egyes útvonalakat, a téglalap felosztását kisebb téglalapokra rekurzív osztással, és zárójeleket, amikor zárójelpár is megengedett, beleértve a teljes elemsort. A katalán számok szorosan kapcsolódó objektumkészleteket is számolnak, beleértve a sokszög háromszögekre bontását, a síkfákat, amelyekben minden belső csúcsnak pontosan két gyermeke van, és a zárójelek közötti távolságot, ahol minden zárójelpár pontosan két karaktert vagy zárójelcsoportot vesz körül [3] .

A katalán számsorozat és a Schroeder-Hipparchosz számsor, ha végtelen dimenziós vektoroknak tekintjük, az egyetlen sajátvektor a számsorozatok természetesen definiált lineáris operátorai sorozatának első kettőjéhez [6] [7] . Általánosabban, a k -edik sorozat ebben az egész sorozatban , ahol az x n számokat a Narayana számok összegeként szorozzuk k hatványaival . Ez egy hipergeometrikus függvényként ábrázolható :

 Ha ebben a képletben k = 1-et helyettesítünk , akkor a katalán számokat kapjuk, a k  = 2-t pedig a Schroeder-Hipparkhosz-számokat kapjuk [7] .

Ha az asszociaéder lapjainak számát a Schroeder-Hipparkhosz-számok adják meg, akkor az asszociaéder csúcsainak számát a katalán számok. A permutációs poliéder megfelelő számai a rendezett Bell-számok és a faktoriálisok .

Rekurzió

A fenti összegzési képlethez hasonlóan a Schroeder-Hipparkhosz-számok a rekurzív képlettel határozhatók meg :

Stanley ezt a tényt függvénygeneráló szekvenciákkal igazolta [8] , míg Foata és Zeilberger közvetlen kombinatorikus bizonyítást [9] adott .

Történelem

Plutarkhosz párbeszéde (a Table Talk-ból) a következő sort tartalmazza:

Chrysippus azt mondja, hogy a tíz egyszerű állításból megfogalmazható összetett állítások száma eléri az egymilliót. (Hipparkhosz ezt kétségtelenül cáfolta, kimutatva, hogy 103 049 igenlő komplex állítás létezik, és 310 952 negatív.) [8] .

Ez az állítás 1994-ig megmagyarázhatatlan maradt, amikor is David Hough, a George Washington Egyetem mesterszakos hallgatója észrevette, hogy 103 049 módon lehet zárójeleket beilleszteni egy tíz elemből álló karakterláncba [1] [8] [10] . Hasonló magyarázatot adhatunk egy másik számra is – ez nagyon közel áll a tíz Schroeder-Hipparkhosz-szám átlagához, 310954, és felsorolja a tíz elem összes zárójel-elrendezését a negatív részecskével együtt [10] .

A zárójelek számolásának problémáját Schroeder vezette be a modern matematikába [11] .

Plutarkhosz két Hipparkhosz-számra vonatkozó számítása felfedi Hipparkhosz és a korábbi görög filozófus, Chrysippus közötti nézeteltérést , aki azzal érvelt, hogy a tíz egyszerű állításból megfogalmazható összetett állítások száma eléri az egymilliót. Suzanne Bobzin [12] , a modern filozófia képviselője kifogásolta, hogy Chrysippus számítása helyes volt, a sztoikus logika elemzése alapján. Susanna Bobzin rekonstruálta mind Chrysippus, mind Hipparkhosz számításait, és kijelentette, hogy az a módszer, amellyel Hipparkhosz a hibás sztoikus logikájából kapott matematikailag helyes eredményeket, új megvilágításba helyezi a kötőszó és az állítás sztoikus fogalmait [13] .


Jegyzetek

  1. ↑ 12. Stanley , 1999 , p. 1.45. gyakorlat, 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. Research Paper 112, 17 pp.
  6. ↑ Bernstein és 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.

Irodalom

Linkek