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_{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).

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 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

$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},\dots ,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},\dots ,\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

${\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 $[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)={\frac {1}{2}}\left(1-{\sqrt {1-4z}}\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 Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009.brak strony w książce

Linki zewnętrzne

• Analytic Combinatorics (online)