Klasa kombinatoryczna

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

  1. An = {a ∈ A:|a|=n}
  2. an = |An|
  3. A(z) =
  4. [zn]A(z) = an

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[edytuj | edytuj kod]

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

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

Podstawowe konstrukcje[edytuj | edytuj kod]

Niech będą klasami kombinatorycznymi.

Suma klas[edytuj | edytuj kod]

Jeśli to ich sumę definiujemy jako klasę

Twierdzenie:

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[edytuj | edytuj kod]

Produktem klas i nazywamy klasę gdzie |(a,b)| = |a|A+|b|B.

Twierdzenie:

gdzie oznacza iloczyn Cauchy’ego szeregów.

Operacja ciągów klas[edytuj | edytuj kod]

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

Twierdzenie:

Operacja podzbiorów skończonych klasy[edytuj | edytuj kod]

Załóżmy, że a0 = 0. Klasą podzbiorów skończonych elementów klasy A nazywamy klasę gdzie oznacza zbiór wszystkich skończonych podzbiorów zbioru A oraz

Twierdzenie:

Operacja multizbiorów[edytuj | edytuj kod]

Załóżmy, że a0 = 0. Klasą podzbiorów skończonych elementów klasy A nazywamy klasę gdzie oznacza zbiór wszystkich multizbiorów elementów zbioru A oraz

Twierdzenie:

Typowe zastosowanie[edytuj | edytuj kod]

Przykład 1. Niech gdzie Niech Wtedy więc

zatem 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

Po kilkunastu algebraicznych przekształceniach otrzymujemy więc [zn]T(z) = Cn-1, gdzie Cn oznacza n-tą liczbę Catalana.

Bibliografia[edytuj | edytuj kod]

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

Linki zewnętrzne[edytuj | edytuj kod]