How many ways to distribute 5n candies to n children, whereby no children can recieve more than 5?

117 Views Asked by At

To note, the candies are indistinguishable and the children are distinguishable. Also as the title states, the only restriction is that limit to which a child can receive. In fact, a child can receive none, and not all the candies need to be given out. I've done similar problems, such as (1) where all the candies have to be given out but with no restrictions, and (2) all the candies are given out with a minimum.

But for this specific problem where do I even begin?

2

There are 2 best solutions below

2
On BEST ANSWER

There are six different number of candies that can be given to a particular child, and the number of candies each child receives is independent of other children. So it's just $6^n$.

If you want to be a bit fancier, clearly $f(1)=6$. If you add a $n+1th$ child and give them $k$ candies, then you have $5(n+1)-k$ candies to distribute among $n$ children. If $k<6$, then $5(n+1)-k\geq 5n$. The number of ways to distribute more than $5n$ candies among $n$ children is the same as the number of ways to distribute $5n$ (since each child gets at most 5, you are giving out at most $5n$). So for each number of candies given to the $n+1th$ child, there are $f(n)$ distributions, for a total of $f(n+1)=6f(n)$. By induction, $f(n)=6^n$.

If you want to be really fancy, there's Mike Earnest's answer.

0
On

Hint: Let $E$ be the set of ways to give the $5n$ candies to the $n$ children, without the $5$ candy limit. First, figure out how to count the number of elements of $E$, using stars and bars.

Next, let $E_i$ be the set of distributions in $E$ where child number $i$ receives more than $5$ candies. These are the bad sets you need to subtract out. Specifically, you need to compute $$ |E|-\Big|\bigcup_{i=1}^nE_i\Big| $$ To compute the size of the union, use the principle of inclusion-exclusion. In the process of this, you will need to compute the sizes of the intersections $|E_{i_1}\cap E_{i_2}\cap \dots \cap E_{i_k}|$, which can be done with a modification of the method used to compute $|E|$.