Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

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

share|improve this answer
1  
Wow, just what I was asking; however, I am having a difficult time determining the summations at the end, and does n=6? –  poyla fan May 16 '11 at 2:24
    
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. –  Peter Patzt May 16 '11 at 10:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.