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)