Klasa kombinatoryczna

W matematyce klasa kombinatoryczna jest policzalnym zbiorem obiektów matematycznych wraz z funkcją rozmiaru odwzorowującą każdy obiekt na nieujemną liczbę całkowitą, tak że istnieje skończenie wiele obiektów o każdym rozmiarze.

Liczenie ciągów i izomorfizm

Sekwencja liczenia klasy kombinatorycznej jest sekwencją liczb elementów o rozmiarze i dla i = 0, 1, 2, ...; można to również opisać jako funkcję generującą , której współczynnikami są te liczby. Sekwencje liczenia klas kombinatorycznych są głównym przedmiotem badań kombinatoryki wyliczeniowej . Mówi się, że dwie klasy kombinatoryczne są izomorficzne, jeśli mają taką samą liczbę obiektów każdego rozmiaru lub równoważnie, jeśli ich sekwencje liczenia są takie same. Często, gdy wiadomo, że dwie klasy kombinatoryczne są izomorficzne, bijektywnego dowodu tej równoważności; taki dowód można interpretować jako pokazujący, że obiekty w dwóch klasach izomorficznych są względem siebie kryptomorficzne .

Na przykład triangulacje wielokątów foremnych (o rozmiarze określonym przez liczbę boków wielokąta i ustalony wybór wielokąta do triangulacji dla każdego rozmiaru) oraz zbiór nieukorzenionych płaskich drzew binarnych (aż do izomorfizmu wykresu , ze stałym kolejność liści i rozmiar określony przez liczbę liści) są liczone liczbami katalońskimi , więc tworzą izomorficzne klasy kombinatoryczne. Izomorfizm bijektywny w tym przypadku jest określony przez dwoistość grafu planarnego : triangulację można przekształcić bijektywnie w drzewo z liściem dla każdej krawędzi wielokąta, wewnętrznym węzłem dla każdego trójkąta i krawędzią dla każdych dwóch (krawędzie wielokątów?) Lub trójkątów które sąsiadują ze sobą.

Kombinatoryka analityczna

Teoria gatunków kombinatorycznych i jej rozszerzenie na kombinatorykę analityczną dostarczają języka do opisu wielu ważnych klas kombinatorycznych, konstruowania nowych klas z kombinacji wcześniej zdefiniowanych i automatycznego wyprowadzania ich sekwencji liczenia. Na przykład dwie klasy kombinatoryczne mogą być łączone za pomocą rozłącznej sumy lub konstrukcji iloczynu kartezjańskiego , w której obiekty są uporządkowanymi parami jednego obiektu z każdej z dwóch klas, a funkcja rozmiaru jest sumą rozmiarów każdego obiektu w para. Operacje te odpowiednio tworzą operacje dodawania i mnożenia półpierścienia na rodzinie (klasy równoważności izomorfizmu) klas kombinatorycznych, w których obiektem zerowym jest pusta klasa kombinatoryczna, a jednostką jest klasa, której jedynym obiektem jest zbiór pusty .

Wzory permutacji

W badaniu wzorców permutacji kombinatoryczna klasa klas permutacji , wyliczana według długości permutacji, nazywana jest klasą Wilfa . Badanie wyliczeń określonych klas permutacji ujawniło nieoczekiwane równoważności w liczeniu sekwencji pozornie niepowiązanych klas permutacji.