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

== Groups ==
A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms:
* closure: <math>\forall g,h\in G, g\cdot h \in G</math>;
* associativity: <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>;
* identity: there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>;
* inverse: <math>\forall g\in G</math>, there exists an <math>h\in G</math> such that <math>g\cdot h=e</math>, and we denote that <math>h=g^{-1}</math>.

=== Permutation groups===

=== Group action ===
{{Theorem|Definition (group action)|
:A '''group action''' of a group <math>G</math> on a set <math>X</math> is a binary operator:
::<math>\circ:G\times X\rightarrow X</math>
:satisfying:
:* Associativity: <math>(g\cdot h)\circ x=g\circ (h\circ x)</math> for all <math>g,h\in G</math> and <math>x\in X</math>;
:* Identity: <math>e\circ x=x</math> for all <math>x\in X</math>.
}}

== Burnside's Lemma ==

=== Orbits ===

=== Counting orbits===
{{Theorem|Burnside's Lemma|
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. For each <math>\pi\in G</math>, let <math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math> be the set of elements invariant under action by <math>\pi</math>. The number of orbits, denoted <math>|X/G|</math>, is 
::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math>
}}

==Pólya's Theory of Counting ==
=== The cycle index ===

=== Pólya's enumeration formula ===

=== de Bruijn's generalization===