组合数学 (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 81: Line 81:
Due to the above lemma, <math>|G_x|=\frac{|G|}{|Gx|}</math>, thus
Due to the above lemma, <math>|G_x|=\frac{|G|}{|Gx|}</math>, thus
:<math>\sum_{x\in X}|G_x|=\sum_{x\in X}\frac{|G|}{|Gx|}=|G|\sum_{x\in X}\frac{1}{|Gx|}</math>.
:<math>\sum_{x\in X}|G_x|=\sum_{x\in X}\frac{|G|}{|Gx|}=|G|\sum_{x\in X}\frac{1}{|Gx|}</math>.
We may enumerate the <math>x\in X</math> in the sum by first enumerating the orbits and then the elements in each orbit. Suppose there are <math>m</math> orbits <math>X_1,X_2,\ldots,X_m</math>. They forms a partition of <math>X</math>, and for any <math>X_i</math> and every <math>x\in X_i</math>, <math>X_i=Gx</math>. Thus,
We may enumerate the <math>x\in X</math> in the sum by first enumerating the orbits and then the elements in each orbit. Denote the orbits by <math>X_1,X_2,\ldots,X_{|X/G|}</math>. They forms a partition of <math>X</math>, and for any <math>X_i</math> and every <math>x\in X_i</math>, <math>X_i=Gx</math>. Thus,
:<math>|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|X_i|}=|G|\sum_{i=1}^m1=|G|m</math>.
:<math>|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|X_i|}=|G|\sum_{i=1}^{|X/G|}1=|G|{|X/G|}</math>.
Combining everything together
Combining everything together
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|m</math>,
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|{|X/G|}</math>,
which gives us that the number of orbits is
which gives us that the number of orbits is
:<math>m=\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 07:52, 27 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].

Example: coloring a necklace

Suppose a necklace is made of [math]\displaystyle{ n }[/math] beads, each with one of the [math]\displaystyle{ m }[/math] colors. Formally, a necklace is an assignment [math]\displaystyle{ x:[n]\rightarrow[m] }[/math] of [math]\displaystyle{ m }[/math] colors to [math]\displaystyle{ n }[/math] positions. Let [math]\displaystyle{ X=\{x:[n]\rightarrow[m]\} }[/math] be the set of all such assignments.

For example, when [math]\displaystyle{ n=4 }[/math] and [math]\displaystyle{ m=2 }[/math], [math]\displaystyle{ X }[/math] contains all possible 2-colorings (say red and blue) of 4 positions.

[math]\displaystyle{ X=\{{\color{blue}bbbb}, {\color{blue}bbb}{\color{red}r}, {\color{blue}bb}{\color{red}r}{\color{blue}b}, {\color{blue}bb}{\color{red}rr}, {\color{blue}b}{\color{red}r}{\color{blue}b}{\color{red}r}, {\color{blue}b}{\color{red}rr}{\color{blue}b}, {\color{blue}b}{\color{red}rrr}, {\color{red}r}{\color{blue}bbb}, {\color{red}r}{\color{blue}bb}{\color{red}r}, {\color{red}r}{\color{blue}b}{\color{red}r}{\color{blue}b}, {\color{red}r}{\color{blue}b}{\color{red}rr}, {\color{red}rr}{\color{blue}bb}, {\color{red}rr}{\color{blue}b}{\color{red}r}, {\color{red}rrr}{\color{blue}b}, {\color{red}rrrr}\} }[/math]

We consider two kinds of symmetric operations on necklaces:

  • Rotation: the corresponding group is the cyclic group [math]\displaystyle{ C_n }[/math].
  • Rotation and reflection: the corresponding group is the dihedral group [math]\displaystyle{ D_n }[/math].

Mathematically, these operations on necklaces are described as group actions on [math]\displaystyle{ X }[/math]. Recall that each member [math]\displaystyle{ x\in X }[/math] is an [math]\displaystyle{ m }[/math]-coloring [math]\displaystyle{ x:[n]\rightarrow[m] }[/math] of [math]\displaystyle{ n }[/math] positions. Suppose the permutation group is [math]\displaystyle{ G }[/math], for any [math]\displaystyle{ \pi\in G }[/math] and any [math]\displaystyle{ x\in X }[/math], the group action [math]\displaystyle{ \pi\circ x }[/math] is naturally defined as such:

[math]\displaystyle{ (\pi\circ x)(i)=x(\pi(i)) }[/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 a set [math]\displaystyle{ P=\{\pi_1,\pi_2,\ldots,\pi_t\} }[/math] of permutations such that [math]\displaystyle{ \pi_i\circ x=x_i\, }[/math] for [math]\displaystyle{ i=1,2,\ldots,t }[/math]. We construct a bijection between [math]\displaystyle{ G }[/math] and [math]\displaystyle{ P\times G_x }[/math], which will prove the lemma.

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=\pi_i^{-1}\circ(\pi\circ x)=\pi_i^{-1}\circ(\pi_i\circ x)=(\pi_i^{-1}\cdot\pi_i)\circ x=e\circ x=x }[/math].

Denote that [math]\displaystyle{ \sigma=\pi_i^{-1}\cdot \pi }[/math]. Then

  • [math]\displaystyle{ \pi_i\cdot\sigma=\pi_i\cdot(\pi_i^{-1}\cdot\pi)=\pi }[/math], and
  • [math]\displaystyle{ \sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x }[/math], which implies that [math]\displaystyle{ \sigma\in G_x }[/math].

Therefore, each [math]\displaystyle{ \pi\in G }[/math] corresponds to a unique pair [math]\displaystyle{ (\pi_i,\sigma)\in P\times G_x }[/math]. We have a 1-1 mapping from [math]\displaystyle{ G }[/math] to [math]\displaystyle{ P\times G_x }[/math].

For every [math]\displaystyle{ \pi_i\in P }[/math] and every [math]\displaystyle{ \sigma\in G_x }[/math], [math]\displaystyle{ \pi=\pi_i\cdot\sigma\in G }[/math]. We show that this is a 1-1 mapping. Suppose that [math]\displaystyle{ \pi_i\cdot\sigma=\pi_j\cdot\tau }[/math] for some [math]\displaystyle{ \pi_i,\pi_j\in P }[/math] and [math]\displaystyle{ \sigma,\tau\in G_x }[/math]. Then [math]\displaystyle{ (\pi_i\cdot\sigma)\circ x=\pi_i\circ(\sigma\circ x)=\pi_i\circ x=x_i }[/math] and [math]\displaystyle{ (\pi_j\cdot \tau)\circ x=\pi_j\circ(\tau\circ x)=\pi_j\circ x=x_j }[/math], which implies [math]\displaystyle{ x_i=x_j }[/math] and correspondingly [math]\displaystyle{ \pi_i=\pi_j }[/math]. Since [math]\displaystyle{ \pi_i\cdot\sigma=\pi_j\cdot\tau }[/math], [math]\displaystyle{ \sigma=\tau }[/math]. Therefore, we show that the mapping is 1-1.

In conclusion, there exists a bijection between [math]\displaystyle{ P\times G_x }[/math] and [math]\displaystyle{ G }[/math]. As a consequence, [math]\displaystyle{ |Gx||G_x|=|P||G_x|=|P\times G_x|=|G| }[/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].

Due to the above lemma, [math]\displaystyle{ |G_x|=\frac{|G|}{|Gx|} }[/math], thus

[math]\displaystyle{ \sum_{x\in X}|G_x|=\sum_{x\in X}\frac{|G|}{|Gx|}=|G|\sum_{x\in X}\frac{1}{|Gx|} }[/math].

We may enumerate the [math]\displaystyle{ x\in X }[/math] in the sum by first enumerating the orbits and then the elements in each orbit. Denote the orbits by [math]\displaystyle{ X_1,X_2,\ldots,X_{|X/G|} }[/math]. They forms a partition of [math]\displaystyle{ X }[/math], and for any [math]\displaystyle{ X_i }[/math] and every [math]\displaystyle{ x\in X_i }[/math], [math]\displaystyle{ X_i=Gx }[/math]. Thus,

[math]\displaystyle{ |G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|X_i|}=|G|\sum_{i=1}^{|X/G|}1=|G|{|X/G|} }[/math].

Combining everything together

[math]\displaystyle{ \sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|{|X/G|} }[/math],

which gives us that the number of orbits is

[math]\displaystyle{ {|X/G|}=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi| }[/math].
[math]\displaystyle{ \square }[/math]

Pólya's Theory of Counting

The cycle index

Pólya's enumeration formula

de Bruijn's generalization