Ever since I first encountered Polya's Enumeration theorem (PET) to solve a problem from Project Euler, it has continued to fascinate on every occasion. I already wrote about them sometime back. Annoying Precision has a beautiful post about PET which I highly recommend. In this post, we are going to see three problems and the associated Cycle Indices. The first two are quite common whereas the third not so much.
The common setup for all the three problems is that we are given an infinite number of balls of $m$ different colors (all identical otherwise). Let the colors be $c_1,c_2,c_3,\cdots,c_m$. Note that we are going for the 'inventory' or the generating function $F(c_1,c_2,c_3,\cdots,c_m)$ rather than just the count.
Case 1 Well..in the first case, given the setup above, we are interested in choosing $n$ balls. This is easy as PET tells us that,
$F_1(c_1,c_2,\cdots,c_m)=Z_{S_n}(a_1,a_2,a_2,\cdots,a_n)$
where $S_n$ denotes the Symmetric group of order $n$ and $a_k=c_1^k+c_2^k+\cdots+c_m^k$.
For example, with $n=3$ and four colors black, white, green and red i.e. $c_1=W$, $c_2=B$, $c_3=R$ and $c_4=G$,
$\begin{align}
F_1(B,G,R,W)&=Z_{S_3}(B+G+R+W,B^2+G^2+R^2+W^2,B^3+G^3+R^3+W^3)\\
&=B^3 + B^2 G + B G^2 + G^3 + B^2 R + B G R + G^2 R + B R^2 +
G R^2 + \\
&\quad R^3 + B^2 W + B G W + G^2 W + B R W + G R W + R^2 W + B W^2 + \\
&\quad G W^2 + R W^2 + W^3\\
\end{align}$
The use of Symmetric Group $S_n$ as we are 'choosing' the balls rather than 'ordering' them. Their Cycle indices are given by
$\displaystyle Z(S_n)=\sum_{i_1+2i_2+3i_3+\cdots+ni_n=n}\prod_{k=1}^n\frac{a_k^{i_k}}{k^{i_k}i_k!}$
The generating function of the same is given by,
$\displaystyle \sum_{n=0}^\infty Z(S_n)t^n=\text{exp}\left(a_1\frac{t}{1}+a_2\frac{t^2}{2}+a_3\frac{t^3}{3}+a_4\frac{t^4}{4}+\cdots\right)$
Case 2 In the second case, we are choosing $n$ balls such that each color can be used at most once. Now, with PET, we have,
$F_2(c_1,c_2,\cdots,c_m)=Z_{A_n}(a_1,a_2,a_2,\cdots,a_n)$
where $A_n$ denotes the Alternating group of order $n$.
For example, with $n=3$ and four colors black, white, green and red i.e. $c_1=W$, $c_2=B$, $c_3=R$ and $c_4=G$,
$\begin{align}
F_2(B,G,R,W)&=Z_{A_3}(B+G+R+W,B^2+G^2+R^2+W^2,B^3+G^3+R^3+W^3)\\
&=B G R + B G W + B R W + G R W\\
\end{align}$
$\displaystyle Z(A_n)=\sum_{i_1+2i_2+3i_3+\cdots+ni_n=n}(-1)^{i_2+i_4+\cdots}\prod_{k=1}^n\frac{a_k^{i_k}}{k^{i_k}i_k!}$
The corresponding generating function is given by,
$\displaystyle \sum_{n=0}^\infty Z(A_n)t^n=\text{exp}\left(a_1\frac{t}{1}-a_2\frac{t^2}{2}+a_3\frac{t^3}{3}-a_4\frac{t^4}{4}+\cdots\right)$
Case 3 In the last case, we will be choosing $n$ balls such that histogram of colors follows $\mathbf{n}=\{j_1,j_2,j_3,\cdots\}=\{1^{n_1},2^{n_2},3^{n_3},\cdots\}$ with $1\leq j_1 \leq j_2 \leq \cdots$ and $n=j_1+j_2+\cdots=n_1+2n_2+3n_3+\cdots$.
Computing the cycle index is tricky in itself. In fact, it is not even clear to me what 'group' are we dealing with here.
Any way to compute the cycle index, consider the polynomials $P_{\{j_1,j_2,j_3,\cdots,j_m\}}(a_1,a_2,a_3,\cdots)$ defined by the recursion (without the arguments $a_i$'s for clarity)
$\displaystyle P_{\{j_1,j_2,\cdots,j_m\}}=a_{j_m}P_{\{j_1,j_2,\cdots,j_{m-1}\}}-\sum_{i=1}^{m-1}P_{\{j_1,j_2,\cdots,j_{i-1},j_i+j_m,j_{i+1},\cdots,j_{m-1}\}}$
with the boundary condition $P_{\{\}}=1$. Now the Cycle index is given by,
$\displaystyle Z(G_{\mathbf{n}})=\frac{1}{n_1!n_2!n_3!\cdots}P_{\{j_1,j_2,j_3,\cdots\}}(a_1,a_2,a_3,a_4,\cdots)$
The Generating function of Cycle indices of all 'histograms' can be shown to be,
$\displaystyle \sum_{\mathbf{n}} Z(G_{\mathbf{n}})\mathbf{t}^{\mathbf{n}}=\text{exp}\left(a_1C_1-a_2C_2+a_3C_3-a_4C_4+\cdots\right)$
where the sum on the LHS runs through all multisets $\mathbf{n}=\{1^{n_1},2^{n_2},3^{n_3}\cdots\}$ with $\mathbf{t}^\mathbf{n}=t_1^{n_1}t_2^{n_2}t_3^{n_3}\cdots$ and $C_n(t_1,t_2,t_3,\cdots)$'s are such that
$\begin{align}
\displaystyle C_n(t_1,t_2,t_3,\cdots)&=[z^n]\log (1-t_1z+t_2z^2-t_3z^3+\cdots)^{-1}\\
&=\sum_{k=1}^n\frac{1}{k}\hat{B}_{n,k}(t_1,-t_2,\cdots,(-1)^{k-1}t_{n-k+1})\\
&=\sum_{n_1+2n_2+3n_3+\cdots=n}(-1)^{n_2+n_4+\cdots}\binom{n_1+n_2+\cdots}{n_1,n_2,\cdots}\frac{\mathbf{t}^\mathbf{n}}{n_1+n_2+\cdots}\\
\end{align}$
where $\hat{B}_{n,k}(x_1,x_2,\cdots,x_{n-k+1})$ are the ordinary Bell Polynomials and the sum in the last equality runs through all integer partitions of $n$.
Note that (i) at $t_1=t$ and $t_i=0$ for $i>1$, that above reduces to the Case 2 and (ii) at $t_i=t$ for $i>0$ the above reduced to Case 1 as it should.
For example, we again have the four colors as in the previous cases but we choose $\mathbf{n}=\{1,1,2\}$. That is, we choose four balls of which two balls are of different colors and the remaining two balls are of the same color but that which different from the first two.
$\begin{align}
F_3(B,G,R,W)&=Z_{G_{\{1,1,2\}}}(B+G+R+W,B^2+G^2+R^2+W^2,B^3+G^3+R^3+W^3,B^4+G^4+R^4+W^4)\\
&=B^2 G R + B G^2 R + B G R^2 + B^2 G W + B G^2 W + B^2 R W + \\
&\quad G^2 R W +
B R^2 W + G R^2 W + B G W^2 + B R W^2 + G R W^2\\
\end{align}$
where I've used $G_{\mathbf{n}}$ to denote the Group we are dealing with.
Now that we come to the end of the post, we make note of something beautiful in case it went unnoticed so far. In fact, it is also the reason why we looked at these three cases.
If we just set aside the notion of PET for a moment, what we have done amounts to expressing the homogenous symmetric functions, elementary symmetric functions and the monomial symmetric functions (respectively) in terms of the powersum symmetric functions in variables $B,G,R,$ and $W$. This reveals a nice connection between Cycle indices (along with their resp. generating functions) and ring of Symmetric functions.
In addition, All of the above have interesting applications in subset/multiset sums modulo a parameter, number of solutions to (multipartite) linear Diophantine equations, multipartite partitions and by extension to un-ordered factorizations which I invite the readers to explore. I found these extremely interesting and instructive to work all these out. Hope you enjoyed too.
The common setup for all the three problems is that we are given an infinite number of balls of $m$ different colors (all identical otherwise). Let the colors be $c_1,c_2,c_3,\cdots,c_m$. Note that we are going for the 'inventory' or the generating function $F(c_1,c_2,c_3,\cdots,c_m)$ rather than just the count.
Case 1 Well..in the first case, given the setup above, we are interested in choosing $n$ balls. This is easy as PET tells us that,
$F_1(c_1,c_2,\cdots,c_m)=Z_{S_n}(a_1,a_2,a_2,\cdots,a_n)$
where $S_n$ denotes the Symmetric group of order $n$ and $a_k=c_1^k+c_2^k+\cdots+c_m^k$.
For example, with $n=3$ and four colors black, white, green and red i.e. $c_1=W$, $c_2=B$, $c_3=R$ and $c_4=G$,
$\begin{align}
F_1(B,G,R,W)&=Z_{S_3}(B+G+R+W,B^2+G^2+R^2+W^2,B^3+G^3+R^3+W^3)\\
&=B^3 + B^2 G + B G^2 + G^3 + B^2 R + B G R + G^2 R + B R^2 +
G R^2 + \\
&\quad R^3 + B^2 W + B G W + G^2 W + B R W + G R W + R^2 W + B W^2 + \\
&\quad G W^2 + R W^2 + W^3\\
\end{align}$
The use of Symmetric Group $S_n$ as we are 'choosing' the balls rather than 'ordering' them. Their Cycle indices are given by
$\displaystyle Z(S_n)=\sum_{i_1+2i_2+3i_3+\cdots+ni_n=n}\prod_{k=1}^n\frac{a_k^{i_k}}{k^{i_k}i_k!}$
The generating function of the same is given by,
$\displaystyle \sum_{n=0}^\infty Z(S_n)t^n=\text{exp}\left(a_1\frac{t}{1}+a_2\frac{t^2}{2}+a_3\frac{t^3}{3}+a_4\frac{t^4}{4}+\cdots\right)$
Case 2 In the second case, we are choosing $n$ balls such that each color can be used at most once. Now, with PET, we have,
$F_2(c_1,c_2,\cdots,c_m)=Z_{A_n}(a_1,a_2,a_2,\cdots,a_n)$
where $A_n$ denotes the Alternating group of order $n$.
For example, with $n=3$ and four colors black, white, green and red i.e. $c_1=W$, $c_2=B$, $c_3=R$ and $c_4=G$,
$\begin{align}
F_2(B,G,R,W)&=Z_{A_3}(B+G+R+W,B^2+G^2+R^2+W^2,B^3+G^3+R^3+W^3)\\
&=B G R + B G W + B R W + G R W\\
\end{align}$
$\displaystyle Z(A_n)=\sum_{i_1+2i_2+3i_3+\cdots+ni_n=n}(-1)^{i_2+i_4+\cdots}\prod_{k=1}^n\frac{a_k^{i_k}}{k^{i_k}i_k!}$
The corresponding generating function is given by,
$\displaystyle \sum_{n=0}^\infty Z(A_n)t^n=\text{exp}\left(a_1\frac{t}{1}-a_2\frac{t^2}{2}+a_3\frac{t^3}{3}-a_4\frac{t^4}{4}+\cdots\right)$
Case 3 In the last case, we will be choosing $n$ balls such that histogram of colors follows $\mathbf{n}=\{j_1,j_2,j_3,\cdots\}=\{1^{n_1},2^{n_2},3^{n_3},\cdots\}$ with $1\leq j_1 \leq j_2 \leq \cdots$ and $n=j_1+j_2+\cdots=n_1+2n_2+3n_3+\cdots$.
Computing the cycle index is tricky in itself. In fact, it is not even clear to me what 'group' are we dealing with here.
Any way to compute the cycle index, consider the polynomials $P_{\{j_1,j_2,j_3,\cdots,j_m\}}(a_1,a_2,a_3,\cdots)$ defined by the recursion (without the arguments $a_i$'s for clarity)
$\displaystyle P_{\{j_1,j_2,\cdots,j_m\}}=a_{j_m}P_{\{j_1,j_2,\cdots,j_{m-1}\}}-\sum_{i=1}^{m-1}P_{\{j_1,j_2,\cdots,j_{i-1},j_i+j_m,j_{i+1},\cdots,j_{m-1}\}}$
with the boundary condition $P_{\{\}}=1$. Now the Cycle index is given by,
$\displaystyle Z(G_{\mathbf{n}})=\frac{1}{n_1!n_2!n_3!\cdots}P_{\{j_1,j_2,j_3,\cdots\}}(a_1,a_2,a_3,a_4,\cdots)$
The Generating function of Cycle indices of all 'histograms' can be shown to be,
$\displaystyle \sum_{\mathbf{n}} Z(G_{\mathbf{n}})\mathbf{t}^{\mathbf{n}}=\text{exp}\left(a_1C_1-a_2C_2+a_3C_3-a_4C_4+\cdots\right)$
where the sum on the LHS runs through all multisets $\mathbf{n}=\{1^{n_1},2^{n_2},3^{n_3}\cdots\}$ with $\mathbf{t}^\mathbf{n}=t_1^{n_1}t_2^{n_2}t_3^{n_3}\cdots$ and $C_n(t_1,t_2,t_3,\cdots)$'s are such that
$\begin{align}
\displaystyle C_n(t_1,t_2,t_3,\cdots)&=[z^n]\log (1-t_1z+t_2z^2-t_3z^3+\cdots)^{-1}\\
&=\sum_{k=1}^n\frac{1}{k}\hat{B}_{n,k}(t_1,-t_2,\cdots,(-1)^{k-1}t_{n-k+1})\\
&=\sum_{n_1+2n_2+3n_3+\cdots=n}(-1)^{n_2+n_4+\cdots}\binom{n_1+n_2+\cdots}{n_1,n_2,\cdots}\frac{\mathbf{t}^\mathbf{n}}{n_1+n_2+\cdots}\\
\end{align}$
where $\hat{B}_{n,k}(x_1,x_2,\cdots,x_{n-k+1})$ are the ordinary Bell Polynomials and the sum in the last equality runs through all integer partitions of $n$.
Note that (i) at $t_1=t$ and $t_i=0$ for $i>1$, that above reduces to the Case 2 and (ii) at $t_i=t$ for $i>0$ the above reduced to Case 1 as it should.
For example, we again have the four colors as in the previous cases but we choose $\mathbf{n}=\{1,1,2\}$. That is, we choose four balls of which two balls are of different colors and the remaining two balls are of the same color but that which different from the first two.
$\begin{align}
F_3(B,G,R,W)&=Z_{G_{\{1,1,2\}}}(B+G+R+W,B^2+G^2+R^2+W^2,B^3+G^3+R^3+W^3,B^4+G^4+R^4+W^4)\\
&=B^2 G R + B G^2 R + B G R^2 + B^2 G W + B G^2 W + B^2 R W + \\
&\quad G^2 R W +
B R^2 W + G R^2 W + B G W^2 + B R W^2 + G R W^2\\
\end{align}$
where I've used $G_{\mathbf{n}}$ to denote the Group we are dealing with.
Now that we come to the end of the post, we make note of something beautiful in case it went unnoticed so far. In fact, it is also the reason why we looked at these three cases.
If we just set aside the notion of PET for a moment, what we have done amounts to expressing the homogenous symmetric functions, elementary symmetric functions and the monomial symmetric functions (respectively) in terms of the powersum symmetric functions in variables $B,G,R,$ and $W$. This reveals a nice connection between Cycle indices (along with their resp. generating functions) and ring of Symmetric functions.
In addition, All of the above have interesting applications in subset/multiset sums modulo a parameter, number of solutions to (multipartite) linear Diophantine equations, multipartite partitions and by extension to un-ordered factorizations which I invite the readers to explore. I found these extremely interesting and instructive to work all these out. Hope you enjoyed too.
(untidy) Mathematica code:
Clear["Global`*"];
MonomSymPoly[l_] :=
MonomSymPoly[l] =
Which[Length[l] <= 0, 1, True,
Subscript[p, Last[l]] MonomSymPoly[Most[l]] -
Sum[MonomSymPoly[
Sort[Most[l] +
Last[l] Table[Boole[i == j], {j, Length[l] - 1}]]], {i,
Length[l] - 1}]];
MultiSetCycIndex[l_] :=
Factor[Expand[
MonomSymPoly[l]/Times @@ Factorial[Length /@ Split[l]]]];
(*Sum[BellY[n,k,Table[Power[-1,j-1]Factorial[ j-1]Subscript[x, \
j],{j,n-k+1}]],{k,n}]/Factorial[n]*)
Li = {1, 2, 2};
Li = Sort[Li];
MultiSetCycIndex[Li]
Expand[% /. Subscript[p, j_] :> W^j + B^j + R^j + G^j]
Print["Hi"];
n = 4;
m = Total[Li];
Coeffs = Table[{Subscript[t, j], 0, 0}, {j, m}];
Do[
Coeffs[[j, 3]] += 1;
, {j, Li}];
(*Exp[Sum[Factor[Sum[Factorial[k-1]BellY[n,k,Table[Power[-1,j-1]\
Factorial[j]Subscript[t, j],{j,n-k+1}]],{k,n}]Subscript[p, \
n]/Factorial[n]],{n,m}]]//TraditionalForm*)
(*Sum[Factorial[k-1]BellY[n,k,Table[Power[-1,j-1]Factorial[j]\
Subscript[t, j],{j,n-k+1}]],{k,n}]/Factorial[n]*)
SeriesCoefficient[
Exp[Sum[Sum[
Factorial[k - 1] BellY[n, k,
Table[Power[-1, j - 1] Factorial[j] Subscript[t, j], {j,
n - k + 1}]], {k, n}] Power[-1, n - 1] Subscript[p, n]/
Factorial[n], {n, m}]], Evaluate @@ Sequence[Coeffs]]
(*SeriesCoefficient[Exp[Sum[Factor[SeriesCoefficient[-Log[1+Sum[\
Subscript[t, i]Power[-x,i],{i,m}]],{x,0,k}]Subscript[p, \
k]],{k,m}]],Evaluate@@Sequence[Coeffs]]*)
SeriesCoefficient[
Exp[Sum[Factor[
SeriesCoefficient[
Log[Power[
1 + Sum[Subscript[t, i] Power[-x, i], {i, m}], -1]], {x, 0,
k}] Power[-1, k - 1] Subscript[p, k]], {k, m}]],
Evaluate @@ Sequence[Coeffs]]
Expand[% /. Subscript[p, j_] :> W^j + B^j + R^j + G^j]
Sum[Factor[
SeriesCoefficient[
Log[Power[1 + Sum[Subscript[t, i] Power[-x, i], {i, m}], -1]], {x,
0, k}] Power[-1, k - 1] Subscript[p, k]], {k, m}]
Series[Log[
Power[1 + Sum[Subscript[t, i] Power[-x, i], {i, m}], -1]], {x, 0, m}]
Series[Exp[Sum[Subscript[a, k] Power[t, k]/k, {k, 4}]], {t, 0, 4}]
Until then
Yours Aye
Me
