Question

In how many ways can 10 identical presents be distributed among 6 children so that each child gets at least one present?

Answer 1

Give each child one present. There are 4 presents remaining. The number of ways of distributing the remaining 4 presents among the 6 children is
\[6C4=\frac{6!}{4!2!}=you\ can\ calculate\]

Answer 2

@kropot72, doesn't that assume that the remaining 4 presents go to 4 different children from among the 6? The way I read the problem, one child could get 2, 3 or all 4 of the remaining presents.

Answer 3

I think the first 6 presents would be a permutation, \(10 P 6=\dfrac{10!}{4!}\)

But then with the remaining 4 presents, I'm thinking it would be something like a partitioning of the 4 presents into 6 groups, where a group can have between 0 and 4 of the presents?? Notice that at least 2 groups must have 0, but as many as 5 could have 0.

Answer 4

There can be many combinations for the arrangement!
Because it is atleast so it should be 10 or 9 or 8 or 7 or 6 and so we add them up.
@DebbieG should I permute or select/combine?
10C6 + 9C6 + 8C6 + 7C6 + 6C6

Answer 5

I think the first 6 presents is just a straight forward permutation as I said above.

I think it could be similar to this example with the apples, but since the presents are distinct you have to account for that? You can almost do it as if identical, but then multiply by the number of permutations of the 4 presents??

http://math.stackexchange.com/questions/152451/combinations-of-distinct-vs-identical-objects

I have to go, will be back later to see if we've figured this out! :)

Answer 6

Oh crud, I just realized that they are IDENTICAL presents... must read the question more carefully, lol! That makes it a lot simpler.....

Answer 7

This problem has been bugging me because I want to understand it. I think I finally get it! It's discussed here:
http://www.beatthegmat.com/gifts-t101495.html
But even reading that, I was having a hard time wrapping my head around it, but I think I get it now.

I think the solution, with n=6 and r=4, is: \[\left(\begin{matrix}n+r-1 \\ r\end{matrix}\right)=\frac{ (n+r-1)! }{ r!(n-1)! }=\frac{ 9! }{ 4!5! }=126\]but here is the intuition behind it.

Think of putting the 6 children in a row:

C1 C2 C3 C4 C5 C6

Now starting at C1, you either drop a present with that child, or you move to C2. If you drop a present, you can then either drop another present with C1, or not, in which case you move to C2. And so on, down the row of kids, until the 4 presents have been dropped somewhere.

Model this process with \(\Large \rightarrow\) to represent moving from child to child, and \( \Large \Box \) to represent leaving a present. So the process involves arranging a total of 4 BOXES and 5 ARROWS. E.g.:

\( \Large \Box \)\( \Large \Box \)\( \Large \Box \)\( \Large \Box \) \(\Large \rightarrow\)\(\Large \rightarrow\)\(\Large \rightarrow\)\(\Large \rightarrow\)\(\Large \rightarrow\)is the arrangement where C1 gets all 4 presents.

\(\Large \rightarrow\)\(\Large \rightarrow\)\(\Large \rightarrow\)\(\Large \rightarrow\)\(\Large \rightarrow\)\( \Large \Box \)\( \Large \Box \)\( \Large \Box \)\( \Large \Box \) is the arrangement where C6 gets all 4 presents.

\( \Large \Box \)\(\Large \rightarrow\)\(\Large \rightarrow\)\( \Large \Box \) \( \Large \Box \) \(\Large \rightarrow\)\(\Large \rightarrow\)\( \Large \Box \) \(\Large \rightarrow\) means that C1 gets a present, C3 gets 2 presents and C5 gets 1 present.

And so on.... each arrangement of arrows and boxes gives us a different distribution of the presents among the children.

So what we are doing comes down to: out of n+r-1=9 POSITIONS, we are choosing 4 of those positions to have BOXES. The boxes are identical, so it does not matter the order of the boxes in the same slot, hence the formula:

\[\left(\begin{matrix}n+r-1 \\ r\end{matrix}\right)=\frac{ (n+r-1)! }{ r!(n-1)! }\]

Answer 8

I also found this tutorial very helpful:
http://www.mathsisfun.com/combinatorics/combinations-permutations.html

The first sections are pretty basic combination & permutation stuff, but the example down at the bottom for "combinations with repetition" and the ice cream cones was very helpful.