7
$\begingroup$

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.

2 Answers 2

6

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$.

  • 0
    I 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
1

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.