Klasa kombinatoryczna

Klasą kombinatoryczną nazywamy parę A = (A,|.|) taką, że A jest zbiorem niepustym zaś $|\cdot |:A\to 𝐍$ 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}^{\mathrm{\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}^{\mathrm{\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(\genfrac{}{}{0ex}{}{n}{k})z^k=(1+z{)}^n.$

Podstawowe konstrukcje

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

Suma klas

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

Twierdzenie: $(𝒜+ℬ)(z)=𝒜(z)+ℬ(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 $𝒜$ i $ℬ$ nazywamy klasę $𝒜\times ℬ=(A\times B,|\cdot |),$ gdzie |(a,b)| = |a|_A+|b|_B.

Twierdzenie: $(𝒜\times ℬ)(z)=𝒜(z)\cdot ℬ(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{S}\mathrm{E}\mathrm{Q}(𝒜)=E\cup A\cup (A\times A)\cup (A\times A\times A)\cup \dots$

Twierdzenie: $\mathrm{S}\mathrm{E}\mathrm{Q}(𝒜)(z)=\frac{1}{1-𝒜(z)}$

Operacja podzbiorów skończonych klasy

Załóżmy, że a₀ = 0. Klasą podzbiorów skończonych elementów klasy A nazywamy klasę $\mathrm{S}\mathrm{E}\mathrm{T}(𝒜)=(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+\dots +|a_n{|}_A.$

Twierdzenie: $\mathrm{S}\mathrm{E}\mathrm{T}(𝒜)(z)=\prod _{n=1}^{\mathrm{\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{M}\mathrm{U}\mathrm{L}\mathrm{T}(𝒜)=(\mathrm{M}\mathrm{u}\mathrm{l}\mathrm{t}(A),|\cdot |),$ gdzie $\mathrm{M}\mathrm{u}\mathrm{l}\mathrm{t}(A)$ oznacza zbiór wszystkich multizbiorów elementów zbioru A oraz $|m|=\sum _{a\in A}m(a)|a{|}_A.$

Twierdzenie: $\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}(𝒜)(z)=\prod _{n=1}^{\mathrm{\infty }}\frac{1}{(1-z^n{)}^{a_n}}$

Typowe zastosowanie

Przykład 1. Niech $𝒜=(\{{\bullet }_1,\dots ,{\bullet }_k\},|\cdot |)$ gdzie $|{\bullet }_1|=\dots =|{\bullet }_k|=1.$ Niech $ℬ=\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}(𝒜).$ Wtedy $ℬ(z)=\frac{1}{(1-z{)}^k},$ więc

$\begin{array}{cc}ℬ(z)& =(1-z{)}^{-k}\\ & =\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{-k}{n})(-1{)}^n{z}^n\\ & =\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{n+k-1}{n})z^n\\ & =\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{n+k-1}{k-1})z^n\end{array}$

zatem $[z^n]ℬ(z)=(\genfrac{}{}{0ex}{}{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}(1-\sqrt{1-4z}).$

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

Bibliografia

• Szablon:Cytuj książkę

Linki zewnętrzne

• Analytic Combinatorics (online)