Orbits group action o:GxX→X orbit ofx:Gx={πox|T∈G} equivalent class of configuration x X/G={Gx|x∈X} our goal:count X/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: G=Dn X/G: g
X = [2][n] G = Cn G = Dn X/G : X/G :
configuration x [n][m] 2×○ 4×0 a(2,4)=3 i=(n1,n2,.,nm)s.t.n1+n2+…+nm=n a:of config.(up to symmetry)with ni many color i pattern inventory (multi-variate)generating function Fc(y1,y2,.,ym)= ∑ag1g2.…g nm i=(n1,,nm) m1+..:+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 FG(y1,y2,.,ym)= ∑ aa322.…ym i=(n1,,nm) n1+...+nm=n a元：#of config.(up to symmetry）with ni many color i G-Dn X/G: 0只人 FD6(1,2)=+72+31+3i2+3y12+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)
2 k Mr(21,22,...,n)= k cycles i=1 cycle index: Pa(1,2n）= ∑M(1,2,,cn) π∈G pattern inventory (multi-variate)generating function FG(y1,y2,.,ym)= ∑ a1y22.…ymm t=(n1,,nm) n1+:..+nm=n a:of config.(up to symmetry)with ni many color i Polya's enumeration formula (1937,1987): Fc(y1,y2,.,ym）=PG ∑∑听，，∑ 2=1 i=1 i=1
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)