Przesiewanie cykliczne

W matematyce kombinatorycznej przesiewanie cykliczne jest zjawiskiem, za pomocą którego ocena funkcji generującej dla skończonego zbioru u pierwiastków jedności liczy klasy symetrii obiektów, na które oddziałuje grupa cykliczna .

Definicja

Niech C będzie grupą cykliczną generowaną przez element c rzędu n . Załóżmy, że C działa na zbiorze X . Niech X ( q ) będzie wielomianem o współczynnikach całkowitych. Wtedy mówi się, że trójka ( X , X ( q ), C ) wykazuje zjawisko przesiewania cyklicznego ( CSP ), jeśli dla wszystkich liczb całkowitych d wartość X ( e ^{2 $π$ id / n} ) jest liczbą elementów ustaloną przez c ^d . W szczególności X (1) jest licznością zbioru X iz tego powodu X ( q ) jest traktowany jako funkcja generująca dla X.

Przykłady

Współczynnik dwumianowy q

{\ Displaystyle \ lewo [{n \ na szczycie k} \ prawej] _ {q}}

jest wielomianem w q określonym przez

{\ Displaystyle \ lewo [{n \ na szczycie k} \ prawo] _ {q} = {\ Frac {\ prod _ {i = 1} ^ {n} (1 + q + q ^ {2} + \ cdots + q^{i-1})}{\left(\prod _{i=1}^{k}(1+q+q^{2}+\cdots +q^{i-1})\right) \cdot \left(\prod _{i=1}^{nk}(1+q+q^{2}+\cdots +q^{i-1})\right)}}.}

Łatwo zauważyć, że jego wartość przy $=$ 1 jest zwykłym współczynnikiem dwumianowym funkcja generująca dla podzbiorów {1, 2 ..., n } o rozmiarze k . Podzbiory te wykonują naturalne działanie grupy cyklicznej C rzędu n , która działa poprzez dodanie 1 do każdego elementu zbioru, modulo n . Na przykład, gdy n = 4 i k = 2, orbity grupowe są

{\ Displaystyle \ {1,3 \} \ do \ {2,4 \} \ do \ {1,3 \}}

(o rozmiarze 2 )

I

{\ Displaystyle \ {1,2 \} \ do \ {2,3 \} \ do \{3,4\}\do \{1,4\}\do \{1,2\}}

(rozmiaru 4).

Można pokazać, że obliczenie współczynnika q -dwumianowego, gdy q jest n -tym pierwiastkiem jedności, daje liczbę podzbiorów ustalonych przez odpowiedni element grupy.

W przykładzie n = 4 i k = 2, q -współczynnik dwumianowy wynosi

{\ Displaystyle \ lewo [{4 \ na szczycie 2} \ prawo] _ {q} = 1 + q + 2q ^ {2} + q ^ {3} + q ^ {4};}

ocena tego wielomianu przy q = 1 daje 6 (ponieważ wszystkie sześć podzbiorów jest ustalonych przez element tożsamości grupy); oszacowanie go przy q = −1 daje 2 (podzbiory {1, 3} i {2, 4} są ustalane przez dwie aplikacje generatora grup); a oszacowanie go przy q = ± i daje 0 (żadne podzbiory nie są ustalane przez jedno lub trzy zastosowania generatora grup).

Lista cyklicznych zjawisk przesiewania

W dokumencie Reiner-Stanton-White podano następujący przykład:

Niech α będzie złożeniem n , a W ( α ) będzie zbiorem wszystkich słów o długości n z literami α _i równymi i . Pochodzenie słowa w to dowolny indeks j taki, że w $\ Displaystyle w_ {j}> w_ {j + 1}}$ . Zdefiniuj główny indeks ${\ Displaystyle \ operatorname {maj} (w)}$ na słowach jako sumę wszystkich zejść.

Trójka ${\ Displaystyle (X_ {n}, C_ {n-1}, {\ Frac {1} {[n +1] _ {q}}} \ lewo [{2n \ na górze n} \ prawej] _ {q})}$ wykazują cykliczne zjawisko przesiewania, gdzie ${\ Displaystyle X_ {n}}$ jest zbiorem nie- skrzyżowanie (1,2)-konfiguracje [ n − 1].

Niech λ będzie prostokątnym podziałem o rozmiarze n i niech X będzie zbiorem standardowych obrazów Younga o kształcie λ . Niech C = Z / nZ działa na X poprzez promocję. wtedy ${\ Displaystyle (X, C, {\ Frac {[n]! _ {q}} {\ prod _{(i,j)\in \lambda }[h_{ij}]_{q}}})}$ wykazują zjawisko przesiewania cyklicznego. Zauważ, że wielomian jest q -analogiem wzoru na długość haka .

Ponadto niech λ będzie prostokątnym podziałem o rozmiarze n i niech X będzie zbiorem półstandardowych obrazów Younga o kształcie λ . Niech C = Z / kZ działa na X poprzez k -promocję. wtedy $Displaystyle (X, C, q ^ {- \ kappa (\ lambda)} s_ {\lambda }(1,q,q^{2},\dotsc ,q^{k-1})}}$ wykazują zjawisko przesiewania cyklicznego. Tutaj ${\ Displaystyle \ kappa (\ lambda) = \ suma _ {i} (i-1) \ lambda _ {i}}$ i s _λ to Schur wielomian .

Rosnący obraz to półstandardowy obraz Younga, w którym zarówno wiersze, jak i kolumny rosną ściśle, a zbiór wpisów ma postać ${\ Displaystyle 1,2, \ kropka, \ ell}$ dla trochę ${\ Displaystyle \ ell}$ . Niech ${\ Displaystyle Inc_ {k} (2 \ razy n)}$ oznacza zbiór rosnącego obrazu z dwoma rzędami o długości n i maksymalnym wpisem ${\ Displaystyle 2n-k }$ . Wtedy ${\ Displaystyle (\ nazwa operatora {Inc} _ {k} (2 \ razy n), C_ {2n-k}, q ^ {n + {\ binom {k} {2}}} {\ Frac {\ lewo [{ n-1 \atop k}\right]_{q}\left[{2n-k \atop nk-1}\right]_{q}}{[nk]_{q}}})} wykazują$ cykliczność zjawisko przesiewania, w którym działa poprzez promocję K. ${2n-k}}$

Niech ${\ Displaystyle S _ {\ lambda, j}}$ będzie zbiorem permutacji typu cyklicznego λ i dokładnie j przekroczeń. Niech ${\ Displaystyle a_ {\ lambda, j} (q) = \ suma _ {\ sigma \ in S _ {\ lambda, j}} q ^ {\ operatorname {maj} (\ sigma) - \ operatorname {exc} (\ sigma)}} i niech C n {\ displaystyle C_ {$ n $działać$ na ${\ Displaystyle S _ {\ lambda, j}}$ przez koniugację.

Następnie ${\ Displaystyle (S _ {\ lambda, j}, C_ {n}, a _ {\ lambda, j} (q))$ } zjawisko przesiewania.

Uwagi i odniesienia

Sagan, Bruce (2011). „Zjawisko przesiewania cyklicznego: ankieta” . W Chapman, Robin (red.). Ankiety w kombinatoryce 2011 . Seria notatek z wykładów London Mathematical Society. Tom. 392. Cambridge University Press. s. 183–233. ISBN 978-1-139-50368-6 .