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

== Groups ==
A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms:
* ''closure'': <math>\forall g,h\in G, g\cdot h \in G</math>;
* ''associativity'': <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>;
* ''identity'': there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>;
* ''inverse'': <math>\forall g\in G</math>, there exists an <math>h\in G</math> such that <math>g\cdot h=e</math>, and we denote that <math>h=g^{-1}</math>.

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

;Symmetric group <math>S_n</math>
:Let <math>S_n</math> denote the set of all permutations of <math>[n]</math>. It is easy to verify that <math>S_n</math> together with function composition <math>\cdot</math> form a group.  This group is called the '''symmetric group''' on <math>n</math> elements.

Subgroups of <math>S_n</math> are called '''permutation groups'''. The most basic permutation group is <math>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>C_n</math>
:Given a permutation <math>\pi\in S_n</math>, denote that 
::<math>\pi^t=\underbrace{\pi\cdot\pi\cdots\pi}_t</math>, 
:and <math>\pi^0=e</math> is the identity. 
:We define a special permutation <math>\sigma\,</math> as that <math>\sigma(i)=(i+1)\bmod n\,</math> for any <math>i</math>, and let <math>C_n=\{\sigma^t\mid t\ge 0\}</math>. We say that <math>C_n</math> is ''generated'' by the permutation <math>\sigma</math>. It is easy to verify that <math>C_n</math> is a subgroup of <math>S_n</math>. The group <math>C_n</math> is called the '''cyclic group''' of order <math>n</math>, which is the group formed by all '''rotational symmetries''' of a regular polygon of <math>n</math> sides.
:It is easy to see that <math>|C_n|=n</math>, that is, there are <math>n</math> rotations of a regular <math>n</math>-gon.

;Dihedral group <math>D_n</math>
:Define another special permutation <math>\rho\,</math> as that <math>\rho(i)=n-i-1\,</math> for all <math>i\in[n]</math>. The '''Dihedral group''' <math>D_n</math> is obtained by adding <math>\rho</math> into <math>C_n</math> and then take a ''closure'' (under operations of "<math>\cdot</math>"). This group is the group of symmetries, including '''rotations''' as well as '''reflections''', of a regular polygon of <math>n</math> sides.
:It is an exercise to check that <math>|D_n|=2n</math>.

==== Cycle decomposition ====
A permutation <math>\pi:[n]\xrightarrow[\text{onto}]{\text{1-1}}[n]</math> can be written in the following form:
:<math>\begin{pmatrix}
1 & 2 & \cdots & n \\
\pi(1) & \pi(2) & \cdots & \pi(n) 
\end{pmatrix}</math>.
For example,
:<math>\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>1\rightarrow 3\rightarrow 1</math> and <math>2\rightarrow5\rightarrow4\rightarrow2</math>.
We can denote the permutation by
:<math>(13)(254)</math>.

=== Group action ===
{{Theorem|Definition (group action)|
:A '''group action''' of a group <math>G</math> on a set <math>X</math> is a binary operator:
::<math>\circ:G\times X\rightarrow X</math>
:satisfying:
:* Associativity: <math>(g\cdot h)\circ x=g\circ (h\circ x)</math> for all <math>g,h\in G</math> and <math>x\in X</math>;
:* Identity: <math>e\circ x=x</math> for all <math>x\in X</math>.
}}

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

For example, when <math>n=4</math> and <math>m=2</math>, <math>X</math> contains all possible 2-colorings (say red and blue) of 4 positions.
:<math>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>C_n</math>.
* Rotation and reflection: the corresponding group is the dihedral group <math>D_n</math>.

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

== Burnside's Lemma ==

=== Orbits ===
{{Theorem|Definition|
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. For any <math>x\in X</math>. The '''orbit''' of <math>x</math> under action of <math>G</math>, denoted <math>Gx</math>, is defined as
::<math>Gx=\{\pi\circ x\mid \pi\in G\}</math>.
}}

For any <math>x,y,z\in X</math>, the followings can be verified for orbits
* ''reflexivity'': <math>x\in Gx</math> since <math>e\circ x=x</math>;
* ''symmetric'':  if <math>y\in Gx</math> then there is a <math>\pi\in G</math> such that <math>\pi\circ x=y</math>, thus <math>\pi^{-1}\circ y=\pi^{-1}\circ(\pi\circ x) =(\pi^{-1}\cdot \pi)\circ x=e\circ x=x</math>, hence <math>x\in Gy</math>;
* ''transitivity'': if <math>y\in Gx</math> and <math>z\in Gy</math>, then there exist <math>\pi,\sigma\in G</math> such that <math>\pi\circ x=y</math> and <math>\sigma\circ y=z</math>, thus <math>(\sigma\cdot \pi)\circ x=\sigma\circ(\pi\circ x)=\sigma\circ y=z</math>, hence <math>z\in Gx</math>.

Therefore, <math>x\in Gy</math> defines an equivalent relation between <math>x</math> and <math>y</math>, and orbits partition the set <math>X</math>.

;Example
:Back to the example of coloring necklaces.

:<math>X</math> contains all possible 2-colorings (say red and blue) of 4 positions.
::<math>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>C_4</math> acting on <math>X</math> partitions the <math>X</math> into the following equivalent classes:
::<math>\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>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>.

There is a beautiful identity for invariant sets and stabilizers.
{{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 a set <math>P=\{\pi_1,\pi_2,\ldots,\pi_t\}</math> of permutations such that <math>\pi_i\circ x=x_i\,</math> for <math>i=1,2,\ldots,t</math>. We construct a bijection between <math>G</math> and <math>P\times G_x</math>, which will prove the lemma.

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=\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>\sigma=\pi_i^{-1}\cdot \pi</math>. Then 
*<math>\pi_i\cdot\sigma=\pi_i\cdot(\pi_i^{-1}\cdot\pi)=\pi</math>, and 
*<math>\sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x</math>, which implies that <math>\sigma\in G_x</math>. 
Therefore, each <math>\pi\in G</math> corresponds to a unique pair <math>(\pi_i,\sigma)\in P\times G_x</math>. We have a 1-1 mapping from <math>G</math> to <math>P\times G_x</math>.

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

In conclusion, there exists a bijection between <math>P\times G_x</math> and <math>G</math>. As a consequence, <math>|Gx||G_x|=|P||G_x|=|P\times G_x|=|G|</math>.
}}

=== Counting orbits===

{{Theorem|Burnside's Lemma|
: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>
}}
{{Proof|
Let 
:<math>A(\pi,x)=\begin{cases}1 & \pi\circ x=x,\\ 0 & \text{otherwise.}\end{cases}</math>
Basically <math>A(\pi,x)</math> indicates whether <math>x</math> is invariant under action of <math>\pi</math>. We can think of <math>A</math> as a matrix indexed by <math>G\times X</math>. An important observation is that the row sums and column sums of <math>A</math> are <math>|X_\pi|</math> and <math>|G_x|</math> respectively, namely,
:<math>|X_\pi|=\sum_{x\in X}A(\pi,x)</math> and <math>|G_x|=\sum_{\pi\in G}A(\pi,x)</math>.
Then a double counting gives that
:<math>\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>|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>.
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}^{|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>\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>{|X/G|}=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi|</math>.
}}

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

We define the cycle index of a permutation group <math>G</math>.
For a permutation <math>\pi\in G</math> of <math>[n]</math>, if <math>\pi</math> is a product of <math>k</math> cycles, and the <math>i</math>th cycle has length <math>\ell_i</math>, let
:<math>M_\pi(x_1,x_2,\ldots,x_n)=\prod_{i=1}^k x_{\ell_i}</math>.
The '''cycle index''' of <math>G</math> is defined by 
:<math>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>m</math>-colorings of <math>n</math> objects, discounting the symmetries described by permutation group <math>G</math>, is given by
:<math>P_G(\underbrace{m,m,\ldots,m}_{n})</math>

=== Pólya's enumeration formula ===
For any tuple <math>\mathbf{v}=(n_1,n_2,\ldots,n_m)</math> of nonnegative integers satisfying that <math>n_1+n_2+\cdots +n_m=n</math>, let <math>a_{\mathbf{v}}</math> represent the number of nonequivalent (with respect to a permutation group <math>G</math>) <math>m</math>-colorings of the <math>n</math> objects, where the <math>i</math>th color occurs precisely <math>n_i</math> times. The '''pattern inventory''' is the (multivariate) generating function for the sequence <math>a_{\mathbf{v}}</math>, defined as
:<math>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>\mathbf{v}=(n_1,n_2,\ldots,n_m)</math> satisfying that <math>n_1+n_2+\cdots +n_m=n</math> and <math>n_i\ge 0, 1\le i\le m</math>.

{{Theorem|Theorem (Pólya's enumeration formula)|
:Let <math>G</math> be a permutation group. The pattern inventory for the nonequivalent <math>m</math>-colorings of <math>n</math> objects under the action of <math>G</math> is:
::<math>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>\mathbf{v}=(n_1,\ldots,n_m)</math> be a vector of nonnegative integers satisfying that <math>n_1+\cdots+n_m=n</math>, and let <math>a_{\mathbf{v}}</math> represent the number of nonequivalent (with respect to a permutation group <math>G</math>) <math>m</math>-colorings of the <math>n</math> objects, such that the <math>i</math>th color occurs precisely <math>n_i</math> times.

The set of configurations is now
:<math>X^{\mathbf{v}}=\{x:[n]\rightarrow[m]\mid \forall i\in[m], x^{-1}(i)=n_i\}</math>,
which contains all <math>m</math>-colorings of the <math>n</math> objects such that the <math>i</math>th color occurs precisely <math>n_i</math> times, without considering symmetries.

For every <math>\pi\in G</math>, the invariant set is now
:<math>X_\pi^{\mathbf{v}}=\{x\in X^{\mathbf{v}}\mid \pi\circ x=x\}</math>.

;Claim 1<nowiki>:</nowiki> <math>a_{\mathbf{v}}=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi^{\mathbf{v}}|</math>.
{{Proofbox|
;Proof of Claim 1.
For <math>\mathbf{v}=(n_1,\ldots,n_m)</math>, given any permutation <math>\pi\in G</math>, <math>|X^{\mathbf{v}}_\pi|</math> gives the number of colorings <math>x</math> in <math>X^\mathbf{v}</math> invariant under action of <math>\pi</math>, and <math>a_\mathbf{v}</math> is the number of orbits of <math>X^\mathbf{v}</math> induced by the action of permutation group <math>G</math>. Due to Burnside's lemma,
:<math>a_{\mathbf{v}}=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi^{\mathbf{v}}|</math>.
}}
;Claim 2<nowiki>:</nowiki> <math>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>.
{{Proofbox|
;Proof of Claim 2.
Supposed that a permutation <math>\pi\in G</math> can be represented as a composition of <math>k</math> cycles, the <math>i</math>th cycle of length <math>\ell_i</math>.
:<math>\pi=\overbrace{\underbrace{(\cdots\cdots)}_{\ell_1}\underbrace{(\cdots)}_{\ell_2}\cdots\underbrace{(\cdots)}_{\ell_k}}^{k \text{ cycles}}</math>
The permutation <math>\pi</math> does not change a coloring <math>x</math>, if and only if every cycle of <math>\pi</math> are assigned the same color. Then <math>|X^{\mathbf{v}}_\pi|</math> equals the number of <math>m</math>-colorings of <math>k</math> cycles, where the <math>i</math>th cycle is of length <math>\ell_i</math>, satisfying that the <math>i</math>th color occurs precisely <math>n_i</math> times. The following generalized version of multinomial theorem generates <math>|X^{\mathbf{v}}_\pi|</math> for all <math>\mathbf{v}=(n_1,\ldots,n_m)</math>.
:<math>
\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>\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>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>.
}}

Combining everything together,
:<math>
\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>
}}