组合数学 (Fall 2011)/Pólya's theory of counting

Burnside's Lemma

Burnside's Lemma

Let [math]\displaystyle{ G }[/math] be a permutation group acting on a set [math]\displaystyle{ X }[/math]. For each [math]\displaystyle{ \pi\in G }[/math], let [math]\displaystyle{ X_\pi=\{x\in X\mid \pi\circ x=x\} }[/math] be the set of elements invariant under action by [math]\displaystyle{ \pi }[/math]. The number of orbits, denoted [math]\displaystyle{ |X/G| }[/math], is [math]\displaystyle{ |X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|. }[/math]