Orbits group action o:G×X→X orbit ofx:G={πox|π∈G equivalent class of configuration x X/G={Gx|x∈X} our goal::countX/G到
0 1 2 3 4 5 0 1 2 3 4 5 group action : G ⇥ X ! X Orbits orbit of x : Gx = {⇡ x | ⇡ 2 G} equivalent class of configuration x X/G = {Gx | x 2 X} our goal: count |X/G|
X=2]m G=Cn X/G: =Dn X/G:
X = [2][n] G = Cn G = Dn X/G : X/G :
configuration x [n][m] 2×O 4×O a(2,4)=3 i=(n1,n2,.,nm) S.t.n1+n2+·+nm=m a元：#of config.(up to symmetry）with ni many color i pattern inventory (multi-variate)generating function Fc(y1,2,.,ym)= ∑ aay1y22.…ymm d=(n1,,nm) n1+··十nm=n
2 × 4 × configuration x : [n] ! [m] ~ v = (n1, n2,...,nm) a~ v : # of config. (up to symmetry) with ni many color i n1 + n2 + ··· + nm = n pattern inventory : FG(y1, y2,...,ym) = X ~v=(n1,...,nm) n1+···+nm=n a~ v yn1 1 yn2 2 ··· ynm m (multi-variate) generating function s.t. a(2,4) = 3
pattern inventory (multi-variate)generating function Fc(y1,2,,ym)= ∑ aay152.…m i=(n1,,nm) n1+…+nm=n a元：#of config.(up to symmetry）with ni many color i G=Dn X/G: 。 8 o38383 FD。(1,2)=g9+yi2+3y1+3y7+3g7}+15+8
a~ v : # of config. (up to symmetry) with ni many color i pattern inventory : FG(y1, y2,...,ym) = X ~v=(n1,...,nm) n1+···+nm=n a~ v yn1 1 yn2 2 ··· ynm m (multi-variate) generating function G = Dn X/G : = y6 1 + y5 1y2 + 3y4 1y2 2 + 3y3 1y3 2 + 3y2 1y4 2 + y1y5 2 + y6 FD6 2 (y1, y2)
- Mr(21,22,...,n)=xe k cycles i=1 cycle index:P(,22n)=a∑M.,n） r∈G pattern inventory (multi-variate)generating function Fc(y1,2,.,ym)= ∑ a1y2…ymm i=(n1,,nm) n1+...+nm=n of config.(up to symmetry)with ni many color i Polya's enumeration formula (1937,1987): m FG(V1,V2,...,Vm)=PG ∑，∑，∑
a~ v : # of config. (up to symmetry) with ni many color i pattern inventory : FG(y1, y2,...,ym) = X ~v=(n1,...,nm) n1+···+nm=n a~ v yn1 1 yn2 2 ··· ynm m (multi-variate) generating function FG(y1, y2,...,ym) = PG X m i=1 yi, X m i=1 y2 i ,...,X m i=1 yn i ! Pólya’s enumeration formula (1937,1987): ⇡ = `1 z }| { (···) `2 z }| { (···)··· `k z }| { (···) | {z } k cycles M⇡(x1, x2,...,xn) = Y k i=1 x`i PG(x1, x2,...,xn) = 1 |G| X ⇡2G cycle index: M⇡(x1, x2,...,xn)