Katalánské číslo - Catalan number

The C₅ = 42 nepřekračující oddíly sady 5 prvků (níže, dalších 10 z 52 oddíly )

v kombinatorická matematika, Katalánská čísla tvoří a sekvence z přirozená čísla které se vyskytují v různých počítání problémů, často zahrnující rekurzivně definované objekty. Jsou pojmenovány po belgickém matematikovi Eugène Charles Catalan (1814–1894).

The nth katalánské číslo je dáno přímo ve smyslu binomické koeficienty podle

${ displaystyle C_ {n} = { frac {1} {n + 1}} {2n vyberte n} = { frac {(2n)!} {(n + 1)! , n!}} = prod limits _ {k = 2} ^ {n} { frac {n + k} {k}} qquad { text {for}} n geq 0.}$

První katalánská čísla pro n = 0, 1, 2, 3, ... jsou

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 9148256366, 34305961340 4861946401452, ... (sekvence A000108 v OEIS ).

Vlastnosti

Alternativní výraz pro C_n je

${ displaystyle C_ {n} = {2n vybrat n} - {2n zvolit n + 1} = {1 nad n + 1} {2n vybrat n} quad { text {pro}} n geq 0,}$

což je ekvivalent k výrazu uvedenému výše, protože ${ displaystyle { tbinom {2n} {n + 1}} = { tfrac {n} {n + 1}} { tbinom {2n} {n}}}$. To ukazuje C_n je celé číslo, což z prvního uvedeného vzorce není hned zřejmé. Tento výraz tvoří základ pro a důkaz správnosti vzorce.

Katalánská čísla uspokojují relace opakování^[1]

${ displaystyle C_ {0} = 1 quad { text {a}} quad C_ {n + 1} = součet _ {i = 0} ^ {n} C_ {i} , C_ {ni} quad { text {for}} n geq 0,}$

${ displaystyle sum _ {i_ {1} + cdots + i_ {m} = n, i_ {1}, ldots, i_ {m} geq 0} C_ {i_ {1}} cdots C_ {i_ {m}} = { begin {cases} { dfrac {m (n + 1) (n + 2) cdots (n + m / 2-1)} {2 (n + m / 2 + 2) ( n + m / 2 + 3) cdots (n + m)}} C_ {n + m / 2}, & m { text {even}} [5pt] { dfrac {m (n + 1) ( n + 2) cdots (n + (m-1) / 2)} {(n + (m + 3) / 2) (n + (m + 3) / 2 + 1) cdots (n + m)}} C_ {n + (m-1) / 2}, & m { text {odd,}} end {případy}}}$

a

${ displaystyle C_ {0} = 1 quad { text {a}} quad C_ {n + 1} = { frac {2 (2n + 1)} {n + 2}} C_ {n}.}$

Asymptoticky roste katalánský počet

${ displaystyle C_ {n} sim { frac {4 ^ {n}} {n ^ {3/2} { sqrt { pi}}}}}$

v tom smyslu, že kvocient z nth katalánské číslo a výraz vpravo inklinuje k 1 jako n blíží se nekonečnu. To lze dokázat použitím Stirlingova aproximace pron! nebo prostřednictvím generující funkce.

Jediné katalánské číslo C_n které jsou zvláštní, jsou ty, pro které n = 2^k - 1; všichni ostatní jsou sudí. Jediné hlavní katalánské čísla jsou C₂ = 2 a C₃ = 5.^[2]

Katalánská čísla mají integrální zastoupení

${ displaystyle C_ {n} = int _ {0} ^ {4} x ^ {n} rho (x) , dx,}$

kde ${ displaystyle rho (x) = { tfrac {1} {2 pi}} { sqrt { tfrac {4-x} {x}}}.}$ To znamená, že katalánská čísla jsou řešením verze Hausdorffův momentový problém.^[3]

Aplikace v kombinatorice

Existuje mnoho problémů s počítáním kombinatorika jehož řešení je dáno katalánskými čísly. Kniha Enumerativní kombinatorika: svazek 2 kombinatorialist Richard P. Stanley obsahuje sadu cvičení, která popisují 66 různých interpretací katalánských čísel. Následuje několik příkladů s ilustracemi případů C₃ = 5 a C₄ = 14.

Lattice of 14 Dyck words of length 8 - ( a ) interpretováno jako nahoru a dolů

• C_n je počet Dyckova slova^[4] délky 2n. Dyckovo slovo je tětiva skládající se z n X a n Y jsou takové, že žádný počáteční segment řetězce nemá více Y než X. Například následující jsou Dyckova slova délky 6:

• Re-interpretace symbolu X jako otevřeného závorky a Y jako blízká závorka, C_n spočítá počet výrazů obsahujících n páry závorek, které jsou správně přiřazeny:

• C_n je počet různých způsobů n + 1 faktorů může být úplně v závorkách (nebo počet způsobů sdružování n aplikace a binární operátor ). Pro n = 3, například máme následujících pět různých závorek čtyř faktorů:

The spolupracovník řádu 4 s C.₄= 14 plných binárních stromů s 5 listy

• Po sobě jdoucí aplikace binárního operátoru mohou být reprezentovány z hlediska úplnosti binární strom. (Zakořeněný binární strom je úplný pokud má každý vrchol buď dvě děti, nebo žádné děti.) Z toho vyplývá C_n je počet plných binárních souborů stromy s n + 1 listů:

• C_n je počet neizomorfních objednané (nebo rovinné) stromy s n + 1 vrcholy.^[5]
• C_n je počet monotónních příhradové cesty podél okrajů mřížky s n × n čtvercové buňky, které neprocházejí nad úhlopříčkou. Monotónní cesta je cesta, která začíná v levém dolním rohu, končí v pravém horním rohu a sestává výhradně z okrajů směřujících doprava nebo nahoru. Počítání takových cest je ekvivalentní počítání Dyckových slov: X znamená „pohyb vpravo“ a Y znamená „pohyb nahoru“.

Následující diagramy ukazují případ n = 4:

To lze stručně reprezentovat uvedením katalánských prvků podle výšky sloupce:^[6]

Trojúhelníky odpovídají vnitřním uzlům binárních stromů.

• A konvexní mnohoúhelník s n + 2 strany lze řezat trojúhelníky spojením vrcholů s nepřekřížením úsečky (forma polygon triangulace ). Počet vytvořených trojúhelníků je n a počet různých způsobů, jak toho lze dosáhnout, je C_n. Následující šestiúhelníky ilustrují případ n = 4:

• C_n je počet zásobník - přenosný obměny z {1, ..., n}. Obměna w je nazýván stohovatelné -li S(w) = (1, ..., n), kde S(w) je definován rekurzivně takto: write w = unv kde n je největším prvkem v w a u a proti jsou kratší sekvence a jsou nastaveny S(w) = S(u)S(proti)n, s S být identitou pro jednoprvkové sekvence.
• C_n je počet permutací {1, ...,n} které se vyhýbají permutační vzor 123 (nebo alternativně kterýkoli z dalších vzorů délky 3); to znamená počet permutací bez třídobé rostoucí subsekvence. Pro n = 3, tyto permutace jsou 132, 213, 231, 312 a 321. Pro n = 4, jsou to 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 a 4321.
• C_n je počet nepřekračující oddíly ze sady {1, ...,n}. Tím spíše, C_n nikdy nepřekračuje nth Bell číslo. C_n je také počet nepřekračujících oddílů sady {1, ..., 2n} ve kterém má každý blok velikost 2. Spojení těchto dvou faktů může být použito v důkazu od matematická indukce že všechny volný, uvolnit kumulanty stupně více než 2 z Wignerův půlkruhový zákon jsou nula. Tento zákon je důležitý v bezplatná pravděpodobnost teorie a teorie náhodné matice.
• C_n je počet způsobů, jak obkladat výškový tvar schodiště n s n obdélníky. Následující obrázek ilustruje případ n = 4:

• C_n je počet způsobů, jak vytvořit "pohoří" s n zdvihy a n dolní tahy, které zůstanou nad vodorovnou čarou. Interpretace pohoří je, že hory nikdy nepůjdou pod horizont.

• C_n je počet standardní Young tableaux jehož diagram je 2-by-n obdélník. Jinými slovy, jedná se o počet způsobů, jakými jsou čísla 1, 2, ..., 2n lze uspořádat do 2-by-n obdélník tak, aby se každý řádek a každý sloupec zvětšoval. Vzorec jako takový lze odvodit jako speciální případ vzorec délky háku.
• C_n je počet způsobů, jakými jsou vrcholy konvexní 2n-gon lze spárovat tak, aby se úsečky spojující spárované vrcholy neprotínaly. To je přesně podmínka, která zaručuje, že spárované hrany lze identifikovat (sešit) k vytvoření uzavřeného povrchu rodu nula (topologická 2-koule).
• C_n je počet semiordery na n neoznačené položky.^[7]
• V chemickém inženýrství C_n−1 je počet možných separačních sekvencí, které mohou oddělit směs n komponenty.^[8]

Důkaz vzorce

Existuje několik způsobů, jak vysvětlit vzorec

${ displaystyle C_ {n} = { frac {1} {n + 1}} {2n vyberte n}}$

řeší výše uvedené kombinatorické problémy. První níže uvedený důkaz používá a generující funkce. Ostatní důkazy jsou příklady bijektivní důkazy; zahrnují doslova počítání sbírky nějakého druhu objektu, aby se dospělo ke správnému vzorci.

První důkaz

Nejprve pozorujeme, že všechny výše uvedené kombinatorické problémy uspokojují Segnerova^[9] relace opakování

${ displaystyle C_ {0} = 1 quad { text {a}} quad C_ {n + 1} = součet _ {i = 0} ^ {n} C_ {i} , C_ {ni} quad { text {for}} n geq 0.}$

Například každé Dyckovo slovo w délky ≥ 2 lze do formuláře zapsat jedinečným způsobem

w = Xw₁Yw₂

s (možná prázdnými) Dyckovými slovy w₁ a w₂.

The generující funkce pro katalánská čísla je definována

${ displaystyle c (x) = součet _ {n = 0} ^ { infty} C_ {n} x ^ {n}.}$

Recyklační vztah uvedený výše lze potom shrnout do generování funkční formy podle vztahu

${ displaystyle c (x) = 1 + xc (x) ^ {2};}$

jinými slovy, tato rovnice vyplývá z relace rekurence rozšířením obou stran do výkonových řad. Na jedné straně relace opakování jednoznačně určuje katalánská čísla; na druhou stranu lze vztah generující funkce algebraicky vyřešit tak, aby poskytoval

${ displaystyle c (x) = { frac {1 mp { sqrt {1-4x}}} {2x}} = { frac {2} {1 pm { sqrt {1-4x}}} }.}$

Při výběru znaménka mínus (v prvním výrazu) má zlomek výkonovou řadu na 0, takže jeho koeficienty proto musí být katalánská čísla. Toto řešení vyhovuje

${ displaystyle lim _ {x až 0 ^ {+}} c (x) = C_ {0} = 1}$

Druhé řešení se znaménkem plus má pól na 0, takže pro něj nemůže být platným řešením C(X).

Druhá odmocnina může být rozšířena jako mocninová řada pomocí identity

${ displaystyle { sqrt {1 + y}} = součet _ {n = 0} ^ { infty} {{ frac {1} {2}} zvolit n} y ^ {n} = součet _ {n = 0} ^ { infty} { frac {(-1) ^ {n + 1}} {4 ^ {n} (2n-1)}} {2n vyberte n} y ^ {n} = 1 + { frac {1} {2}} y - { frac {1} {8}} y ^ {2} + cdots.}$

Toto je zvláštní případ Newtonova zobecněná binomická věta; stejně jako u obecné věty, lze ji dokázat výpočtem derivací k vytvoření Taylorovy řady. Nastavení y = −4X a dosazení této výkonové řady do výrazu pro C(X) a posun součtového indexu n o 1 se expanze zjednodušuje na

${ displaystyle c (x) = součet _ {n = 0} ^ { infty} {2n vyberte n} { frac {x ^ {n}} {n + 1}}.}$

Koeficienty jsou nyní požadovaným vzorcem pro C_n.

Další způsob, jak se dostat C(X) je vyřešit pro xc(X) a dodržujte to ${ displaystyle int _ {0} ^ {x} ! t ^ {n} , dt}$ se objeví v každém členu výkonové řady.

Druhý důkaz

Obrázek 1. Neplatná část cesty (v plné červené barvě) je převrácena. Špatné cesty dosah (n – 1, n + 1) místo (n,n).

Tento důkaz závisí na triku známém jako Andréova reflexní metoda, který byl původně použit v souvislosti s Bertrandova věta o hlasování. (Princip reflexe byl široce připisován Désiré André, ale jeho metoda ve skutečnosti nepoužívala odrazy; a metoda reflexe je variací kvůli Aeblymu a Mirimanoffovi.^[10]) Počítáme cesty, které začínají a končí na úhlopříčce n × n mřížka. Všechny takové cesty mají n doprava a n nahoru. Protože si můžeme vybrat, který z 2n kroky jsou nahoru (nebo ekvivalentně doprava), existují ${ displaystyle { tbinom {2n} {n}}}$ celkem monotónní cesty tohoto typu. A špatný cesta protne hlavní úhlopříčku a dotkne se další vyšší (fatální) úhlopříčka (na obrázku znázorněna červeně). Otočíme část cesty, která se objeví po dotyku, kolem této fatální úhlopříčky, jak je znázorněno; tato geometrická operace se rovná zaměnění všech kroků doprava a nahoru po tomto dotyku. V části cesty, která se neodráží, je o jeden krok nahoru více než doprava, takže zbývající část špatné cesty má jeden více vpravo než nahoru (protože končí na hlavní diagonále). Když se tato část cesty odráží, bude mít také jeden více nahoru než pravý krok. Protože stále existují 2n kroky, teď už musí být n + 1 kroky nahoru a n - 1 krok vpravo. Takže místo dosažení cíle (n,n), všechny špatné cesty (poté, co se část cesty projeví) skončí v místě (n − 1, n + 1). Jako každá monotónní cesta v (n − 1) × (n + 1) mřížka musí splňovat fatální úhlopříčku, tento proces reflexe nastavuje bijekci mezi špatnými cestami původní mřížky a monotónními cestami této nové mřížky, protože proces reflexe je reverzibilní. Počet špatných cest je tedy,

${ displaystyle {n-1 + n + 1 zvolit n-1} = {2n zvolit n-1} = {2n zvolit n + 1}}$

a počet katalánských cest (tj. dobrých cest) se získá odstraněním počtu špatných cest z celkového počtu monotónních cest původní mřížky,

${ displaystyle C_ {n} = {2n vyberte n} - {2n vyberte n + 1}.}$

Pokud jde o Dyckova slova, začínáme (non-Dyck) sekvencí n X a n Y a vyměňte všechna X a Y po prvním Y, které poruší Dyckův stav. V tom prvním Y jsou k + 1 Y a k X je pro některé k mezi 1 a n − 1.

Třetí důkaz

Následující bijektivní důkaz, i když je více zapojen než ten předchozí, poskytuje přirozenější vysvětlení tohoto pojmu n + 1 ve jmenovateli vzorce proC_n. Zobecněnou verzi tohoto důkazu lze najít v příspěvku Rukavické Josefa (2011).^[11]

Obrázek 2. Cesta s překročením 5.

Předpokládejme, že dostaneme monotónní cestu, která se může stát, že protneme diagonálu. The převaha cesty je definován jako počet vertikální hrany, které leží výše úhlopříčka. Například na obrázku 2 jsou okraje ležící nad úhlopříčkou označeny červeně, takže překročení cesty je 5.

Nyní, pokud dostaneme monotónní cestu, jejíž překročení není nula, můžeme použít následující algoritmus k vytvoření nové cesty, jejíž překročení je o jedno menší než to, kterým jsme začali.

• Začněte zleva doleva a sledujte cestu, dokud nejdříve nepojede nad úhlopříčku.
• Pokračujte v cestě, dokud se nedostanete dotkne se úhlopříčka znovu. Označit podle X první takový okraj, kterého je dosaženo.
• Zaměňte část cesty, která se vyskytla dříve X s částí vyskytující se po X.

Následující příklad by to měl objasnit. Na obrázku 3 černá tečka označuje bod, kde cesta nejprve protíná úhlopříčku. Černá hrana je Xa vyměníme červenou část za zelenou, abychom vytvořili novou cestu, která je znázorněna na druhém diagramu.

Obrázek 3. Probíhá výměna zelené a červené části.

Překročení kleslo ze tří na dvě. Algoritmus ve skutečnosti způsobí, že se překročení sníží o jednu, pro jakoukoli cestu, kterou jej napájíme, protože první svislý krok začínající na úhlopříčce (v bodě označeném černou tečkou) je jedinečná svislá hrana, která pod operací přechází z úhlopříčky pod ni; všechny ostatní svislé okraje zůstávají na stejné straně úhlopříčky.

Obrázek 4. Všechny monotónní cesty v mřížce 3 × 3, ilustrující algoritmus snižování překročení.

Není také těžké pochopit, že tento proces je reverzibilní: vzhledem k jakékoli cestě P jehož překročení je menší než n, existuje přesně jedna cesta, která vede P když se na něj použije algoritmus. Ve skutečnosti (černý) okraj X, který byl původně prvním horizontálním krokem končícím na úhlopříčce, se stal poslední horizontální krok začíná na úhlopříčce.

To znamená, že počet cest překročení n se rovná počtu cest překročení n - 1, což se rovná počtu cest překročení n - 2 a tak dále, až na nulu. Jinými slovy, rozdělili jsme soubor Všechno monotónní cesty do n + 1 stejně velkých tříd, což odpovídá možnému překročení mezi 0 a n. Protože tam jsou

${ displaystyle {2n vyberte n}}$

monotónní cesty, získáme požadovaný vzorec

${ displaystyle C_ {n} = { frac {1} {n + 1}} {2n vyberte n}.}$

Obrázek 4 ilustruje situaci pron = 3. Každá z 20 možných monotónních cest se objeví někde v tabulce. První sloupec zobrazuje všechny cesty překročení tři, které leží zcela nad úhlopříčkou. Sloupce vpravo ukazují výsledek po sobě jdoucích aplikací algoritmu, přičemž překročení klesá po jedné jednotce. Existuje pět řádků, to znamená,C₃ = 5.

Čtvrtý důkaz

Tento důkaz používá definici triangulace katalánských čísel k vytvoření vztahu mezi C_n a C_n+1. Vzhledem k mnohoúhelníku P s n + 2 strany, nejprve označte jednu z jeho stran jako základnu. Li P je poté triangulován, můžeme dále vybrat a orientovat jednu z jejích 2n + 1 hran. Existují (4n + 2)C_n takové zdobené triangulace. Nyní dostal mnohoúhelník Q s n + 3 strany, znovu označte jednu z jeho stran jako základnu. Li Q je trojúhelníková, můžeme dále označit jednu ze stran kromě základní. Existují (n + 2)C_n + 1 takové zdobené triangulace. Pak existuje jednoduchá bijekce mezi těmito dvěma druhy zdobených triangulací: Trojúhelník můžeme buď sbalit dovnitř Q jehož strana je označena, nebo naopak zvětšit orientovanou hranu dovnitř P na trojúhelník a označit jeho novou stranu. Tím pádem

${ displaystyle (4n + 2) C_ {n} = (n + 2) C_ {n + 1}.}$

Binomický vzorec pro C_n vyplývá okamžitě z tohoto vztahu a počáteční podmínkyC₁ = 1.

Pátý důkaz

Tento důkaz je založen na Dyckova slova interpretace katalánských čísel, tak C_n je počet způsobů, jak se správně shodovat n dvojice závorek. Označíme (případně prázdný) opravit řetězec s C a jeho inverzní (kde jsou „[“ a „]“ vyměněny) s C⁺. Protože jakýkoli C lze jednoznačně rozložit na C = [ C₁ ] C₂, shrnutí možných míst k umístění závorky okamžitě dává rekurzivní definici

${ displaystyle C_ {0} = 1 quad { text {a}} quad C_ {n + 1} = součet _ {i = 0} ^ {n} C_ {i} , C_ {ni} quad { text {for}} n geq 0.}$

Tak teď b stát za vyrovnaný řetězec délky 2n—To znamená, že obsahuje stejný počet „[“ a „]“ - a ${ displaystyle textstyle B_ {n} = {2n zvolit n} = d_ {n} C_ {n}}$ s určitým faktorem d_n ≥ 1. Jak je uvedeno výše, libovolný vyvážený řetězec lze jednoznačně rozložit na jeden [C ] b nebo]C⁺ [ b, tak

${ displaystyle B_ {n + 1} = 2 součet _ {i = 0} ^ {n} B_ {i} C_ {n-i}.}$

Jakýkoli nesprávný vyvážený řetězec začíná na C ], tak

${ displaystyle B_ {n + 1} -C_ {n + 1} = součet _ {i = 0} ^ {n} {2i + 1 zvolit i} C_ {ni} = součet _ {i = 0} ^ {n} { frac {2i + 1} {i + 1}} B_ {i} C_ {ni}.}$

Odečtení výše uvedených rovnic a použití B_i = d_i C_i dává

${ displaystyle C_ {n + 1} = 2 součet _ {i = 0} ^ {n} d_ {i} C_ {i} C_ {ni} - součet _ {i = 0} ^ {n} { frac {2i + 1} {i + 1}} d_ {i} C_ {i} C_ {ni} = sum _ {i = 0} ^ {n} { frac {d_ {i}} {i + 1 }} C_ {i} C_ {ni}.}$

Porovnání koeficientů s původním vzorcem rekurze pro C_n dává d_i = i + 1, takže

${ displaystyle C_ {n} = { frac {1} {n + 1}} {2n vyberte n}.}$

Šestý důkaz

Tento jednoduchý důkaz^[12] je také založen na Dyckova slova interpretace katalánských čísel, ale používá krásný cyklus Lemma od Dvoretzky a Motzkin.^[13]Zavolejte sekvenci X a Y. dominující pokud, při čtení zleva doprava, nerovnováha je vždy kladné, to znamená, že počet X je vždy přísně větší než počet Y. Cycle Lemma tvrdí, že jakákoli sekvence ${ displaystyle m}$ X a ${ displaystyle n}$ Y, kde ${ displaystyle m> n}$, má přesně ${ displaystyle m-n}$ dominující cyklické permutace. Chcete-li to vidět, jednoduše uspořádejte danou posloupnost ${ displaystyle m + n}$ X a Y jsou v kruhu a opakovaně odstraňují sousední páry XY, dokud pouze ${ displaystyle m-n}$ X zůstávají. Každá z těchto X byla začátkem dominující cyklické permutace, než bylo cokoli odstraněno ${ displaystyle m = n + 1}$, existuje právě jedna dominující cyklická permutace. Odstranění úvodního X z něj (dominující sekvence musí začínat X) zanechává Dyckovu sekvenci. Protože tam jsou ${ displaystyle C_ {n} = { frac {1} {2n + 1}} {2n + 1 zvolit n} = { frac {1} {n + 1}} {2n zvolit n}}$ odlišné cykly ${ displaystyle n + 1}$ X a ${ displaystyle n}$ Y, z nichž každý odpovídá přesně jedné Dyckově sekvenci, ${ displaystyle C_ {n}}$ počítá Dyckovy sekvence.

Hankelova matice

The n×n Hankelova matice jehož (i, j) položka je katalánské číslo C_i+j−2 má určující 1, bez ohledu na hodnotu n. Například pro n = 4 máme

${ displaystyle det { begin {bmatrix} 1 & 1 & 2 & 5 1 & 2 & 5 & 14 2 & 5 & 14 & 42 5 & 14 & 42 & 132 end {bmatrix}} = 1.}$

Navíc, pokud je indexování „posunuto“ tak, aby (i, j) položka je vyplněna katalánským číslem C_i+j−1 pak je determinant stále 1, bez ohledu na hodnotu nNapříklad pro n = 4 máme

${ displaystyle det { begin {bmatrix} 1 & 2 & 5 & 14 2 & 5 & 14 & 42 5 & 14 & 42 & 132 14 & 42 & 132 & 429 end {bmatrix}} = 1.}$

Dohromady tyto dvě podmínky jednoznačně definují katalánská čísla.

Dějiny

Katalánská čísla v Mingantuově knize Rychlá metoda pro získání přesného poměru dělení kruhu svazek III

Katalánskou sekvenci popsal v 18. století Leonhard Euler, kterého zajímalo množství různých způsobů rozdělení polygonu na trojúhelníky. Sekvence je pojmenována po Eugène Charles Catalan, který objevil souvislost s výrazy v závorkách během svého zkoumání Věže Hanoje hádanka. Trik pro počítání slov Dyck našel Désiré André v roce 1887.

V roce 1988 vyšlo najevo, že katalánská číselná řada byla použita Čína mongolský matematik Mingantu do roku 1730.^[14][15] Tehdy začal psát svou knihu Ge Yuan Mi Lu Jie Fa [Rychlá metoda pro získání přesného poměru dělení kruhu], kterou dokončil jeho student Chen Jixin v roce 1774, ale publikoval o šedesát let později. Peter J. Larcombe (1999) načrtl některé rysy práce Mingantu, včetně podnětu Pierra Jartouxe, který na počátku 17. století přinesl do Číny tři nekonečné série.

Například Ming použil katalánskou sekvenci k vyjádření řady expanzí hříchu (2α) a hříchu (4α), pokud jde o hřích (α).

Zobecnění

Sekvence dvou parametrů nezáporných celých čísel ${ displaystyle { frac {(2m)! (2n)!} {(m + n)! m! n!}}}$je zevšeobecnění katalánských čísel. Tito jsou pojmenovaní superkatalánská číslatím, že Ira Gessel. Tato čísla by neměla být zaměňována s Schröder – Hipparchusova čísla, kterým se někdy také říká superkatalánská čísla.

Pro ${ displaystyle m = 1}$, to je jen dvojnásobek běžných katalánských čísel, a pro ${ displaystyle m = n}$, čísla mají snadný kombinatorický popis. Jiné kombinatorické popisy jsou však známé pouze^[16]pro ${ displaystyle m = 2,3}$ a ${ displaystyle 4}$,^[17]a je otevřeným problémem najít obecnou kombinatorickou interpretaci.

Sergej Fomin a Nathan Reading dali zevšeobecněné katalánské číslo spojené s jakoukoli konečnou krystalografikou Skupina coxeterů, jmenovitě počet plně komutativních prvků skupiny; pokud jde o přidružené kořenový systém, je to počet antiřetězců (nebo ideálních řádů) v posetu pozitivních kořenů. Klasické katalánské číslo ${ displaystyle C_ {n}}$ odpovídá kořenovému systému typu ${ displaystyle A_ {n}}$. Klasická relace opakování se zobecňuje: katalánské číslo Coxeterova diagramu se rovná součtu katalánských čísel všech jeho maximálních správných dílčích diagramů.^[18]

Viz také

Poznámky

Reference

• Stanley, Richard P. (2015), Katalánská čísla. Cambridge University Press, ISBN  978-1-107-42774-7.
• Conway a Chlap (1996) Kniha čísel. New York: Copernicus, s. 96–106.
• Gardner, Martin (1988), Cestování v čase a další matematické zmatky, New York: W.H. Freeman and Company, str.253–266 (kap. 20), ISBN  0-7167-1924-X
• Koshy, Thomas (2008), Katalánská čísla s aplikacemi, Oxford University Press, ISBN  978-0-19-533454-8
• Koshy, Thomas & Zhenguang Gao (2011) „Některé vlastnosti dělitelnosti katalánských čísel“, Matematický věstník 95:96–102.
• Larcombe, P.J. (1999). „Čínský objev katalánských čísel z 18. století“ (PDF). Matematické spektrum. 32: 5–7.
• Stanley, Richard P. (1999), Enumerativní kombinatorika. Sv. 2, Cambridge studia pokročilé matematiky, 62, Cambridge University Press, ISBN  978-0-521-56069-6, PAN  1676282
• Egecioglu, Omer (2009), Hodnocení determinantu Katalánsko-Hankel (PDF)
• Gheorghiciuc, Irina; Orelowitz, Gidon (2020), Superkatalánská čísla třetího a čtvrtého druhu, arXiv:2008.00133

externí odkazy

• Stanley, Richard P. (1998), Katalánský dodatek k enumerativní kombinatorice, svazek 2 (PDF)
• Weisstein, Eric W. "Katalánské číslo". MathWorld.
• Dickau, Robert M .: Katalánská čísla Další příklady.
• Davis, Tom: Katalánská čísla. Ještě více příkladů.
• „Ekvivalence tří katalánských interpretací čísel“ z projektu Demonstrace Wolfram [1]
• Učební materiály související s Číselné trojúhelníky spojené s oddíly na Wikiversity