Twierdzenie o wyliczeniu z etykietą

W matematyce kombinatorycznej twierdzenie o wyliczeniu z etykietą jest odpowiednikiem twierdzenia o wyliczeniu Pólya dla przypadku z etykietą, w którym mamy zbiór oznaczonych obiektów danych przez wykładniczą funkcję generującą (EGF) g ( z ), które są rozłożone na n szczelinach i grupa permutacji G , która permutuje szczeliny, tworząc w ten sposób klasy równoważności konfiguracji. Istnieje specjalna operacja ponownego etykietowania, która ponownie oznacza obiekty w gniazdach, przypisując etykiety od 1 do k , gdzie k jest całkowitą liczbą węzłów, czyli sumą liczby węzłów poszczególnych obiektów. EFG liczby różnych konfiguracji w ramach tego procesu ponownego etykietowania jest podany przez ${\ displaystyle f_ {n} (z)}$

${\ Displaystyle f_ {n} (z) = {\ Frac {g (z) ^ {n}} {| G |}}.}$

W szczególności, jeśli G jest grupą symetryczną rzędu n (stąd | sol | = n !), funkcje można dodatkowo połączyć w jedną funkcję generującą ${\ displaystyle f_ {n} (z)}$ :

${\ Displaystyle F (z, t) = \ suma _ {n = 0} ^ {\ infty} f_ {n} (z) t ^ {n} = \ suma _ {n =0}^{\infty}}{\frac {g(z)^{n}}{n!}}t^{n}=e^{g(z)t}}$

który jest wykładniczy ze zmienną z i zwykły ze zmienną t .

Proces ponownego etykietowania

Zestaw cykli jest ponownie oznaczany w celu utworzenia permutacji. (Są trzy gniazda i ${\ displaystyle G = S_ {3}}$ .)

$rozmiarze$ że obiekt o ${\ Displaystyle | \ omega |}$ reprezentowane przez ${\ Displaystyle Z ^ {|\ omega |}/|\ omega |!}$ zawiera ${\ displaystyle |\ omega |= m}$ oznaczone węzły wewnętrzne, z etykietami od 1 do m . Akcja G na szczelinach jest znacznie uproszczona w porównaniu z przypadkiem nieoznaczonym, ponieważ etykiety rozróżniają obiekty w szczelinach, a orbity pod literą G mają ten sam rozmiar ${\ Displaystyle | G |}$ . (EGF g ( z ) może nie zawierać obiektów o rozmiarze zero. Dzieje się tak, ponieważ nie są one rozróżniane za pomocą etykiet, a zatem obecność dwóch lub więcej takich obiektów tworzy orbity, których rozmiar jest mniejszy niż | G | { $G |}$ .) Jak wspomniano, węzły obiektów są ponownie etykietowane, gdy są umieszczane w gniazdach. Powiedzmy, $drugiego gniazda i tak dalej$ obiekt o rozmiarze $trafia do$ gniazda, obiekt o rozmiarze a całkowity rozmiar konfiguracja to k , więc

${\ displaystyle r_ {1} + r_ {2} + \ cdots + r_ {n} = k.}$

Proces ponownego etykietowania działa w następujący sposób: wybierz jedną z nich

${\ Displaystyle {k \ wybierz r_ {1}, r_ {2}, \ ldots r_ {n}}}$

podziały zbioru k etykiet na podzbiory o rozmiarze ${\ displaystyle r_ {1}, r_ {2}, \ ldots r_ {n}.}$ Teraz ponownie oznacz wewnętrzne węzły każdego obiektu, używając etykiet z odpowiedniego podzbioru, zachowując kolejność etykiet. Np. jeśli pierwszy obiekt zawiera cztery węzły oznaczone od 1 do 4, a zestaw etykiet wybranych dla tego obiektu to {2, 5, 6, 10}, to węzeł 1 otrzymuje etykietę 2, węzeł 2, etykietę 5, węzeł 3 , etykieta 6 i węzeł 4, etykieta 10. W ten sposób etykiety na obiektach indukują unikalne etykietowanie przy użyciu etykiet z podzbioru ${\ Displaystyle [k]}$ wybrany dla obiektu.

Dowód twierdzenia

Z przeetykietowania konstrukcji wynika, że ​​są

${\ Displaystyle {\ Frac {1} {| G|}} \ suma _ {r_ {1} + r_ {2} + \ ldots + r_ {n} = k} \wybierz r_{1},r_{2},\ldots r_{n}}\;r_{1}![z^{r_{1}}]g(z)\;r_{2}![z^ {r_{2}}]g(z)\;\cdots \;r_{n}![z^{r_{n}}]g(z)}$

Lub

${\ Displaystyle {\ Frac {k!}} {| G |}} \ suma _ {r_ {1} + r_ {2} + \ ldots + r_ {n} = k} [z ^{r_{1}}]g(z)[z^{r_{2}}]g(z)\cdots [z^{r_{n}}]g(z)\;=\;{\frac {k!}{|G|}}[z^{k}]g(z)^{n}}$

różne konfiguracje o łącznej wielkości k . Formuła daje liczbę całkowitą , ponieważ $wynosi$ k < n nie obejmuje rozmiar zero) i kiedy ${\ displaystyle k \ geq n}$ mamy ${\ displaystyle n! | k!}$ i kolejność ${\ Displaystyle | G|}$ z G dzieli rząd ${\ displaystyle S_ {n}}$ , czyli ${\ displaystyle n!}$ , przez twierdzenie Lagrange'a. Wniosek jest taki, że EGF oznaczonych konfiguracji jest podany przez

${\ Displaystyle f_ {n} (z) = \ suma _ {k \ geq 0} \ lewo ({\ Frac {k!} {| G |}} [z ^ {k}] g (z) ^ {n }\right){\frac {z^{k}}{k!}}={\frac {1}{|G|}}\sum _{k\geq 0}z^{k}[z^{ k}]g(z)^{n}={\frac {g(z)^{n}}{|G|}}.}$

Formułę tę można również uzyskać wyliczając sekwencje, czyli przypadek, gdy sloty nie są permutowane, i używając powyższego argumentu bez ${\ Displaystyle 1/| G|}$ -czynnik pokazujący, że ich funkcja generująca w przypadku ponownego etykietowania jest dana przez ${\ Displaystyle g (z) ^ {n}}$ . Na koniec zauważ, że każda sekwencja należy do orbity o rozmiarze ${\ Displaystyle | G|}$ , stąd funkcja generująca orbity jest określona przez ${\ Displaystyle g (z) ^ {n} /| G |.}$

• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire desstructures arborescentes , LaCIM, Montréal (1994). Wersja angielska: Gatunki kombinatoryczne i struktury podobne do drzew , Cambridge University Press (1998).