Klasa kombinatoryczna

Klasą kombinatoryczną nazywamy parę A = (A,|.|) taką, że A jest zbiorem niepustym zaś $|\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)].

Podstawowe definicje

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

1. A_n = {a ∈ A:|a|=n}
2. a_n = |A_n|
3. A(z) = $\sum_{k=0}^{\infty} a_n z^n$
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).

Podstawowe przykłady

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

$N(z) = \sum_{k=0}^\infty z^k = \frac{1}{1-z}$

4. Niech X bedzie 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

$P(z) = \sum_{k=0}^n \binom{n}{k}z^k = (1+z)^n$

Podstawowe konstrukcje

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

Suma klas

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

Twierdzenie: $(\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².

Produkt klas

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

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

gdzie $A(z)\cdot B(z)$ oznacza iloczyn Cauchy'ego szeregów.

Operacja ciągów klas

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

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

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

Operacja podzbiorów skończonych klasy

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

Twierdzenie: $\mathrm{SET}(\mathcal{A}) (z) = \prod_{n=1}^{\infty}(1+z^n)^{a_n}$

Operacja multizbiorów

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

Twierdzenie: $\mathrm{MULT}(\mathcal{A}) (z) = \prod_{n=1}^{\infty}\frac{1}{(1-z^n)^{a_n}}$

Typowe zastosowanie

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

$\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}(-1)^n z^n = \sum_{n\geq 0}\binom{n+k-1}{k-1}(-1)^n z^n$

zatem $[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

$T(z) = \frac12 \left(1-\sqrt{1-4 z}\right)$

Po kilkunastu algebraicznych przekształceniach otrzymujemy $[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.

Bibliografia

Philippe Flajolet, Robert Sadgewick: Analytic Combinatorics. Cambridge University Press, 2009. 

Linki zewnętrzne

• Analytic Combinatorics (online)