Klasa kombinatoryczna

Klasą kombinatoryczną nazywamy parę A = (A,|.|) taką, że A jest zbiorem niepustym zaś ${\displaystyle |\cdot |:A\rightarrow \mathbf {N} }$ jest funkcją ze zbioru A w zbiór liczb naturalnych taka, że dla każdej liczby naturalnej n zbiór {a ∈ A: |a| = n} jest skończony.

Liczbę |a| interpretujemy jako wagę lub rozmiar elementu a. Zbiór A nazywamy uniwersum klasy A. Klasy kombinatoryczne są podstawowymi obiektami Kombinatoryki Analitycznej.

Dwie klasy (A,|.|) i (B,[.]) są izomorficzne, jeśli istnieje bijekcja f:A → B taka, że dla każdego a ∈ A mamy |a| = [f(a)].

Niech A = (A,| . |) będzie klasą kombinatoryczną. Wprowadzamy oznaczenia:

1. A_n = {a ∈ A:|a|=n}
2. a_n = |A_n|
3. A(z) = ${\displaystyle \sum _{k=0}^{\infty }a_{k}z^{k}$
4. [zⁿ]A(z) = a_n

Szereg potęgowy A(z) nazywamy funkcją tworzącą klasy kombinatorycznej A.

Jeśli klasy A i B są izomorficzne, to A(z) = B(z).

1. Niech E = ({e},|.|), gdzie |e| = 0. Wtedy E(z) = 1.
2. Niech Z = ({a},|.|), gdzie |a| = 1. Wtedy Z(z) = z.
3. Niech N oznacza zbiór liczb naturalnych oraz niech N = (N,id), gdzie id oznacza identyczność na zbiorze liczb naturalnych. Wtedy

${\displaystyle N(z)=\sum _{k=0}^{\infty }z^{k}={\frac {1}{1-z}.}$

4. Niech X będzie zbiorem mocy n oraz niech P(X) będzie zbiorem potęgowym zbioru X. Rozważamy klasę P = (P(X),|.|), gdzie |A| oznacza moc zbioru A. Wtedy

${\displaystyle P(z)=\sum _{k=0}^{n}{\binom {n}{k}z^{k}=(1+z)^{n}.}$

Niech ${\displaystyle {\mathcal {A}=(A,|\cdot |_{A}),}$ ${\displaystyle {\mathcal {B}=(B,|\cdot |_{B})}$ będą klasami kombinatorycznymi.

Jeśli ${\displaystyle A\cap B=\emptyset }$ to ich sumę definiujemy jako klasę ${\displaystyle {\mathcal {A}+{\mathcal {B}=(A\cup B,|\cdot |_{A}\cup |\cdot |_{B}).}$

Twierdzenie: ${\displaystyle ({\mathcal {A}+{\mathcal {B})(z)={\mathcal {A}(z)+{\mathcal {B}(z)}$

Przykład: Rozważamy klasę A z uniwersum A = {ε, •, ♦, ♣, ♥} taką, że |ε| = 0, |•| = |♦|=1 i |♣| = |♥|=2.

Wtedy A(z) = {ε}(z) + {•}(z) + {♦}(z) + {♣}(z) + {♥}(z) = 1 + 2z + 2z².

Produktem klas ${\displaystyle {\mathcal {A}$ i ${\displaystyle {\mathcal {B}$ nazywamy klasę ${\displaystyle {\mathcal {A}\times {\mathcal {B}=(A\times B,|\cdot |),}$ gdzie |(a,b)| = |a|_A+|b|_B.

Twierdzenie: ${\displaystyle ({\mathcal {A}\times {\mathcal {B})(z)={\mathcal {A}(z)\cdot {\mathcal {B}(z)}$

gdzie ${\displaystyle A(z)\cdot B(z)}$ oznacza iloczyn Cauchy’ego szeregów.

Załóżmy, że a₀ = 0. Klasą ciągów skończonych elementów klasy A nazywamy klasę

${\displaystyle \mathrm {SEQ} ({\mathcal {A})=E\cup A\cup (A\times A)\cup (A\times A\times A)\cup \ldots }$

Twierdzenie: ${\displaystyle \mathrm {SEQ} ({\mathcal {A})(z)={\frac {1}{1-{\mathcal {A}(z)}$

Załóżmy, że a₀ = 0. Klasą podzbiorów skończonych elementów klasy A nazywamy klasę ${\displaystyle \mathrm {SET} ({\mathcal {A})=(P_{fin}(A),|\cdot |),}$ gdzie ${\displaystyle P_{fin}(A)}$ oznacza zbiór wszystkich skończonych podzbiorów zbioru A oraz ${\displaystyle |\{a_{1},\dots ,a_{n}\}|=|a_{1}|_{A}+\ldots +|a_{n}|_{A}.}$

Twierdzenie: ${\displaystyle \mathrm {SET} ({\mathcal {A})(z)=\prod _{n=1}^{\infty }(1+z^{n})^{a_{n}$

Załóżmy, że a₀ = 0. Klasą podzbiorów skończonych elementów klasy A nazywamy klasę ${\displaystyle \mathrm {MULT} ({\mathcal {A})=(\mathrm {Mult} (A),|\cdot |),}$ gdzie ${\displaystyle \mathrm {Mult} (A)}$ oznacza zbiór wszystkich multizbiorów elementów zbioru A oraz ${\displaystyle |m|=\sum _{a\in A}m(a)|a|_{A}.}$

Twierdzenie: ${\displaystyle \mathrm {MULT} ({\mathcal {A})(z)=\prod _{n=1}^{\infty }{\frac {1}{(1-z^{n})^{a_{n}$

Przykład 1. Niech ${\displaystyle {\mathcal {A}=(\{\bullet _{1},\dots ,\bullet _{k}\},|\cdot |)}$ gdzie ${\displaystyle |\bullet _{1}|=\ldots =|\bullet _{k}|=1.}$ Niech ${\displaystyle {\mathcal {B}=\mathrm {MULT} ({\mathcal {A}).}$ Wtedy ${\displaystyle {\mathcal {B}(z)={\frac {1}{(1-z)^{k},}$ więc

${\displaystyle {\begin{aligned}{\mathcal {B}(z)&=(1-z)^{-k}\\&=\sum _{n\geq 0}{\binom {-k}{n}(-1)^{n}z^{n}\\&=\sum _{n\geq 0}{\binom {n+k-1}{n}z^{n}\\&=\sum _{n\geq 0}{\binom {n+k-1}{k-1}z^{n}\end{aligned}$

zatem ${\displaystyle [z^{n}]{\mathcal {B}(z)={\binom {n+k-1}{k-1}.}$ Otrzymaliśmy wzór na liczbę multizbiorów rozmiaru n podzbioru k-elementowego.

Przykład 2. Niech T oznacza klasę drzew planarnych. Niech • oznacza wierzchołek drzewa. Wtedy T ≈ {•} × SEQ(T), więc T(z) = z/(1-T(z)), z czego wnioskujemy, że

${\displaystyle T(z)={\frac {1}{2}\left(1-{\sqrt {1-4z}\right).}$

Po kilkunastu algebraicznych przekształceniach otrzymujemy ${\displaystyle [z^{n}]T(z)={\frac {1}{n}{\binom {2(n-1)}{n-1},}$ więc [zⁿ]T(z) = C_n-1, gdzie C_n oznacza n-tą liczbę Catalana.

• Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009. Brak numerów stron w książce

• Analytic Combinatorics (online)