# 组合数学 (Fall 2017)/Pólya's theory of counting

## Groups

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

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

### Permutation groups

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

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

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

Cyclic group ${\displaystyle C_{n}}$
Given a permutation ${\displaystyle \pi \in S_{n}}$, denote that
${\displaystyle \pi ^{t}=\underbrace {\pi \cdot \pi \cdots \pi } _{t}}$,
and ${\displaystyle \pi ^{0}=e}$ is the identity.
We define a special permutation ${\displaystyle \sigma \,}$ as that ${\displaystyle \sigma (i)=(i+1){\bmod {n}}\,}$ for any ${\displaystyle i}$, and let ${\displaystyle C_{n}=\{\sigma ^{t}\mid t\geq 0\}}$. We say that ${\displaystyle C_{n}}$ is generated by the permutation ${\displaystyle \sigma }$. It is easy to verify that ${\displaystyle C_{n}}$ is a subgroup of ${\displaystyle S_{n}}$. The group ${\displaystyle C_{n}}$ is called the cyclic group of order ${\displaystyle n}$, which is the group formed by all rotational symmetries of a regular polygon of ${\displaystyle n}$ sides.
It is easy to see that ${\displaystyle |C_{n}|=n}$, that is, there are ${\displaystyle n}$ rotations of a regular ${\displaystyle n}$-gon.
Dihedral group ${\displaystyle D_{n}}$
Define another special permutation ${\displaystyle \rho \,}$ as that ${\displaystyle \rho (i)=n-i-1\,}$ for all ${\displaystyle i\in [n]}$. The Dihedral group ${\displaystyle D_{n}}$ is obtained by adding ${\displaystyle \rho }$ into ${\displaystyle C_{n}}$ and then take a closure (under operations of "${\displaystyle \cdot }$"). This group is the group of symmetries, including rotations as well as reflections, of a regular polygon of ${\displaystyle n}$ sides.
It is an exercise to check that ${\displaystyle |D_{n}|=2n}$.

#### Cycle decomposition

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

${\displaystyle {\begin{pmatrix}1&2&\cdots &n\\\pi (1)&\pi (2)&\cdots &\pi (n)\end{pmatrix}}}$.

For example,

${\displaystyle {\begin{pmatrix}1&2&3&4&5\\3&5&1&2&4\end{pmatrix}}}$.

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

${\displaystyle 1\rightarrow 3\rightarrow 1}$ and ${\displaystyle 2\rightarrow 5\rightarrow 4\rightarrow 2}$.

We can denote the permutation by

${\displaystyle (13)(254)}$.

### Group action

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

#### Example: coloring a necklace

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

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

${\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}\}}$

We consider two kinds of symmetric operations on necklaces:

• Rotation: the corresponding group is the cyclic group ${\displaystyle C_{n}}$.
• Rotation and reflection: the corresponding group is the dihedral group ${\displaystyle D_{n}}$.

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

${\displaystyle (\pi \circ x)(i)=x(\pi (i))}$.

## Burnside's Lemma

### Orbits

 Definition Let ${\displaystyle G}$ be a permutation group acting on a set ${\displaystyle X}$. For any ${\displaystyle x\in X}$. The orbit of ${\displaystyle x}$ under action of ${\displaystyle G}$, denoted ${\displaystyle Gx}$, is defined as ${\displaystyle Gx=\{\pi \circ x\mid \pi \in G\}}$.

For any ${\displaystyle x,y,z\in X}$, the followings can be verified for orbits

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

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

Example
Back to the example of coloring necklaces.
${\displaystyle X}$ contains all possible 2-colorings (say red and blue) of 4 positions.
${\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}\}}$
We consider the rotations of necklaces. The cyclic group ${\displaystyle C_{4}}$ acting on ${\displaystyle X}$ partitions the ${\displaystyle X}$ into the following equivalent classes:
{\displaystyle {\begin{aligned}&\{{\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{aligned}}}

### Invariant sets and stabilizers

Let ${\displaystyle G}$ be a permutation group acting on a set ${\displaystyle X}$. Let ${\displaystyle \pi \in G,x\in X}$.

• The invariant set of ${\displaystyle \pi }$:
${\displaystyle X_{\pi }=\{x\in X\mid \pi \circ x=x\}}$.
• The stabilizer of ${\displaystyle x}$:
${\displaystyle G_{x}=\{\pi \in G\mid \pi \circ x=x\}}$.

There is a beautiful identity for invariant sets and stabilizers.

 Lemma Let ${\displaystyle G}$ be a permutation group acting on a set ${\displaystyle X}$. For any ${\displaystyle x\in X}$, ${\displaystyle |G_{x}||Gx|=|G|\,}$.
Proof.
 Recall that the orbit ${\displaystyle Gx=\{\pi \circ x\mid \pi \in G\}}$. Suppose that ${\displaystyle Gx=\{x_{1},x_{2},\ldots ,x_{t}\}}$. Then there exist a set ${\displaystyle P=\{\pi _{1},\pi _{2},\ldots ,\pi _{t}\}}$ of permutations such that ${\displaystyle \pi _{i}\circ x=x_{i}\,}$ for ${\displaystyle i=1,2,\ldots ,t}$. We construct a bijection between ${\displaystyle G}$ and ${\displaystyle P\times G_{x}}$, which will prove the lemma. For any ${\displaystyle \pi \in G}$, it holds that ${\displaystyle \pi \circ x=x_{i}}$ for some ${\displaystyle x_{i}}$, and since ${\displaystyle \pi _{i}\circ x=x_{i}}$, we have ${\displaystyle \pi _{i}\circ x=\pi \circ x}$, hence ${\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}$. Denote that ${\displaystyle \sigma =\pi _{i}^{-1}\cdot \pi }$. Then ${\displaystyle \pi _{i}\cdot \sigma =\pi _{i}\cdot (\pi _{i}^{-1}\cdot \pi )=\pi }$, and ${\displaystyle \sigma \circ x=(\pi _{i}^{-1}\cdot \pi )\circ x=x}$, which implies that ${\displaystyle \sigma \in G_{x}}$. Therefore, each ${\displaystyle \pi \in G}$ corresponds to a unique pair ${\displaystyle (\pi _{i},\sigma )\in P\times G_{x}}$. We have a 1-1 mapping from ${\displaystyle G}$ to ${\displaystyle P\times G_{x}}$. For every ${\displaystyle \pi _{i}\in P}$ and every ${\displaystyle \sigma \in G_{x}}$, ${\displaystyle \pi =\pi _{i}\cdot \sigma \in G}$. We show that this is a 1-1 mapping. Suppose that ${\displaystyle \pi _{i}\cdot \sigma =\pi _{j}\cdot \tau }$ for some ${\displaystyle \pi _{i},\pi _{j}\in P}$ and ${\displaystyle \sigma ,\tau \in G_{x}}$. Then ${\displaystyle (\pi _{i}\cdot \sigma )\circ x=\pi _{i}\circ (\sigma \circ x)=\pi _{i}\circ x=x_{i}}$ and ${\displaystyle (\pi _{j}\cdot \tau )\circ x=\pi _{j}\circ (\tau \circ x)=\pi _{j}\circ x=x_{j}}$, which implies ${\displaystyle x_{i}=x_{j}}$ and correspondingly ${\displaystyle \pi _{i}=\pi _{j}}$. Since ${\displaystyle \pi _{i}\cdot \sigma =\pi _{j}\cdot \tau }$, ${\displaystyle \sigma =\tau }$. Therefore, we show that the mapping is 1-1. In conclusion, there exists a bijection between ${\displaystyle P\times G_{x}}$ and ${\displaystyle G}$. As a consequence, ${\displaystyle |Gx||G_{x}|=|P||G_{x}|=|P\times G_{x}|=|G|}$.
${\displaystyle \square }$

### Counting orbits

 Burnside's Lemma Let ${\displaystyle G}$ be a permutation group acting on a set ${\displaystyle X}$. The number of orbits, denoted ${\displaystyle |X/G|}$, is ${\displaystyle |X/G|={\frac {1}{|G|}}\sum _{\pi \in G}|X_{\pi }|.}$
Proof.
 Let ${\displaystyle A(\pi ,x)={\begin{cases}1&\pi \circ x=x,\\0&{\text{otherwise.}}\end{cases}}}$ Basically ${\displaystyle A(\pi ,x)}$ indicates whether ${\displaystyle x}$ is invariant under action of ${\displaystyle \pi }$. We can think of ${\displaystyle A}$ as a matrix indexed by ${\displaystyle G\times X}$. An important observation is that the row sums and column sums of ${\displaystyle A}$ are ${\displaystyle |X_{\pi }|}$ and ${\displaystyle |G_{x}|}$ respectively, namely, ${\displaystyle |X_{\pi }|=\sum _{x\in X}A(\pi ,x)}$ and ${\displaystyle |G_{x}|=\sum _{\pi \in G}A(\pi ,x)}$. Then a double counting gives that ${\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}|}$. Due to the above lemma, ${\displaystyle |G_{x}|={\frac {|G|}{|Gx|}}}$, thus ${\displaystyle \sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|Gx|}}=|G|\sum _{x\in X}{\frac {1}{|Gx|}}}$. We may enumerate the ${\displaystyle x\in X}$ in the sum by first enumerating the orbits and then the elements in each orbit. Denote the orbits by ${\displaystyle X_{1},X_{2},\ldots ,X_{|X/G|}}$. They forms a partition of ${\displaystyle X}$, and for any ${\displaystyle X_{i}}$ and every ${\displaystyle x\in X_{i}}$, ${\displaystyle X_{i}=Gx}$. Thus, ${\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|}}$. Combining everything together ${\displaystyle \sum _{\pi \in G}|X_{\pi }|=\sum _{x\in X}|G_{x}|=|G|\sum _{x\in X}{\frac {1}{|Gx|}}=|G|{|X/G|}}$, which gives us that the number of orbits is ${\displaystyle {|X/G|}={\frac {1}{|G|}}\sum _{\pi \in G}|X_{\pi }|}$.
${\displaystyle \square }$

## Pólya's Theory of Counting

### The cycle index

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

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

${\displaystyle M_{\pi }(x_{1},x_{2},\ldots ,x_{n})=\prod _{i=1}^{k}x_{\ell _{i}}}$.

The cycle index of ${\displaystyle G}$ is defined by

${\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})}$.

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

${\displaystyle P_{G}(\underbrace {m,m,\ldots ,m} _{n})}$

### Pólya's enumeration formula

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

${\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}}}$,

where the sum runs over all ${\displaystyle \mathbf {v} =(n_{1},n_{2},\ldots ,n_{m})}$ satisfying that ${\displaystyle n_{1}+n_{2}+\cdots +n_{m}=n}$ and ${\displaystyle n_{i}\geq 0,1\leq i\leq m}$.

 Theorem (Pólya's enumeration formula) Let ${\displaystyle G}$ be a permutation group. The pattern inventory for the nonequivalent ${\displaystyle m}$-colorings of ${\displaystyle n}$ objects under the action of ${\displaystyle G}$ is: ${\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)}$.
Proof.

Let ${\displaystyle \mathbf {v} =(n_{1},\ldots ,n_{m})}$ be a vector of nonnegative integers satisfying that ${\displaystyle n_{1}+\cdots +n_{m}=n}$, and let ${\displaystyle a_{\mathbf {v} }}$ represent the number of nonequivalent (with respect to a permutation group ${\displaystyle G}$) ${\displaystyle m}$-colorings of the ${\displaystyle n}$ objects, such that the ${\displaystyle i}$th color occurs precisely ${\displaystyle n_{i}}$ times.

The set of configurations is now

${\displaystyle X^{\mathbf {v} }=\{x:[n]\rightarrow [m]\mid \forall i\in [m],x^{-1}(i)=n_{i}\}}$,

which contains all ${\displaystyle m}$-colorings of the ${\displaystyle n}$ objects such that the ${\displaystyle i}$th color occurs precisely ${\displaystyle n_{i}}$ times, without considering symmetries.

For every ${\displaystyle \pi \in G}$, the invariant set is now

${\displaystyle X_{\pi }^{\mathbf {v} }=\{x\in X^{\mathbf {v} }\mid \pi \circ x=x\}}$.
Claim 1: ${\displaystyle a_{\mathbf {v} }={\frac {1}{|G|}}\sum _{\pi \in G}|X_{\pi }^{\mathbf {v} }|}$.
 Proof of Claim 1. For ${\displaystyle \mathbf {v} =(n_{1},\ldots ,n_{m})}$, given any permutation ${\displaystyle \pi \in G}$, ${\displaystyle |X_{\pi }^{\mathbf {v} }|}$ gives the number of colorings ${\displaystyle x}$ in ${\displaystyle X^{\mathbf {v} }}$ invariant under action of ${\displaystyle \pi }$, and ${\displaystyle a_{\mathbf {v} }}$ is the number of orbits of ${\displaystyle X^{\mathbf {v} }}$ induced by the action of permutation group ${\displaystyle G}$. Due to Burnside's lemma, ${\displaystyle a_{\mathbf {v} }={\frac {1}{|G|}}\sum _{\pi \in G}|X_{\pi }^{\mathbf {v} }|}$. ${\displaystyle \square }$
Claim 2: ${\displaystyle M_{\pi }\left(\sum _{i=1}^{m}y_{i},\sum _{i=1}^{m}y_{i}^{2},\ldots ,\sum _{i=1}^{m}y_{i}^{n}\right)=\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}}}$.
 Proof of Claim 2. Supposed that a permutation ${\displaystyle \pi \in G}$ can be represented as a composition of ${\displaystyle k}$ cycles, the ${\displaystyle i}$th cycle of length ${\displaystyle \ell _{i}}$. ${\displaystyle \pi =\overbrace {\underbrace {(\cdots \cdots )} _{\ell _{1}}\underbrace {(\cdots )} _{\ell _{2}}\cdots \underbrace {(\cdots )} _{\ell _{k}}} ^{k{\text{ cycles}}}}$ The permutation ${\displaystyle \pi }$ does not change a coloring ${\displaystyle x}$, if and only if every cycle of ${\displaystyle \pi }$ are assigned the same color. Then ${\displaystyle |X_{\pi }^{\mathbf {v} }|}$ equals the number of ${\displaystyle m}$-colorings of ${\displaystyle k}$ cycles, where the ${\displaystyle i}$th cycle is of length ${\displaystyle \ell _{i}}$, satisfying that the ${\displaystyle i}$th color occurs precisely ${\displaystyle n_{i}}$ times. The following generalized version of multinomial theorem generates ${\displaystyle |X_{\pi }^{\mathbf {v} }|}$ for all ${\displaystyle \mathbf {v} =(n_{1},\ldots ,n_{m})}$. {\displaystyle {\begin{aligned}&\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_{\pi }^{\mathbf {v} }|y_{1}^{n_{1}}y_{2}^{n_{2}}\cdots y_{m}^{n_{m}}.\end{aligned}}} On the other hand, {\displaystyle {\begin{aligned}&\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}^{m}y_{i}^{2},\ldots ,\sum _{i=1}^{m}y_{i}^{n}\right).\end{aligned}}} Therefore, ${\displaystyle M_{\pi }\left(\sum _{i=1}^{m}y_{i},\sum _{i=1}^{m}y_{i}^{2},\ldots ,\sum _{i=1}^{m}y_{i}^{n}\right)=\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}}}$. ${\displaystyle \square }$

Combining everything together,

{\displaystyle {\begin{aligned}&\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}^{m}y_{i}^{2},\ldots ,\sum _{i=1}^{m}y_{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{aligned}}}
${\displaystyle \square }$