Thursday, April 23, 2020

Pólya's Enumeration Theorem with Applications - Part III


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.

(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

Friday, April 10, 2020

A note on Partial fractions


I recently found a nice identity about Partial fractions on Interesting identities about Partial fractions. The same could also be found, albeit on a different form, on A note on partial fractions. So this post is actually a note on 'A note on Partial fractions'.

It says, if $u+v=$, then for integers $m,n \geq 1$,

$\displaystyle \frac{1}{u^mv^n}=\sum_{k=0}^{m-1}\frac{\binom{n-1+k}{k}}{u^{m-k}}+\sum_{l=0}^{n-1}\frac{\binom{m-1+l}{l}}{v^{n-l}}$

The wordpress page proves this with L'Hospital's rule whereas the webpage proves this with induction. But for someone interested in Probability, two-things-adding-upto-1, the binomial coefficient and then it immediately hit me.

It's actually the 'Problem of Points', one of the classical problems of probability where two friends $A$ and $B$ play a series of games where $A$ needs $m$ wins and $B$ needs $n$ wins to win the match. Assume $A$ has a probability $p$ of winning a each game whereas $B$'s probability is $q=1-p$.

Obviously,

$\mathbb{P}(\text{A wins the match})+\mathbb{P}(\text{B wins the match})=1$

Let's compute the probability of $A$ winning the match. As Pascal reasoned, $A$ needs a minimum of $m$ games and a maximum of $m+n-1$ games to win the match. By the law of total probability,

$\begin{align}
\displaystyle\mathbb{P}(\text{A wins the match})&=\sum_{k=m}^{m+n-1}\mathbb{P}(\text{A wins the match on the }k^{th}\text{ game})\\
&=\sum_{k=m}^{m+n-1}\mathbb{P}(\text{A won }m-1\text{ games out of }k-1\text{ games})\cdot\mathbb{P}(\text{A wins the }k^{th}\text{ game})\\
&=\sum_{k=m}^{m+n-1}\binom{k-1}{m-1}p^{m-1}q^{k-m}\cdot p\\
&=\sum_{k=0}^{n-1}\binom{m+k-1}{k}p^mq^k
\end{align}$

This is 'textbook' Negative Binomial.

Interchanging $m$ with $n$ and $p$ with $q$ gives the probability of $B$ winning the match. Therefore, we finally have,

$\displaystyle \sum_{k=0}^{n-1}\binom{m+k-1}{k}p^mq^k+\sum_{k=0}^{m-1}\binom{n+k-1}{k}q^np^k=1$

Dividing both sides by $p^mq^n$, gives the identity quoted at the start of this post. Tada!!

Note that Fermat's reasoning for the Problem of points produces the following equation. Though correct, it is not particularly useful as a partial fraction decomposition.

$\displaystyle \sum_{k=0}^{n-1}\binom{m+n-1}{m+k}p^{m+k}q^{n-1-k}+\sum_{k=0}^{m-1}\binom{n+m-1}{n+k}q^{n+k}p^{m-1-k}=1$

Hope you enjoyed this.


Until then
Yours Aye
Me