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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
No edit summary
Line 18: Line 18:


== Burnside's Lemma ==
== Burnside's Lemma ==
=== Orbits ===
=== Counting orbits===
{{Theorem|Burnside's Lemma|
{{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  
: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  
Line 24: Line 28:


==Pólya's Theory of Counting ==
==Pólya's Theory of Counting ==
=== The cycle index ===
=== Pólya's enumeration formula ===
=== de Bruijn's generalization===

Revision as of 08:56, 23 September 2011

Groups

A group [math]\displaystyle{ (G,\cdot) }[/math] is set [math]\displaystyle{ G }[/math] along with a binary operator [math]\displaystyle{ \cdot }[/math] which satisfies the following axioms:

  • closure: [math]\displaystyle{ \forall g,h\in G, g\cdot h \in G }[/math];
  • associativity: [math]\displaystyle{ \forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h }[/math];
  • identity: there exists a special element [math]\displaystyle{ e\in G }[/math], called the identity, such that [math]\displaystyle{ e\cdot g=g }[/math] for any [math]\displaystyle{ g\in G }[/math];
  • inverse: [math]\displaystyle{ \forall g\in G }[/math], there exists an [math]\displaystyle{ h\in G }[/math] such that [math]\displaystyle{ g\cdot h=e }[/math], and we denote that [math]\displaystyle{ h=g^{-1} }[/math].

Permutation groups

Group action

Definition (group action)
A group action of a group [math]\displaystyle{ G }[/math] on a set [math]\displaystyle{ X }[/math] is a binary operator:
[math]\displaystyle{ \circ:G\times X\rightarrow X }[/math]
satisfying:
  • Associativity: [math]\displaystyle{ (g\cdot h)\circ x=g\circ (h\circ x) }[/math] for all [math]\displaystyle{ g,h\in G }[/math] and [math]\displaystyle{ x\in X }[/math];
  • Identity: [math]\displaystyle{ e\circ x=x }[/math] for all [math]\displaystyle{ x\in X }[/math].

Burnside's Lemma

Orbits

Counting orbits

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]

Pólya's Theory of Counting

The cycle index

Pólya's enumeration formula

de Bruijn's generalization