4
$\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 is a way to solve this using Pólya-Redfield that would be great, but I cannot figure out the group elements.

I know this is a duplicate of: How many different ways can you distribute 5 apples and 8 oranges among six children?. But I can not comment on this or contact the member who explained the task.

Could someone explain in more detail how to apply this, especially how to evaluate the sums?

Maybe someone has more examples? Or even a book with solved exercises? The main Problem is i dont know what i need to know in order to apply it.

Application 1: How many distinct circular necklace patterns are possible with n beads, these being available in k colors.

It could be solved by Burnside's lemma but I also have no clue to to apply it.

$\endgroup$
2
$\begingroup$

If we consider the distributions of the 5 apples, we have 7 possibilities:

$a) \; 5 \; \;b) \;4+1 \;\;c)\; 3+2 \;\; d)\; 3+1+1 \;\; e) \;2+2+1 \;\; f) \;2+1+1+1 \;\; g) \;1+1+1+1+1$

For each of these cases, we have the following number of ways to distribute the apples and oranges (multiplying the number of ways to distribute the apples by the number of ways to distribute the remaining oranges after each child without an apple has been given an orange):

$a)\;\;6\cdot\binom{8}{5}=336$

$b)\;\;6(5)\cdot\binom{9}{5}=3780$

$c)\;\;6(5)\cdot\binom{9}{5}=3780$

$d)\;\;6\binom{5}{2}\cdot\binom{10}{5}=15120$

$e) \;\;6\binom{5}{2}\cdot\binom{10}{5}=15120$

$f)\;\;6\binom{5}{3}\cdot\binom{11}{5}=27720$

$g)\;\;6\cdot\binom{12}{5}=4752$

This gives a total of $\color{blue}{70,608}$

$\endgroup$
  • $\begingroup$ Thank you! This very clear, although i have a question: a) one child gets alle the apples, all 5, i am choosing a child: this can be done in $\binom{6}{1}=6$, im okey there, then by the imposed condition of giving each child at least one i am loosing 5 oranges, and i have only 3 left. Now i have to distribute 3 oranges among 6 children, this can be done $\binom{6+3-1}{6}=\binom{8}{6}=28$ ways so in total i get from case a)$6\binom{8}{6}=168$. $\endgroup$ – thetha Jul 25 '17 at 9:01
  • $\begingroup$ b) I have to distribute 4+1 apples among the children. I have to choose one child who gets the 4 apples and one child who gets 1 one apple. This can be done in 6*5 ways. Then I have to give each remaining child an orange anyway, so i am loosing 4. And i have 4 remaining. I have to distribute them among 6 children, this can be done $\binom{6+4-1}{6}=84$ ways. So in total i would get from case b) "only" $6*5\binom{6+4-1}{6}=2520$ $\endgroup$ – thetha Jul 25 '17 at 9:09
  • $\begingroup$ okey see my mistake, cant edit though. the 6 should be 5. I get it. $\endgroup$ – thetha Jul 25 '17 at 13:07
5
$\begingroup$

I don't think this is a case for Polya theory. In the following I propose a generating function approach. I'm assuming the apples indistinguishable, the oranges indistinguishable, but the children distinguishable.

Assume for the moment that there is an unlimited supply of apples and oranges. An individual child can receive $j$ apples and $k$ oranges, whereby $j+k\geq1$. This option will enter with weight $x^jy^k$ into the following calculation. The formal sum of all options for one child then is $$f(x,y):={1\over1-x}{1\over1-y}-1={x+y-xy\over(1-x)(1-y)}\ .$$ In the product $f(x,y)\cdot f(x,y)$ each option $x^{j'}y^{k'}$ of a first child is multiplied with each option $x^{j''}y^{k''}$ of a second child and stored as $x^{j'+j''}y^{k'+k''}$. Collecting terms of same combined degrees $(j,k)$ then counts the number of allocations where the two children together have received $j$ apples and $k$ oranges. It follows that the combined options for all six children sum up to $$f^6(x,y)=(x+y-xy)^6\>\sum_{j=0}^\infty{-6\choose j}(-x)^j\>\sum_{k=0}^\infty{-6\choose k}(-y)^k\ ,$$ and the number $N$ we are after is the coefficient of $x^5y^8$ in this expansion. We therefore can restrict the first sum to $j\leq5$ and the second sum to $k\leq8$ and then let Mathematica do the work. The answer is $N=70\,608$.

$\endgroup$
  • $\begingroup$ 1) apples indistinguishable, the oranges indistinguishable, but the children distinguishable- -okey children have names. check 2) Assume for the moment that there is an unlimited supply of apples and oranges, okey check 3) i dont understand from This option,... what principle of counting are applied? Maybe you have a link oder a book name? $\endgroup$ – thetha Jul 24 '17 at 19:00
  • $\begingroup$ i think this is going into the direction of generating functions,...... $\endgroup$ – thetha Jul 24 '17 at 20:11
  • $\begingroup$ @thetha: You are on the right track. A convenient starter is H. Wilfs Generatingfunctionology. $\endgroup$ – Markus Scheuer Jul 24 '17 at 21:43
3
$\begingroup$

Here is another "elementary" answer, somewhat similar to the answer of @user84413.

Let $j\in[5]$ be the number of children receiving at least one apple. Given $j$, we can do the following:

  1. Choose $j$ from the six children in ${6\choose j}$ ways, and give each of them an apple.

  2. Distribute the remaining $5-j$ apples arbitrarily among the $j$ chosen children. According to "stars and bars" (S&B) this can be done in $${j+(5-j)-1\choose j-1}={4\choose j-1}$$ ways.

  3. Give an orange to each of the $6-j$ children that has not received an apple.

  4. Distribute the remaining $8-(6-j)=2+j$ oranges arbitrarily among the six children. According to S&B this can be done in $${6+(2+j)-1\choose 6-1}={7+j\choose5}$$ ways.

The number $N$ of admissible allocations of the fruits is therefore given by $$N=\sum_{j=1}^5{6\choose j}\cdot{4\choose j-1}\cdot{7+j\choose5}=70\,608\ .$$ Given the small numbers occurring here the last computation can be done with pencil and paper, as in user84413's answer.

$\endgroup$
  • $\begingroup$ Thank you! I can follow the argumentation. Would it be possible to apply this to the neclace problem? If one reduce it. for example 2 Colors black and white, and n=5. Its solved here ias.ac.in/article/fulltext/reso/007/09/0019-0035, page 12 with the Polyas - theorem. $\endgroup$ – thetha Jul 25 '17 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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