Kombinatoryka wyliczeniowa

Kombinatoryka wyliczeniowa to dziedzina kombinatoryki , która zajmuje się liczbą sposobów tworzenia pewnych wzorców. Dwa przykłady tego typu problemów to liczenie kombinacji i liczenie permutacji . Bardziej ogólnie, mając 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 elementów w zbiorze jest dość szerokim problemem matematycznym , wiele problemów pojawiających się w zastosowaniach ma stosunkowo prosty opis kombinatoryczny . Dwunastokrotny sposób zapewnia ujednoliconą strukturę do liczenia permutacji , kombinacji i partycji .

Najprostszymi takimi funkcjami są formuły zamknięte , które można wyrazić jako złożenie funkcji elementarnych, takich jak silnie , potęgi i tak dalej. Na przykład, jak pokazano poniżej, liczba różnych możliwych uporządkowań talii n kart wynosi f ( n ) = n !. Problem znalezienia zamkniętej formuły jest znany jako wyliczanie algebraiczne i często obejmuje wyprowadzenie relacji powtarzalności lub funkcji generującej i wykorzystanie jej do uzyskania pożądanej zamkniętej formy.

Często skomplikowana formuła zamknięta daje niewielki wgląd w zachowanie funkcji zliczającej w miarę wzrostu liczby zliczanych obiektów. W takich przypadkach preferowane może być proste asymptotyczne . sol $Displaystyle g (n)}$ \ jest asymptotycznym przybliżeniem do ${\ Displaystyle f (n)}$ ${\ Displaystyle f (n) / g (n) \ rightarrow 1}$ as ${\ Displaystyle n \ rightarrow \ infty}$ . W tym przypadku piszemy ${\ displaystyle f (n) \ sim g (n). \,}$

Funkcje generujące

Funkcje generujące służą do opisu rodzin obiektów kombinatorycznych. Niech $oznacza$ rodzinę obiektów i niech F ( x ) będzie jej funkcją generującą Następnie

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

gdzie $n$ liczbę obiektów kombinatorycznych o . Liczba obiektów kombinatorycznych o rozmiarze n jest zatem określona przez współczynnik $x ^ {n}}$ displaystyle . Teraz zostaną omówione pewne wspólne operacje na rodzinach obiektów kombinatorycznych i ich wpływ na funkcję generującą. Czasami używana jest również wykładnicza funkcja generująca . W tym przypadku miałoby to formę

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

Po określeniu funkcja generująca daje informacje podane 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, z funkcjami generującymi odpowiednio F ( x ) i G ( x ), $dwóch rodzin kombinatorycznych i$ związek tych sol $}}}$ \ displaystyle { \ mathcal { G rodziny ( $sol$ funkcję generującą fa ( x ) + ( x )

Pary

dwóch kombinatorycznych rodzin, jak powyżej, $iloczyn$ kartezjański ) dwóch rodzin ( ) ma funkcję generującą ( x ) sol ( x ).

Sekwencje

(Skończona) sekwencja uogólnia ideę pary, jak zdefiniowano powyżej. Sekwencje są dowolnymi iloczynami kartezjańskimi obiektu kombinatorycznego z samym sobą. Formalnie:

{\ Displaystyle {\ mbox {Seq}} ({\ mathcal {F}}) = \ epsilon \ \ kubek \ {\ mathcal { F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F} }\!\times \!{\mathcal {F}}\ \cup \cdots }

Ujmując powyższe 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 mogą być teraz użyte do wyliczenia typowych obiektów kombinatorycznych, w tym drzew ( binarnych i płaskich), ścieżek Dycka i cykli. Struktura kombinatoryczna składa się z atomów. Na przykład w przypadku drzew atomy byłyby węzłami. Atomy, z których składa się obiekt, mogą być oznakowane 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 płaskie

Drzewa binarne i płaskie 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 . Na ogół istnieje węzeł zwany korzeniem, który nie ma węzła nadrzędnego. W platanach 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 $.$ rodzinę wszystkich platanów Następnie tę rodzinę można rekurencyjnie zdefiniować w następujący sposób:

{\ Displaystyle {\ mathcal {P}} = \ {\ punktor \} \ razy \, {\ mbox {Seq}} ({\ mathcal {P}})}

W tym przypadku reprezentuje rodzinę obiektów składającą się $.$ To ma funkcję generującą x . Niech P ( x ) oznacza funkcję generującą ${\ displaystyle {\ mathcal {P}}}$ . 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 jednocześnie platanem. Korzystając z operacji na rodzinach struktur kombinatorycznych opracowanych wcześniej, przekłada się to na rekurencyjną funkcję generującą:

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

Po rozwiązaniu dla P ( x ):

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

Wyraźny wzór na liczbę platanów o rozmiarze n można teraz wyznaczyć, 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{wyrównane}}}

Uwaga: Zapis [ x ⁿ ] f ( x ) odnosi się do współczynnika x ⁿ w f ( x ). Rozwinięcie szeregu pierwiastka kwadratowego jest oparte na uogólnieniu twierdzenia dwumianu przez Newtona . Aby przejść od czwartej do piątej linii, potrzebne są manipulacje przy użyciu uogólnionego współczynnika dwumianu .

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

Zobacz też

Zeilberger, Doron , kombinatoryka wyliczeniowa i algebraiczna
Björner, Anders i Stanley, Richard P. , kombinatoryczna Miscellany
Graham, Ronald L. , Grötschel M. i Lovász, László , wyd. (1996). Handbook of Combinatoryics , tomy 1 i 2. Elsevier (North-Holandia), Amsterdam i MIT Press, Cambridge, Massachusetts ISBN 0-262-07169-X .
Józef, George Gheverghese (1994) [1991]. The Crest of the Peacock: pozaeuropejskie korzenie matematyki (wyd. 2). Londyn: Penguin Books . ISBN 0-14-012529-9 .
Loehr, Mikołaj A. (2011). Kombinatoryka bijekcyjna . CRC Naciśnij . ISBN 143984884X , ISBN 978-1439848845 .
Stanley, Richard P. (1997, 1999). Wyliczeniowe kombinatoryki , tomy 1 i 2 . Wydawnictwo Uniwersytetu Cambridge . ISBN 0-521-55309-1 , ISBN 0-521-56069-1 .
Goulden, Ian P. i Jackson, David M. (2004). Wyliczanie kombinatoryczne . Publikacje Dover . ISBN 0486435970 .
Riordan, Jan (1958). Wprowadzenie do analizy kombinatorycznej , Wiley & Sons, Nowy Jork (ponownie opublikowane).
Riordan, Jan (1968). Tożsamości kombinatoryczne , Wiley & Sons, Nowy Jork (ponownie opublikowane).
Wilk, Herbert S. (1994). Generowaniefunkcjonologii (wyd. 2). Boston, MA: Prasa akademicka. ISBN 0-12-751956-4 . Zbl 0831.05001 .