How many different ways can you distribute 5 apples and 8 oranges among six children if every child must receive at least one piece of fruit? If there was a way to solve this using Pólya-Redfield that would be great, but I cannot figure out the group elements.
How many different ways can you distribute 5 apples and 8 oranges among six children?
2 Answers
I am too lazy to calculate the numbers of elements with $k$ cycles in $S_8$ but if you do that yourself a solution could work as follows. (I will use this version of Redfield-Polya and $[n]$ shall denote $\{1,\dots,n\}$.)
Let us take $X = [13]$ the set of fruits, where $G= S_5 \times S_8$ acts on $X$ such that the first five apples and the later eight oranges are indistinguishable. Then $K_n = |[n]^X/G|$ is the number of ways to distribute these apples and oranges among six distinguishable children. And $ N_n = K_n -n\cdot K_{n-1}$ the of ways to distribute these apples and oranges among six distinguishable children such that every child must recieve at least one piece of fruit.
Now by the Theorem $K_n = \frac{1}{|G|} \sum_{g\in G} n^{c(g)} = \frac{1}{5!\cdot 8!} \left(\sum_{g\in S_5} n^{c(g)}\right)\left(\sum_{g\in S_8} n^{c(g)}\right) = \frac{1}{5!\cdot 8!} \left(\sum_{i\in [2]} d_i n^{i}\right) \left(\sum_{i\in [4]} e_i n^{i}\right),$ where $c(g)$ is the number of cycles of $g$, $d_i$ the number of permutations of $S_5$ with exactly $i$ cycles and $e_i$ the number of permutations of $S_8$ with exactly $i$ cycles.
The number that we are looking for in the end is $N_6$.
-
0I added what you are looking for in the end. If you have further problems with how I manipulated the sums, I might write it down in more clarity later but encourage you to try to figure it out by yourself. If you have problems specifically figuring out $\sum_{i\in[4]} e_in^i,$ I hope there might be an easier way to find that but I couldn't come up with it yet. I can give you $\sum_{i\in[2]}d_in^i = 1 + 84 n + 35 n^2$ as a reference though as this is a lot easier to calculate. – 2011-05-16
The direct approach is by the use of generating functions.
One kid may have $AB:= (1 + a + a^2 + \cdots + a^5)(1 + b + b^2 + \cdots + b^8)$ fruits, no-fruits are possible. The variants for six kids are AB^6.
the K's, for $5$ apples and $8$ oranges (no-fruits allowed) is the coefficient of $a^5b^8 $. For different n's
$ 1 = 1\times 1, \ 54=6\times 9, \ 945=21\times 45, \ 9240=56\times 165, \ 62370=126\times 495,\ 324324=252\times 1287$
Above the factors are obtained by star and bars method, independently for apples and oranges.
If one fruit is mandatory, the GF for one kid is $AB-1$ and for six kids is $(AB-1)^6$
the N's, (one-fruit mandatory) is the coefficient of $a^5b^8$. For different n's
$N = 1, 52, 786, 5780, 25085, 70608$
The link between K's and N's is given by inclusion-exclusion. We obtain a PIE generating function by multiplying K's with binomial coefficient:
$atleast(x) = 324324+374220x+138600x^2+18900x^3+810x^4+6x^5$
where, for example, there are 138600 distributions with at least two no-fruit kids among six.
$exact(x) = atleast(x-1) = 70608+150510x+86700x^2+15720x^3+780x^4+6x^5$
where, for example, there are $86700$ distributions having exactly two no-fruit kids among six.
The numbers N are also obtained from above coefficients by division with binomial coefficients.
until now we have obtained $N_6$ directly from a GF (and Maple), or via a simpler GF and inclusion-exclusion. We are asked to obtain the number 70608 using labelled apples and oranges.
"Fruits colored with kids"
The combinatorial species is
$E_5(X_1+X_2+X_3+X_4+X_5+X_6).E_8(X_1+X_2+X_3+X_4+X_5+X_6).$
The cycle index is the product of
$Z_5 (a_1 + b_1 + c_1 + d_1 + e_1 + f_1, \ \ a_2 + b_2 + c_2 + d_2 + e_2+ f_2,...)$ and
$Z_8 (a_1 + b_1 + c_1 + d_1 + e_1 + f_1, \ \ a_2 + b_2 + c_2 + d_2 + e_2+ f_2,...)$
Since the sum of coefficients divided by |G| is the required number of orbits (or types), we have to replace all the variables with 1's.
Instead of $Z(6,6,6,6,6...)$ we may take a more general formula that is $Z(n,n,n,n...)$ that will deliver faster all the K numbers above. The result is"
${1 \over 5!8!}(n^5+10n^4+35n^3+50n^2+24n)(n^8+28n^7+322n^6+1960n^5+676n^4+13132n^3+13068n^2+5040n)$
Then we do the PIE.
"Kids colored with fruits"
The species is $[E_1(A+B) + E_2(A+B) +...+E_{13}(A+B)]^6$
We need all cycle indices from Symmetric 1 to Symmetric 13. (there is some place to truncate, since a kid may not have more than 8 fruits, if every kid has a at least one fruit). The cycle index is the sum of all 13 cycle indices meaning that a kid may have 1 or 2 or 3, or... 13 fruits :
$Z(a_1 + b_1, a_2 + b_2, ..... a_{13} + b_{13})$
We have to extract only the part for exactly 5 apples and 8 oranges. A good idea is to replace $a_1$ with $a_1.u$, $a_2$ with $a_2.u^2$ .... $b_{13}$ with $b_{13}.v^{13}$ and to take the coefficient of $u^5v^8$
then we replace every variable with $1$ and we get the 70608.