This post continues what we discussed here.
Pólya's Enumeration theorem allows us to do much more. In all of the examples above, we did not care about the number of balls we had for each color. In fact, that information was not needed to answer the questions we asked ourselves. Also, in both the necklace and the urn problems, we allowed only one ball at a given position. What if there can be more than one ball at one particular position? Consider the following question.
Example 5: 8 indistinguishable Urns arranged in a circle. What is the number of ways to distribute $n$ blue balls into these urns discounting rotational symmetry?
To make the question clear, number the urns from 1 to 8 in clockwise direction. Let's say we have 16 blue balls. Then according to the question, the distributions {1,2,3,4,5,1,0,0} and {5,1,0,0,1,2,3,4} are identical because one can be transformed to other by rotations. To solve this problem with Pólya's Enumeration Theorem we first find the cycle index of Cyclic group of degree 8.
$Z_{C_8}(x_1,x_2,...,x_8)=\frac{1}{8}(x_1^8+x_2^4+2x_4^2+4x_8)$
Pólya's Enumeration theorem says the answer we are looking for is given by
$\frac{1}{8}((X_1^8)_n+(X_2^4)_n+2(X_4^2)_n+4(X_8)_n)$
where $X_a^b=\frac{1}{(1-z^a)^b}$ and $(F(z))_n$ is the coefficient of $z^n$ in the power series of $F(z)$. With Mathematica's help we find the answer to be $30667$ when $n=16$.
The same procedure can be applied for all the permutations groups and each will give the required answer according to their nature. One thing of interest here is that when there are $n$ balls of the same color, $Z_{S_r}$ counts the number of partitions of $n$ into $r$ parts ($0$ included) and $Z_{-S_r}$ counts the number of partitions of $n$ into $r$ distinct parts ($0$ included). This interpretation has an interesting application in the multiplicative partition of $n$ which will be final piece of our discussion.
Now, the previous problem had balls of the same color. What if there are $n_i$ balls of color $c_i$. This is the second main point that I wished to convey in this post. Let's look at the next problem.
Example 6: 4 indistinguishable Urns are arranged in a circle. What is the number of ways to distribute $m$ different colored balls, with $n_i$ balls of color $c_i$, into these urns discounting rotational symmetry?
The answer to this question proceeds in pretty much the same way as the previous answer. We find the cycle index of Cyclic group of degree 4. The important distinction comes in the definition of $(F(z))_n$. Write $n=(n_1,n_2,..,n_m)$ and define,
$(F(z))_n=\Pi_{j=1}^m(F(z))_{n_j}$ where $F(z)$ will be of the form $\Pi_{i=1}^rX_i^\alpha$.
In case of 4 Urns with 1 white balls and 1 black balls discounting rotational symmetry, we use
$Z_{C_4}(x_1,x_2,x_3,x_4)=\frac{1}{4}(x_1^4+x_2^2+2x_4)$
and the final answer will be $\frac{1}{4}((X_1^4)_{(1,1)}+(X_2^2)_{(1,1)}+2(X_4)_{(1,1)}) = 4$
because {bg,$0$,$0$,$0$}, {b,$0$,g,$0$}, {b,g,$0$,$0$} and {g,b,$0$,$0$} are the possible arrangements.
Example 7: What is the number of ways to distribute 2 white balls and 1 black balls into 3 indistinguishable Urns without taking order into account?
This question can be interpreted in at least two (equivalent) ways. First, it is the number of ways of partitioning the 2-partite number (2,1) into three 2-partite numbers. Second, it is the number of multiplicative partitions of $12(=2^2\times3^1)$. That's easy. $12 = 1\times 2\times 6 = 1\times 3\times 4 = 2\times 2\times 3 = 1\times 1\times 12$. Let's check whether Pólya's Enumeration Theorem gives us the same answer.
$Z_{S_3}=\frac{1}{6}(x_1^3+3x_1x_2+2x_3)$
Following the same procedure as above we see the answer is $\frac{1}{6}((X_1^3)_{(2,1)}+3(X_1X_2)_{(2,1)}+2(X_3)_{(2,1)})$. Let's just evaluate one of these terms, preferably $(X_1X_2)_{(2,1)}$.
$(X_1X_2)_{(2,1)}=[z^2]\frac{1}{(1-z)(1-z^2)}\times[z^1]\frac{1}{(1-z)(1-z^2)}=2\times1=2$.
The final answer is $\frac{1}{6}(6\times3+3\times2\times1+2\times0\times0)=4$ which we saw already. In terms of balls and Urns the distribution would look like {$0$,w,wb}, {$0$,b,ww}, {w,w,b} and {$0$,$0$,wwb}.
Example 8: What is the answer to the same question if we want no two urns to have the same pattern of balls?
In this case it asks for the multiplicative partition of 12 with distinct numbers in which case the last two multiplicative partitions listed above will be eliminated. In terms of Urns and balls, {w,w,b} will be eliminated because two urns have one white ball each and {$0$,$0$,wwb} will be eliminated because two urns are empty. To get the answer via Pólya's Enumeration theorem, we'll be using $Z_{-S_3}$ instead of $Z_{S_3}$.
$Z_{-S_3}=\frac{1}{6}(x_1^3-3x_1x_2+2x_3)$
Hence the answer will be $\frac{1}{6}((X_1^3)_{(2,1)}-3(X_1X_2)_{(2,1)}+2(X_3)_{(2,1)})=2$.
Well, that's it from my end. I'm quite impressed with the way I progressed but it's still upto a first time reader to really judge how good I was in explaining what I intended to explain. Any suggestions and corrections are welcome. It feels extremely good to have come up with this post and I enjoyed it. Hope you'll do too. C ya later.
Until then
Yours Aye,
Me
Pólya's Enumeration theorem allows us to do much more. In all of the examples above, we did not care about the number of balls we had for each color. In fact, that information was not needed to answer the questions we asked ourselves. Also, in both the necklace and the urn problems, we allowed only one ball at a given position. What if there can be more than one ball at one particular position? Consider the following question.
Example 5: 8 indistinguishable Urns arranged in a circle. What is the number of ways to distribute $n$ blue balls into these urns discounting rotational symmetry?
To make the question clear, number the urns from 1 to 8 in clockwise direction. Let's say we have 16 blue balls. Then according to the question, the distributions {1,2,3,4,5,1,0,0} and {5,1,0,0,1,2,3,4} are identical because one can be transformed to other by rotations. To solve this problem with Pólya's Enumeration Theorem we first find the cycle index of Cyclic group of degree 8.
$Z_{C_8}(x_1,x_2,...,x_8)=\frac{1}{8}(x_1^8+x_2^4+2x_4^2+4x_8)$
Pólya's Enumeration theorem says the answer we are looking for is given by
$\frac{1}{8}((X_1^8)_n+(X_2^4)_n+2(X_4^2)_n+4(X_8)_n)$
where $X_a^b=\frac{1}{(1-z^a)^b}$ and $(F(z))_n$ is the coefficient of $z^n$ in the power series of $F(z)$. With Mathematica's help we find the answer to be $30667$ when $n=16$.
The same procedure can be applied for all the permutations groups and each will give the required answer according to their nature. One thing of interest here is that when there are $n$ balls of the same color, $Z_{S_r}$ counts the number of partitions of $n$ into $r$ parts ($0$ included) and $Z_{-S_r}$ counts the number of partitions of $n$ into $r$ distinct parts ($0$ included). This interpretation has an interesting application in the multiplicative partition of $n$ which will be final piece of our discussion.
Now, the previous problem had balls of the same color. What if there are $n_i$ balls of color $c_i$. This is the second main point that I wished to convey in this post. Let's look at the next problem.
Example 6: 4 indistinguishable Urns are arranged in a circle. What is the number of ways to distribute $m$ different colored balls, with $n_i$ balls of color $c_i$, into these urns discounting rotational symmetry?
The answer to this question proceeds in pretty much the same way as the previous answer. We find the cycle index of Cyclic group of degree 4. The important distinction comes in the definition of $(F(z))_n$. Write $n=(n_1,n_2,..,n_m)$ and define,
$(F(z))_n=\Pi_{j=1}^m(F(z))_{n_j}$ where $F(z)$ will be of the form $\Pi_{i=1}^rX_i^\alpha$.
In case of 4 Urns with 1 white balls and 1 black balls discounting rotational symmetry, we use
$Z_{C_4}(x_1,x_2,x_3,x_4)=\frac{1}{4}(x_1^4+x_2^2+2x_4)$
and the final answer will be $\frac{1}{4}((X_1^4)_{(1,1)}+(X_2^2)_{(1,1)}+2(X_4)_{(1,1)}) = 4$
because {bg,$0$,$0$,$0$}, {b,$0$,g,$0$}, {b,g,$0$,$0$} and {g,b,$0$,$0$} are the possible arrangements.
Example 7: What is the number of ways to distribute 2 white balls and 1 black balls into 3 indistinguishable Urns without taking order into account?
This question can be interpreted in at least two (equivalent) ways. First, it is the number of ways of partitioning the 2-partite number (2,1) into three 2-partite numbers. Second, it is the number of multiplicative partitions of $12(=2^2\times3^1)$. That's easy. $12 = 1\times 2\times 6 = 1\times 3\times 4 = 2\times 2\times 3 = 1\times 1\times 12$. Let's check whether Pólya's Enumeration Theorem gives us the same answer.
$Z_{S_3}=\frac{1}{6}(x_1^3+3x_1x_2+2x_3)$
Following the same procedure as above we see the answer is $\frac{1}{6}((X_1^3)_{(2,1)}+3(X_1X_2)_{(2,1)}+2(X_3)_{(2,1)})$. Let's just evaluate one of these terms, preferably $(X_1X_2)_{(2,1)}$.
$(X_1X_2)_{(2,1)}=[z^2]\frac{1}{(1-z)(1-z^2)}\times[z^1]\frac{1}{(1-z)(1-z^2)}=2\times1=2$.
The final answer is $\frac{1}{6}(6\times3+3\times2\times1+2\times0\times0)=4$ which we saw already. In terms of balls and Urns the distribution would look like {$0$,w,wb}, {$0$,b,ww}, {w,w,b} and {$0$,$0$,wwb}.
Example 8: What is the answer to the same question if we want no two urns to have the same pattern of balls?
In this case it asks for the multiplicative partition of 12 with distinct numbers in which case the last two multiplicative partitions listed above will be eliminated. In terms of Urns and balls, {w,w,b} will be eliminated because two urns have one white ball each and {$0$,$0$,wwb} will be eliminated because two urns are empty. To get the answer via Pólya's Enumeration theorem, we'll be using $Z_{-S_3}$ instead of $Z_{S_3}$.
$Z_{-S_3}=\frac{1}{6}(x_1^3-3x_1x_2+2x_3)$
Hence the answer will be $\frac{1}{6}((X_1^3)_{(2,1)}-3(X_1X_2)_{(2,1)}+2(X_3)_{(2,1)})=2$.
Well, that's it from my end. I'm quite impressed with the way I progressed but it's still upto a first time reader to really judge how good I was in explaining what I intended to explain. Any suggestions and corrections are welcome. It feels extremely good to have come up with this post and I enjoyed it. Hope you'll do too. C ya later.
Until then
Yours Aye,
Me
No comments:
Post a Comment