Wyliczeniowa kombinatoryka - Enumerative combinatorics

Kombinatoryka wyliczeniowa to obszar kombinatoryki, który zajmuje się liczbą sposobów, w jakie można tworzyć określone wzorce. Dwa przykłady tego typu problemów to liczenie kombinacji i liczenie permutacji . Mówiąc bardziej ogólnie, biorąc pod uwagę nieskończony zbiór skończonych zbiorów S _i indeksowanych przez liczby naturalne , kombinatoryka wyliczeniowa stara się opisać funkcję liczącą, która zlicza liczbę obiektów w S _n dla każdego n . Chociaż liczenie liczby elementów w zestawie jest dość szerokim problemem matematycznym , wiele problemów, które pojawiają się w zastosowaniach, ma stosunkowo prosty opis kombinatoryczny . Dwunastokrotny sposób zapewnia jednolite ramy licząc permutacji , kombinacji i partycje .

Najprostsze takie funkcje to formuły zamknięte , które można wyrazić jako zbiór funkcji elementarnych, takich jak silnia , potęga i tak dalej. Na przykład, jak pokazano poniżej, liczba różnych możliwych kolejności w talii n kart wynosi f ( n ) = n ! Problem znalezienia formuły zamkniętej jest znany jako wyliczenie algebraiczne i często polega na wyprowadzeniu relacji rekurencji lub generowaniu funkcji i wykorzystaniu jej do uzyskania pożądanej postaci zamkniętej.

Często skomplikowana, zamknięta formuła daje niewielki wgląd w zachowanie funkcji liczącej wraz ze wzrostem liczby zliczanych obiektów. W takich przypadkach preferowane może być proste przybliżenie asymptotyczne . Funkcja jest asymptotycznym przybliżeniem, jeśli jest jak . W takim przypadku piszemy ${\ displaystyle g (n)}$${\ displaystyle f (n)}$${\ Displaystyle f (n) / g (n) \ rightarrow 1}$${\ displaystyle n \ rightarrow \ infty}$${\ Displaystyle f (n) \ sim g (n). \,}$

Funkcje generujące

Funkcje generujące służą do opisywania rodzin obiektów kombinatorycznych. Pozwolić oznacza rodzinę obiektów i niech F ( x ) będzie jego funkcja generowania. Następnie ${\ displaystyle {\ mathcal {F}}}$

${\ Displaystyle F (x) = \ suma _ {n = 0} ^ {\ infty} f_ {n} x ^ {n}}$

gdzie oznacza liczbę kombinatorycznych obiektów o rozmiarze n . Liczba obiektów kombinatorycznych o rozmiarze n jest zatem określona przez współczynnik . Zostaną teraz opracowane pewne wspólne operacje na rodzinach obiektów kombinatorycznych i ich wpływ na funkcję generującą. Czasami używana jest również funkcja generowania wykładniczego. W tym przypadku miałby on postać ${\ displaystyle f_ {n}}$${\ displaystyle x ^ {n}}$

${\ Displaystyle F (x) = \ suma _ {n = 0} ^ {\ infty} f_ {n} {\ Frac {x ^ {n}} {n!}}}$

Po ustaleniu funkcja generująca dostarcza informacji podanych w poprzednich podejściach. Ponadto różne naturalne operacje na funkcjach generujących, takie jak dodawanie, mnożenie, różniczkowanie itp., Mają znaczenie kombinatoryczne; pozwala to na rozszerzenie wyników z jednego problemu kombinatorycznego w celu rozwiązania innych.

Unia

Biorąc pod uwagę dwie rodziny kombinatoryczne i funkcje generujące odpowiednio F ( x ) i G ( x ), rozłączny związek dwóch rodzin ( ) ma funkcję generującą F ( x ) + G ( x ). ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle {\ mathcal {G}}}$${\ displaystyle {\ mathcal {F}} \ cup {\ mathcal {G}}}$

Pary

Dla dwóch rodzin kombinatorycznych, jak powyżej, iloczyn kartezjański (para) dwóch rodzin ( ) ma funkcję generującą F ( x ) G ( x ). ${\ displaystyle {\ mathcal {F}} \ razy {\ mathcal {G}}}$

Sekwencje

Sekwencja uogólnia ideę pary, jak zdefiniowano powyżej. Sekwencje są dowolnymi iloczynami kartezjańskimi obiektu kombinatorycznego ze sobą. Formalnie:

${\ Displaystyle {\ mbox {Seq}} ({\ mathcal {F}}) = \ epsilon \ \ cup \ {\ mathcal {F}} \ \ cup \ {\ mathcal {F}} \ razy {\ mathcal { F}} \ \ cup \ {\ mathcal {F}} \ times {\ mathcal {F}} \ times {\ mathcal {F}} \ \ cup \ cdots}$

Ujmując to słowami: Pusta sekwencja lub sekwencja jednego elementu lub sekwencja dwóch elementów lub sekwencja trzech elementów itd. Funkcja generująca wyglądałaby następująco:

${\ Displaystyle 1 + F (x) + [F (x)] ^ {2} + [F (x)] ^ {3} + \ cdots = {\ Frac {1} {1-F (x)}} }$

Struktury kombinatoryczne

Powyższe operacje można teraz wykorzystać do wyliczenia typowych obiektów kombinatorycznych, w tym drzew (binarnych i płaskich), ścieżek i cykli Dycka . Struktura kombinatoryczna składa się z atomów. Na przykład w przypadku drzew atomy byłyby węzłami. Atomy, które składają się na obiekt, mogą być oznaczone lub nie. Atomy nieoznaczone są nie do odróżnienia od siebie, podczas gdy atomy oznaczone są różne. Dlatego w przypadku obiektu kombinatorycznego składającego się z oznaczonych atomów, nowy obiekt można utworzyć, po prostu zamieniając dwa lub więcej atomów.

Drzewa binarne i platany

Drzewa binarne i platany są przykładami nieoznaczonej struktury kombinatorycznej. Drzewa składają się z węzłów połączonych krawędziami w taki sposób, że nie ma cykli. Zwykle istnieje węzeł zwany korzeniem, który nie ma węzła nadrzędnego. W drzewach Plane każdy węzeł może mieć dowolną liczbę dzieci. W drzewach binarnych, szczególnym przypadku platanów, każdy węzeł może mieć dwoje dzieci lub nie mieć ich wcale. Niech oznacza rodzinę wszystkich platanów. Następnie tę rodzinę można zdefiniować rekurencyjnie w następujący sposób: ${\ displaystyle {\ mathcal {P}}}$

${\ Displaystyle {\ mathcal {P}} = \ {\ bullet \} \ razy {\ mbox {Seq}} ({\ mathcal {P}})}$

W tym przypadku reprezentuje rodzinę obiektów składającą się z jednego węzła. Ma to funkcję generującą x . Niech P ( x ) oznacza funkcję generującą . Ujmując powyższy opis słowami: platan składa się z węzła, do którego dołączona jest dowolna liczba poddrzew, z których każde jest również platanem. Użycie operacji na rodzinach struktur kombinatorycznych opracowanych wcześniej przekłada się na rekurencyjną funkcję generującą: ${\ displaystyle \ {\ bullet \}}$${\ displaystyle {\ mathcal {P}}}$

${\ Displaystyle P (x) = x {\ Frac {1} {1-P (x)}}}$

Po rozwiązaniu P ( x ):

${\ Displaystyle P (x) = {\ Frac {1 - {\ sqrt {1-4x}}} {2}}}$

Można teraz określić jednoznaczny wzór na liczbę platanów o rozmiarze n, wyodrębniając współczynnik x ⁿ .

${\ Displaystyle {\ rozpocząć {wyrównane} p_ {n} & = [x ^ {n}] P (x) = [x ^ {n}] {\ Frac {1 - {\ sqrt {1-4x}}} {2}} \\ [6pt] & = [x ^ {n}] {\ frac {1} {2}} - [x ^ {n}] {\ frac {1} {2}} {\ sqrt { 1-4x}} \\ [6pt] & = - {\ frac {1} {2}} [x ^ {n}] \ sum _ {k = 0} ^ {\ infty} {{\ frac {1} {2}} \ choose k} (- 4x) ^ {k} \\ [6pt] & = - {\ frac {1} {2}} {{\ frac {1} {2}} \ choose n} ( -4) ^ {n} \\ [6pt] & = {\ frac {1} {n}} {2n-2 \ choose n-1} \ end {aligned}}}$

Uwaga: notacja [ x ⁿ ] f ( x ) odnosi się do współczynnika x ⁿ we f ( x ). Szeregowe rozwinięcie pierwiastka kwadratowego jest oparte na uogólnieniu Newtona twierdzenia o dwumianach . Aby przejść od czwartej do piątej linii, potrzebne są manipulacje przy użyciu uogólnionego współczynnika dwumianowego .

Wyrażenie w ostatnim wierszu jest równe ( n  - 1) ^tej liczbie katalońskiej . Dlatego p _n = c _{n −1} .

Zobacz też

Bibliografia

• Zeilberger, Doron , Enumerative and Algebraic Combinatorics
• Björner, Anders i Stanley, Richard P. , Różne kombinatory
• Graham, Ronald L. , Grötschel M. i Lovász, László , red. (1996). Handbook of Combinatorics , tomy 1 i 2. Elsevier (Holandia Północna), Amsterdam oraz MIT Press, Cambridge, Mass. ISBN   0-262-07169-X .
• Joseph, George Gheverghese (1994) [1991]. The Crest of the Peacock: Non-European Roots of Mathematics (2nd ed.). Londyn: Penguin Books . ISBN   0-14-012529-9 .
• Loehr, Nicholas A. (2011). Kombinatoryka bijektywna . CRC Press . ISBN   143984884X , ISBN   978-1439848845 .
• Stanley, Richard P. (1997, 1999). Enumerative Combinatorics , Tomy 1 i 2 . Cambridge University Press . ISBN   0-521-55309-1 , ISBN   0-521-56069-1 .
• Goulden, Ian P. i Jackson, David M. (2004). Wyliczenie kombinatoryczne . Publikacje Dover . ISBN   0486435970 .
• Analiza kombinatoryczna - artykuł w Encyclopædia Britannica, wydanie jedenaste
• Riordan, John (1958). An Introduction to Combinatorial Analysis , Wiley & Sons, Nowy Jork (publikacja wznowiona).
• Riordan, John (1968). Combinatorial Identities , Wiley & Sons, New York (wznowiona).
• Wilf, Herbert S. (1994). Generująca funkcjonologia (wyd. 2). Boston, MA: Academic Press. ISBN   0-12-751956-4 . Zbl   0831.05001 .