5
$\begingroup$

So I was in class discussing the following problem:

We have $20$ different presents to distribute to $12$ children. It is not required that every child get something; it could even happen that we give all the presents to one child. In how many ways can we distribute the presents?

After some discussion we realized that the answer was $12^{20}$, because the problem could only be solved if we saw this from the perspective of the presents and not from the children. I thought it was very cool.

Then I went home and thought of a corollary to the problem: how many ways are there so that each child gets at least one present? I have been thinking for a week and I cannot solve it. I thought it was $12^{12} \times 12^8$, the first number to represent the presents distribute to at least one child and the other the ones spread out without discrimination. However, that number is bigger than the original number of ways which makes no sense. How would you go about solving this?

$\endgroup$
1

3 Answers 3

Reset to default
4
$\begingroup$

As you observed, there are $12^{20}$ ways to distribute the presents without restriction. There are $\binom{12}{k}$ ways to exclude $k$ of the recipients from receiving a present and $(12 - k)^{20}$ ways to distribute the presents to the remaining $12 - k$ people. By the Inclusion-Exclusion Principle, the number of ways to distribute the presents so that each person receives at least one is $$\sum_{k = 0}^{12} (-1)^k\binom{12}{k}(12 - k)^{20}$$

$\endgroup$
6
  • 1
    $\begingroup$ This is one of the forms described by The Twelvefold Way, which collects twelve common counting problems. $\endgroup$
    – Dan Uznanski
    Commented Oct 3, 2017 at 2:29
  • 2
    $\begingroup$ I can't figure out where you got the $(-1)^k$ from. Edit: Oh, is it because each way you can exclude 11 people is also a way you can exclude 10 people, 9 people, etc.? $\endgroup$
    – Wildcard
    Commented Oct 3, 2017 at 3:41
  • 2
    $\begingroup$ @wildcard yes. Since "excludes Alice and Bob" is part of both "excludes Alice" and "excludes Bob", taking out both of those has taken out the first thing twice, which is one time too many. $\endgroup$
    – Dan Uznanski
    Commented Oct 3, 2017 at 5:18
  • $\begingroup$ @DanUznanski wait, could you explain that for me? I don’t understand why you wouldn’t always subtract instead of alternating. What’s different about excluding even numbers of people that makes it positive instead of negative? The whole thing makes sense intuitively to me, I just can’t iron out the details in my head. $\endgroup$
    – NeonCop
    Commented Oct 4, 2017 at 16:16
  • 2
    $\begingroup$ Without restriction, the original $12^{20}$ has segments for "excludes noone", "excludes just Alice", "excludes just Bob", and "excludes both". by deleting "excludes Alice" we get rid of "excludes just Alice" and "excludes both"; by deleting "excludes Bob" we get rid of "excludes just Bob" and "excludes both" - but we only really want to delete "excludes both" once, and we've deleted it twice now, so we have to add it back in. This continues down the line - for "excludes these three people" we've now deleted it 3 times and added it 3 times, so we have to delete it one more time. $\endgroup$
    – Dan Uznanski
    Commented Oct 4, 2017 at 17:16
1
$\begingroup$

Here is a way to solve the problem using exponential generating functions. Observe that $$ F(x)=(e^x-1)^{12}=\left(x+\frac{x^2}{2!}+\dotsb\right)^{12}=\sum_{n=0}^{\infty}\left(\sum_{k_i>0} \binom{n}{k_1, k_2, \dotsc,k_{12}}\right) \frac{x^n}{n!} \tag{1} $$ Hence we seek the coefficient of $x^{20}/20!$ in the RHS of (1). But we also have that $$ F(x)=(e^x-1)^{12} =\sum_{k=0}^{12}\binom{12}{k}(-1)^k e^{(12-k)x} =\sum_{k=0}^{12}\binom{12}{k}(-1)^k\left(\sum_{m=0}^{\infty} (12-k)^m\frac{x^m}{m!} \right) \tag{2} $$ by the binomial theorem. In particular the coefficient of $x^{20}/20!$ in the RHS of (1) and thus the number of ways is $$ \sum_{k=0}^{12}\binom{12}{k}(-1)^k (12-k)^{20}. $$

$\endgroup$
0
$\begingroup$

It is actually quite a bit more simple than the previous posters have mentioned - no need to use the binomial and you will end up with a correct answer if you do

I believe the correct answer is

(k-1)C(n-1) thus 19 choose 11

$\endgroup$
4
  • $\begingroup$ Can you explain why this is the correct answer? $\endgroup$
    – Air Conditioner
    Commented Jan 21, 2018 at 22:53
  • $\begingroup$ Yeah because its really 19 choose 11 * 1 choose 1. $\endgroup$
    – mbillion
    Commented Jan 22, 2018 at 23:48
  • $\begingroup$ the term n-1 occurs because you only require 11 partitions, n=12, and n-1=11; i.e. you only need 11 partitions to make 12 seperate groups. the k-1 term is a bit trickier. But essentially you have 11 gifts where the placement matters 11 gifts for which you must give one to each child, doesnt matter which one, but they each get one. Then 9 gifts where you can give them to anyone you want. if you do those two scenarios out long form, and expand the result is (k-1)C(n-1) for all problems of this "every bucket gets one ball" variety $\endgroup$
    – mbillion
    Commented Jan 23, 2018 at 0:08
  • $\begingroup$ 12 choose 12 then equals 1. You are then left with partition theory 9 balls and 11 partitions. 9+11-1=19 and 12-1=11 thus 19 choose 11 per any fundamental probability texts partition equations $\endgroup$
    – mbillion
    Commented Jan 23, 2018 at 0:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .