How many different ways can you distribute 5 apples and 8 oranges among six children?

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.

-

1 Answer

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

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9606980085372925, "perplexity_flag": "head"}