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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
Line 22: Line 22:


=== Orbits ===
=== Orbits ===
Let <math>G</math> be a permutation group acting on a set <math>X</math>. Let <math>\pi\in G, x\in X</math>.
* The '''invariant set''' of <math>\pi</math>:
::<math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math>.
* The '''stabilizer''' of <math>x</math>:
::<math>G_x=\{\pi\in G\mid \pi\circ x=x\}</math>.
* The '''orbit''' of <math>x</math> under action of <math>G</math>:
::<math>Gx=\{\pi\circ x\mid \pi\in G\}</math>.
We think of <math>X</math> as a set of configurations which we may count up to certain symmetry induced by the group action.


=== Counting orbits===
=== Counting orbits===
{{Theorem|Lemma|
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. For any <math>x\in X</math>,
::<math>|G_x||Gx|=|G|\,</math>.
}}
{{Proof|
Recall that the orbit <math>Gx=\{\pi\circ x\mid \pi\in G\}</math>. Suppose that <math>Gx=\{x_1,x_2,\ldots,x_t\}</math>. Then there exist <math>\pi_1,\pi_2,\ldots,\pi_t</math> such that <math>\pi_i\circ x=x_i\,</math> for <math>i=1,2,\ldots,t</math>.
For any <math>\pi\in G</math>, it holds that <math>\pi\circ x=x_i</math> for some <math>x_i</math>, and since <math>\pi_i\circ x=x_i</math>, we have <math>\pi_i\circ x=\pi\circ x</math>, hence <math>(\pi_i^{-1}\cdot\pi)\circ x=x</math>. Denote that <math>\sigma=\pi_i^{-1}\cdot \pi</math>. Then <math>\sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x</math>, which implies that <math>\sigma\in G_x</math>.
}}
{{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>. The number of orbits, denoted <math>|X/G|</math>, is  
::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math>
::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math>
}}
}}

Revision as of 16:15, 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

Cycle decomposition

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

Let [math]\displaystyle{ G }[/math] be a permutation group acting on a set [math]\displaystyle{ X }[/math]. Let [math]\displaystyle{ \pi\in G, x\in X }[/math].

  • The invariant set of [math]\displaystyle{ \pi }[/math]:
[math]\displaystyle{ X_\pi=\{x\in X\mid \pi\circ x=x\} }[/math].
  • The stabilizer of [math]\displaystyle{ x }[/math]:
[math]\displaystyle{ G_x=\{\pi\in G\mid \pi\circ x=x\} }[/math].
  • The orbit of [math]\displaystyle{ x }[/math] under action of [math]\displaystyle{ G }[/math]:
[math]\displaystyle{ Gx=\{\pi\circ x\mid \pi\in G\} }[/math].

We think of [math]\displaystyle{ X }[/math] as a set of configurations which we may count up to certain symmetry induced by the group action.

Counting orbits

Lemma
Let [math]\displaystyle{ G }[/math] be a permutation group acting on a set [math]\displaystyle{ X }[/math]. For any [math]\displaystyle{ x\in X }[/math],
[math]\displaystyle{ |G_x||Gx|=|G|\, }[/math].
Proof.

Recall that the orbit [math]\displaystyle{ Gx=\{\pi\circ x\mid \pi\in G\} }[/math]. Suppose that [math]\displaystyle{ Gx=\{x_1,x_2,\ldots,x_t\} }[/math]. Then there exist [math]\displaystyle{ \pi_1,\pi_2,\ldots,\pi_t }[/math] such that [math]\displaystyle{ \pi_i\circ x=x_i\, }[/math] for [math]\displaystyle{ i=1,2,\ldots,t }[/math].

For any [math]\displaystyle{ \pi\in G }[/math], it holds that [math]\displaystyle{ \pi\circ x=x_i }[/math] for some [math]\displaystyle{ x_i }[/math], and since [math]\displaystyle{ \pi_i\circ x=x_i }[/math], we have [math]\displaystyle{ \pi_i\circ x=\pi\circ x }[/math], hence [math]\displaystyle{ (\pi_i^{-1}\cdot\pi)\circ x=x }[/math]. Denote that [math]\displaystyle{ \sigma=\pi_i^{-1}\cdot \pi }[/math]. Then [math]\displaystyle{ \sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x }[/math], which implies that [math]\displaystyle{ \sigma\in G_x }[/math].

[math]\displaystyle{ \square }[/math]
Burnside's Lemma
Let [math]\displaystyle{ G }[/math] be a permutation group acting on a set [math]\displaystyle{ X }[/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]
Proof.

Let

[math]\displaystyle{ A(\pi,x)=\begin{cases}1 & \pi\circ x=x,\\ 0 & \text{otherwise.}\end{cases} }[/math]

Basically [math]\displaystyle{ A(\pi,x) }[/math] indicates whether [math]\displaystyle{ x }[/math] is invariant under action of [math]\displaystyle{ \pi }[/math]. We can think of [math]\displaystyle{ A }[/math] as a matrix indexed by [math]\displaystyle{ G\times X }[/math]. An important observation is that the row sums and column sums of [math]\displaystyle{ A }[/math] are [math]\displaystyle{ |X_\pi| }[/math] and [math]\displaystyle{ |G_x| }[/math] respectively, namely,

[math]\displaystyle{ |X_\pi|=\sum_{x\in X}A(\pi,x) }[/math] and [math]\displaystyle{ |G_x|=\sum_{\pi\in G}A(\pi,x) }[/math].

Then a double counting gives that

[math]\displaystyle{ \sum_{\pi\in G}|X_\pi|=\sum_{\pi\in G}\sum_{x\in X}A(\pi,x)=\sum_{x\in X}\sum_{\pi\in G}A(\pi,x)=\sum_{x\in X}|G_x| }[/math].


[math]\displaystyle{ \square }[/math]

Pólya's Theory of Counting

The cycle index

Pólya's enumeration formula

de Bruijn's generalization