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

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

A permutation is a bijection [math]\displaystyle{ \pi:[n]\xrightarrow[\text{onto}]{\text{1-1}}[n] }[/math]. We can define a natural operator "[math]\displaystyle{ \cdot }[/math]" between permutations by function composition, i.e. for any [math]\displaystyle{ \pi,\sigma\in S_n }[/math], [math]\displaystyle{ (\pi\cdot\sigma)(i)=\pi(\sigma(i)) }[/math] for all [math]\displaystyle{ i\in[n] }[/math].

Symmetric group [math]\displaystyle{ S_n }[/math]

Let [math]\displaystyle{ S_n }[/math] denote the set of all permutations of [math]\displaystyle{ [n] }[/math]. It is easy to verify that [math]\displaystyle{ S_n }[/math] together with function composition [math]\displaystyle{ \cdot }[/math] form a group. This group is called the symmetric group on [math]\displaystyle{ n }[/math] elements.

Subgroups of [math]\displaystyle{ S_n }[/math] are called permutation groups. The most basic permutation group is [math]\displaystyle{ S_n }[/math] itself (since a group is a subgroup of itself). Besides it, there are several typical permutation groups related to natural symmetric operations.

Cyclic group [math]\displaystyle{ C_n }[/math]

Given a permutation [math]\displaystyle{ \pi\in S_n }[/math], denote that

[math]\displaystyle{ \pi^t=\underbrace{\pi\cdot\pi\cdots\pi}_t }[/math],

and [math]\displaystyle{ \pi^0=e }[/math] is the identity.

We define a special permutation [math]\displaystyle{ \sigma\, }[/math] as that [math]\displaystyle{ \sigma(i)=(i+1)\bmod n\, }[/math] for any [math]\displaystyle{ i }[/math], and let [math]\displaystyle{ C_n=\{\sigma^t\mid t\ge 0\} }[/math]. We say that [math]\displaystyle{ C_n }[/math] is generated by the permutation [math]\displaystyle{ \sigma }[/math]. It is easy to verify that [math]\displaystyle{ C_n }[/math] is a subgroup of [math]\displaystyle{ S_n }[/math]. The group [math]\displaystyle{ C_n }[/math] is called the cyclic group of order [math]\displaystyle{ n }[/math], which is the group formed by all rotational symmetries of a regular polygon of [math]\displaystyle{ n }[/math] sides.

It is easy to see that [math]\displaystyle{ |C_n|=n }[/math], that is, there are [math]\displaystyle{ n }[/math] rotations of a regular [math]\displaystyle{ n }[/math]-gon.

Dihedral group [math]\displaystyle{ D_n }[/math]

Define another special permutation [math]\displaystyle{ \rho\, }[/math] as that [math]\displaystyle{ \rho(i)=n-i-1\, }[/math] for all [math]\displaystyle{ i\in[n] }[/math]. The Dihedral group [math]\displaystyle{ D_n }[/math] is obtained by adding [math]\displaystyle{ \rho }[/math] into [math]\displaystyle{ C_n }[/math] and then take a closure (under operations of "[math]\displaystyle{ \cdot }[/math]"). This group is the group of symmetries, including rotations as well as reflections, of a regular polygon of [math]\displaystyle{ n }[/math] sides.

It is an exercise to check that [math]\displaystyle{ |D_n|=2n }[/math].

Cycle decomposition

A permutation [math]\displaystyle{ \pi:[n]\xrightarrow[\text{onto}]{\text{1-1}}[n] }[/math] can be written in the following form:

[math]\displaystyle{ \begin{pmatrix} 1 & 2 & \cdots & n \\ \pi(1) & \pi(2) & \cdots & \pi(n) \end{pmatrix} }[/math].

For example,

[math]\displaystyle{ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{pmatrix} }[/math].

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

[math]\displaystyle{ 1\rightarrow 3\rightarrow 1 }[/math] and [math]\displaystyle{ 2\rightarrow5\rightarrow4\rightarrow2 }[/math].

We can denote the permutation by

[math]\displaystyle{ (13)(254) }[/math].

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

Definition

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]. The orbit of [math]\displaystyle{ x }[/math] under action of [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ Gx }[/math], is defined as [math]\displaystyle{ Gx=\{\pi\circ x\mid \pi\in G\} }[/math].

For any [math]\displaystyle{ x,y,z\in X }[/math], the followings can be verified for orbits

• reflexivity: [math]\displaystyle{ x\in Gx }[/math] since [math]\displaystyle{ e\circ x=x }[/math];
• symmetric: if [math]\displaystyle{ y\in Gx }[/math] then there is a [math]\displaystyle{ \pi\in G }[/math] such that [math]\displaystyle{ \pi\circ x=y }[/math], thus [math]\displaystyle{ \pi^{-1}\circ y=\pi^{-1}\circ(\pi\circ x) =(\pi^{-1}\cdot \pi)\circ x=e\circ x=x }[/math], hence [math]\displaystyle{ x\in Gy }[/math];
• transitivity: if [math]\displaystyle{ y\in Gx }[/math] and [math]\displaystyle{ z\in Gy }[/math], then there exist [math]\displaystyle{ \pi,\sigma\in G }[/math] such that [math]\displaystyle{ \pi\circ x=y }[/math] and [math]\displaystyle{ \sigma\circ y=z }[/math], thus [math]\displaystyle{ (\sigma\cdot \pi)\circ x=\sigma\circ(\pi\circ x)=\sigma\circ y=z }[/math], hence [math]\displaystyle{ z\in Gx }[/math].

Therefore, [math]\displaystyle{ x\in Gy }[/math] defines an equivalent relation between [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], and orbits partition the set [math]\displaystyle{ X }[/math].

Example

Back to the example of coloring necklaces.

[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}bb}, {\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 the rotations of necklaces. The cyclic group [math]\displaystyle{ C_4 }[/math] acting on [math]\displaystyle{ X }[/math] partitions the [math]\displaystyle{ X }[/math] into the following equivalent classes:

[math]\displaystyle{ \begin{align} &\{{\color{blue}bbbb}\},\\ &\{ {\color{blue}bbb}{\color{red}r}, {\color{blue}bb}{\color{red}r}{\color{blue}b}, {\color{blue}b}{\color{red}r}{\color{blue}bb}, {\color{red}r}{\color{blue}bbb}\},\\ &\{ {\color{blue}bb}{\color{red}rr}, {\color{blue}b}{\color{red}rr}{\color{blue}b}, {\color{red}r}{\color{blue}bb}{\color{red}r}, {\color{red}rr}{\color{blue}bb}, \},\\ &\{ {\color{blue}b}{\color{red}r}{\color{blue}b}{\color{red}r}, {\color{red}r}{\color{blue}b}{\color{red}r}{\color{blue}b}\},\\ &\{ {\color{blue}b}{\color{red}rrr}, {\color{red}r}{\color{blue}b}{\color{red}rr}, {\color{red}rr}{\color{blue}b}{\color{red}r}, {\color{red}rrr}{\color{blue}b}\},\\ &\{ {\color{red}rrrr}\} \end{align} }[/math]

Invariant sets and stabilizers

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].

There is a beautiful identity for invariant sets and stabilizers.

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]

Counting orbits

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

Suppose we want to count the number of ways to color [math]\displaystyle{ n }[/math] objects using up to [math]\displaystyle{ m }[/math] colors, discounting symmetries on the objects described by a group [math]\displaystyle{ G }[/math]. If a coloring [math]\displaystyle{ x:[n]\rightarrow[m] }[/math] is invariant under the action of a permutation [math]\displaystyle{ \pi\in G }[/math], then every position in the same cycle of [math]\displaystyle{ \pi }[/math] must have the same color. Therefore, if [math]\displaystyle{ \pi }[/math] is decomposed to [math]\displaystyle{ k }[/math] disjoint cycles, the number of colorings invariant under the action of [math]\displaystyle{ \pi }[/math] is [math]\displaystyle{ |X_\pi|=m^k }[/math].

We define the cycle index of a permutation group [math]\displaystyle{ G }[/math]. For a permutation [math]\displaystyle{ \pi\in G }[/math] of [math]\displaystyle{ [n] }[/math], if [math]\displaystyle{ \pi }[/math] is a product of [math]\displaystyle{ k }[/math] cycles, and the [math]\displaystyle{ i }[/math]th cycle has length [math]\displaystyle{ \ell_i }[/math], let

[math]\displaystyle{ M_\pi(x_1,x_2,\ldots,x_n)=\prod_{i=1}^k x_{\ell_i} }[/math].

The cycle index of [math]\displaystyle{ G }[/math] is defined by

[math]\displaystyle{ P_G(x_1,x_2,\ldots,x_n)=\frac{1}{|G|}\sum_{\pi\in G}M_\pi(x_1,x_2,\ldots,x_n) }[/math].

Due to Burnside's lemma, the number of equivalent classes of [math]\displaystyle{ m }[/math]-colorings of [math]\displaystyle{ n }[/math] objects, discounting the symmetries described by permutation group [math]\displaystyle{ G }[/math], is given by

[math]\displaystyle{ P_G(\underbrace{m,m,\ldots,m}_{n}) }[/math]

Pólya's enumeration formula

For any tuple [math]\displaystyle{ \mathbf{v}=(n_1,n_2,\ldots,n_m) }[/math] of nonnegative integers satisfying that [math]\displaystyle{ n_1+n_2+\cdots +n_m=n }[/math], let [math]\displaystyle{ a_{\mathbf{v}} }[/math] represent the number of nonequivalent (with respect to a permutation group [math]\displaystyle{ G }[/math]) [math]\displaystyle{ m }[/math]-colorings of the [math]\displaystyle{ n }[/math] objects, where the [math]\displaystyle{ i }[/math]th color occurs precisely [math]\displaystyle{ n_i }[/math] times. The pattern inventory is the (multivariate) generating function for the sequence [math]\displaystyle{ a_{\mathbf{v}} }[/math], defined as

[math]\displaystyle{ F_G(y_1,y_2,\ldots,y_m)=\sum_{\mathbf{v}}a_{\mathbf{v}}y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m} }[/math],

where the sum runs over all [math]\displaystyle{ \mathbf{v}=(n_1,n_2,\ldots,n_m) }[/math] satisfying that [math]\displaystyle{ n_1+n_2+\cdots +n_m=n }[/math] and [math]\displaystyle{ n_i\ge 0, 1\le i\le m }[/math].

Theorem (Pólya's enumeration formula)

Let [math]\displaystyle{ G }[/math] be a permutation group. The pattern inventory for the nonequivalent [math]\displaystyle{ m }[/math]-colorings of [math]\displaystyle{ n }[/math] objects under the action of [math]\displaystyle{ G }[/math] is: [math]\displaystyle{ F_G(y_1,y_2,\ldots,y_m)=P_G\left(\sum_{i=1}^m y_i, \sum_{i=1}^m y_i^2,\ldots, \sum_{i=1}^m y_i^n\right) }[/math].

Proof. Let [math]\displaystyle{ \mathbf{v}=(n_1,\ldots,n_m) }[/math] be a vector of nonnegative integers satisfying that [math]\displaystyle{ n_1+\cdots+n_m=n }[/math], and let [math]\displaystyle{ a_{\mathbf{v}} }[/math] represent the number of nonequivalent (with respect to a permutation group [math]\displaystyle{ G }[/math]) [math]\displaystyle{ m }[/math]-colorings of the [math]\displaystyle{ n }[/math] objects, such that the [math]\displaystyle{ i }[/math]th color occurs precisely [math]\displaystyle{ n_i }[/math] times. The set of configurations is now [math]\displaystyle{ X^{\mathbf{v}}=\{x:[n]\rightarrow[m]\mid \forall i\in[m], x^{-1}(i)=n_i\} }[/math], which contains all [math]\displaystyle{ m }[/math]-colorings of the [math]\displaystyle{ n }[/math] objects such that the [math]\displaystyle{ i }[/math]th color occurs precisely [math]\displaystyle{ n_i }[/math] times, without considering symmetries. For every [math]\displaystyle{ \pi\in G }[/math], the invariant set is now [math]\displaystyle{ X_\pi^{\mathbf{v}}=\{x\in X^{\mathbf{v}}\mid \pi\circ x=x\} }[/math]. Claim 1: [math]\displaystyle{ a_{\mathbf{v}}=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi^{\mathbf{v}}| }[/math]. Proof of Claim 1. For [math]\displaystyle{ \mathbf{v}=(n_1,\ldots,n_m) }[/math], given any permutation [math]\displaystyle{ \pi\in G }[/math], [math]\displaystyle{ |X^{\mathbf{v}}_\pi| }[/math] gives the number of colorings [math]\displaystyle{ x }[/math] in [math]\displaystyle{ X^\mathbf{v} }[/math] invariant under action of [math]\displaystyle{ \pi }[/math], and [math]\displaystyle{ a_\mathbf{v} }[/math] is the number of orbits of [math]\displaystyle{ X^\mathbf{v} }[/math] induced by the action of permutation group [math]\displaystyle{ G }[/math]. Due to Burnside's lemma, [math]\displaystyle{ a_{\mathbf{v}}=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi^{\mathbf{v}}| }[/math]. [math]\displaystyle{ \square }[/math] Claim 2: [math]\displaystyle{ M_\pi\left(\sum_{i=1}^m y_i, \sum_{i=1}^my_i^2,\ldots,\sum_{i=1}^my_i^n\right)=\sum_{\mathbf{v}=(n_1,\ldots,n_m)\atop n_1+\cdots+n_m=n}|X^{\mathbf{v}}_\pi|y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m} }[/math]. Proof of Claim 2. Supposed that a permutation [math]\displaystyle{ \pi\in G }[/math] can be represented as a composition of [math]\displaystyle{ k }[/math] cycles, the [math]\displaystyle{ i }[/math]th cycle of length [math]\displaystyle{ \ell_i }[/math]. [math]\displaystyle{ \pi=\overbrace{\underbrace{(\cdots\cdots)}_{\ell_1}\underbrace{(\cdots)}_{\ell_2}\cdots\underbrace{(\cdots)}_{\ell_k}}^{k \text{ cycles}} }[/math] The permutation [math]\displaystyle{ \pi }[/math] does not change a coloring [math]\displaystyle{ x }[/math], if and only if every cycle of [math]\displaystyle{ \pi }[/math] are assigned the same color. Then [math]\displaystyle{ |X^{\mathbf{v}}_\pi| }[/math] equals the number of [math]\displaystyle{ m }[/math]-colorings of [math]\displaystyle{ k }[/math] cycles, where the [math]\displaystyle{ i }[/math]th cycle is of length [math]\displaystyle{ \ell_i }[/math], satisfying that the [math]\displaystyle{ i }[/math]th color occurs precisely [math]\displaystyle{ n_i }[/math] times. The following generalized version of multinomial theorem generates [math]\displaystyle{ |X^{\mathbf{v}}_\pi| }[/math] for all [math]\displaystyle{ \mathbf{v}=(n_1,\ldots,n_m) }[/math]. [math]\displaystyle{ \begin{align} &\quad\, (y_1^{\ell_1}+y_2^{\ell_1}+\cdots+y_m^{\ell_1})(y_1^{\ell_2}+y_2^{\ell_2}+\cdots+y_m^{\ell_2})\cdots(y_1^{\ell_m}+y_2^{\ell_m}+\cdots+y_m^{\ell_m})\\ &=\sum_{\mathbf{v}=(n_1,\ldots,n_m)\atop n_1+\cdots+n_m=n}|X^{\mathbf{v}}_\pi|y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m}. \end{align} }[/math] On the other hand, [math]\displaystyle{ \begin{align} &\quad\, (y_1^{\ell_1}+y_2^{\ell_1}+\cdots+y_m^{\ell_1})(y_1^{\ell_2}+y_2^{\ell_2}+\cdots+y_m^{\ell_2})\cdots(y_1^{\ell_m}+y_2^{\ell_m}+\cdots+y_m^{\ell_m})\\ &=M_\pi\left(\sum_{i=1}^m y_i, \sum_{i=1}^my_i^2,\ldots,\sum_{i=1}^my_i^n\right). \end{align} }[/math] Therefore, [math]\displaystyle{ M_\pi\left(\sum_{i=1}^m y_i, \sum_{i=1}^my_i^2,\ldots,\sum_{i=1}^my_i^n\right)=\sum_{\mathbf{v}=(n_1,\ldots,n_m)\atop n_1+\cdots+n_m=n}|X^{\mathbf{v}}_\pi|y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m} }[/math]. [math]\displaystyle{ \square }[/math] Combining everything together, [math]\displaystyle{ \begin{align} &\quad\, F_G(y_1,y_2,\ldots,y_m)\\ &=\sum_{\mathbf{v}=(n_1,\ldots,n_m)\atop n_1+\cdots+n_m=n}a_{\mathbf{v}}y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m}\\ &=\sum_{\mathbf{v}=(n_1,\ldots,n_m)\atop n_1+\cdots+n_m=n}\left(\frac{1}{|G|}\sum_{\pi\in G}|X_\pi^{\mathbf{v}}|\right)y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m} &\quad\text{(due to Claim 1)}\\ &=\frac{1}{|G|}\sum_{\pi\in G}\sum_{\mathbf{v}=(n_1,\ldots,n_m)\atop n_1+\cdots+n_m=n} |X_\pi^{\mathbf{v}}|y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m}\\ &=\frac{1}{|G|}\sum_{\pi\in G}M_\pi\left(\sum_{i=1}^m y_i, \sum_{i=1}^my_i^2,\ldots,\sum_{i=1}^my_i^n\right) &\quad\text{(due to Claim 2)}\\ &=P_G\left(\sum_{i=1}^m y_i, \sum_{i=1}^m y_i^2,\ldots, \sum_{i=1}^m y_i^n\right). \end{align} }[/math] [math]\displaystyle{ \square }[/math]