组合数学 (Spring 2016)/Pólya's theory of counting

From EtoneWiki
Jump to: navigation, search

Groups

A group is set along with a binary operator which satisfies the following axioms:

  • closure: ;
  • associativity: ;
  • identity: there exists a special element , called the identity, such that for any ;
  • inverse: , there exists an such that , and we denote that .

Permutation groups

A permutation is a bijection . We can define a natural operator "" between permutations by function composition, i.e. for any , for all .

Symmetric group
Let denote the set of all permutations of . It is easy to verify that together with function composition form a group. This group is called the symmetric group on elements.

Subgroups of are called permutation groups. The most basic permutation group is itself (since a group is a subgroup of itself). Besides it, there are several typical permutation groups related to natural symmetric operations.

Cyclic group
Given a permutation , denote that
,
and is the identity.
We define a special permutation as that for any , and let . We say that is generated by the permutation . It is easy to verify that is a subgroup of . The group is called the cyclic group of order , which is the group formed by all rotational symmetries of a regular polygon of sides.
It is easy to see that , that is, there are rotations of a regular -gon.
Dihedral group
Define another special permutation as that for all . The Dihedral group is obtained by adding into and then take a closure (under operations of ""). This group is the group of symmetries, including rotations as well as reflections, of a regular polygon of sides.
It is an exercise to check that .

Cycle decomposition

A permutation can be written in the following form:

.

For example,

.

The permutation can be equivalently described as a composition of a number of cycles. For example, in the above permutation, we have two cycles:

and .

We can denote the permutation by

.

Group action

Definition (group action)
A group action of a group on a set is a binary operator:
satisfying:
  • Associativity: for all and ;
  • Identity: for all .

Example: coloring a necklace

Suppose a necklace is made of beads, each with one of the colors. Formally, a necklace is an assignment of colors to positions. Let be the set of all such assignments.

For example, when and , contains all possible 2-colorings (say red and blue) of 4 positions.

We consider two kinds of symmetric operations on necklaces:

  • Rotation: the corresponding group is the cyclic group .
  • Rotation and reflection: the corresponding group is the dihedral group .

Mathematically, these operations on necklaces are described as group actions on . Recall that each member is an -coloring of positions. Suppose the permutation group is , for any and any , the group action is naturally defined as such:

.

Burnside's Lemma

Orbits

Definition
Let be a permutation group acting on a set . For any . The orbit of under action of , denoted , is defined as
.

For any , the followings can be verified for orbits

  • reflexivity: since ;
  • symmetric: if then there is a such that , thus , hence ;
  • transitivity: if and , then there exist such that and , thus , hence .

Therefore, defines an equivalent relation between and , and orbits partition the set .

Example
Back to the example of coloring necklaces.
contains all possible 2-colorings (say red and blue) of 4 positions.
We consider the rotations of necklaces. The cyclic group acting on partitions the into the following equivalent classes:

Invariant sets and stabilizers

Let be a permutation group acting on a set . Let .

  • The invariant set of :
.
  • The stabilizer of :
.

There is a beautiful identity for invariant sets and stabilizers.

Lemma
Let be a permutation group acting on a set . For any ,
.
Proof.

Recall that the orbit . Suppose that . Then there exist a set of permutations such that for . We construct a bijection between and , which will prove the lemma.

For any , it holds that for some , and since , we have , hence

.

Denote that . Then

  • , and
  • , which implies that .

Therefore, each corresponds to a unique pair . We have a 1-1 mapping from to .

For every and every , . We show that this is a 1-1 mapping. Suppose that for some and . Then and , which implies and correspondingly . Since , . Therefore, we show that the mapping is 1-1.

In conclusion, there exists a bijection between and . As a consequence, .

Counting orbits

Burnside's Lemma
Let be a permutation group acting on a set . The number of orbits, denoted , is
Proof.

Let

Basically indicates whether is invariant under action of . We can think of as a matrix indexed by . An important observation is that the row sums and column sums of are and respectively, namely,

and .

Then a double counting gives that

.

Due to the above lemma, , thus

.

We may enumerate the in the sum by first enumerating the orbits and then the elements in each orbit. Denote the orbits by . They forms a partition of , and for any and every , . Thus,

.

Combining everything together

,

which gives us that the number of orbits is

.

Pólya's Theory of Counting

The cycle index

Suppose we want to count the number of ways to color objects using up to colors, discounting symmetries on the objects described by a group . If a coloring is invariant under the action of a permutation , then every position in the same cycle of must have the same color. Therefore, if is decomposed to disjoint cycles, the number of colorings invariant under the action of is .

We define the cycle index of a permutation group . For a permutation of , if is a product of cycles, and the th cycle has length , let

.

The cycle index of is defined by

.

Due to Burnside's lemma, the number of equivalent classes of -colorings of objects, discounting the symmetries described by permutation group , is given by

Pólya's enumeration formula

For any tuple of nonnegative integers satisfying that , let represent the number of nonequivalent (with respect to a permutation group ) -colorings of the objects, where the th color occurs precisely times. The pattern inventory is the (multivariate) generating function for the sequence , defined as

,

where the sum runs over all satisfying that and .

Theorem (Pólya's enumeration formula)
Let be a permutation group. The pattern inventory for the nonequivalent -colorings of objects under the action of is:
.
Proof.

Let be a vector of nonnegative integers satisfying that , and let represent the number of nonequivalent (with respect to a permutation group ) -colorings of the objects, such that the th color occurs precisely times.

The set of configurations is now

,

which contains all -colorings of the objects such that the th color occurs precisely times, without considering symmetries.

For every , the invariant set is now

.
Claim 1: .
Proof of Claim 1.

For , given any permutation , gives the number of colorings in invariant under action of , and is the number of orbits of induced by the action of permutation group . Due to Burnside's lemma,

.
Claim 2: .
Proof of Claim 2.

Supposed that a permutation can be represented as a composition of cycles, the th cycle of length .

The permutation does not change a coloring , if and only if every cycle of are assigned the same color. Then equals the number of -colorings of cycles, where the th cycle is of length , satisfying that the th color occurs precisely times. The following generalized version of multinomial theorem generates for all .

On the other hand,

Therefore,

.

Combining everything together,