Distributing $15$ candies to $5$ children with restriction

Question

Suppose you want to distribute $15$ candies to $5$ different children.

(a) In how many ways can this be done if no kid receives more than $6$ candies?

(b) In how many ways can this be done if each child ends up with a different number of candies?

We already determined that the number of ways of distributing the candies to the $5$ children such that each child gets at least one piece is $1,001$ ways.

How do we take care of the restriction of each child receiving no more than $6$? Can we take the complement and subtract the number of ways a child receives $7-15$ pieces? Or would this be a long, unnecessary attempt?

My attempt:

Consider the complement where one kid receives at least $7$ candies.

Step $1$: Choose the child to receive $7$ candies and give him/her the $7$ candies: $5$ choices

Step $2$: Distribute the remaining $15-7=8$ candies to the $5$ children.

There are $\binom{8+4}{4}=\binom{12}{4}=495$ ways to do this.

So there are $5\cdot 495=2,475$ ways to distribute the candies such that one child receives at least $7$ candies.

There are $\binom{15+4}{4}=\binom{19}{4}=3,876$ ways to distribute the candies with no restriction.

So there are $3,876-2,475=1,401$ ways to distribute the candies such that no child receives more than $6$ candies.

Answer 1

Due to the particular values chosen for this problem, it is not too hard to do this by taking the complement, though it gets more difficult in general. For each of the $5$ children, consider the case where that child gets at least $7$. We want to compute the size of the set $S_i$, for $1\leq i\leq 5$, for each of the children. Once you give $7$ to child $i$, you can then count weak compositions of the remaining $8$ into $5$ parts using stars and bars.

Then, for each of the $5$ children, we've counted the number of ways that child $i$ gets at least $7$ pieces, which we put in the set $S_i$. If we subtract these from the total number of distributions without restriction, we get our desired number. But, there is a problem- what if a distribution that gives child $i$ at least $7$ pieces also gives child $j$ at least $7$ pieces? Then we would count it once in $S_i$ and again in $S_j$, meaning that we subtract it twice from the total number of distributions, which would be wrong. That means you would have to add back the number of distributions that give two different children at least $6$ pieces, so that you don't double count your bad cases.

Answer 2

(a) Consider in the ring $\Bbb Q[x]/x^{16}$ the following product of five equal factors: $$ \left(\ x+x^2+x^3+x^4+\dots+x^{15}+O(x^{16})\ \right)^5\ . $$ The coefficient $C$ of $x^{15}$ in this product is exactly the number of possibilities to partition $15$ in five parts $\ge 1$. (We use generating polynomials / series.)

We "simplify" with $x^5$ and search the coefficient $C$ of $x^{10}$ in $$ \left(\ 1+x+x^2+x^3+x^4+\dots\ \right)^5=\frac 1{(1-x)^5}\ . $$ We use here formal power series or polynomials modulo some suitable $O$ of some power of $x$.

This can be computed by starting with $(1-x)^{-1}=1+x+x^2+x^3+\dots$, and we apply the formal derivative four further times. The coefficient in degree $10$ comes from the one in degree $14$, so it is $C=(14\cdot 13\cdot 11\cdot 10)/(-1)(-2)(-3)(-4) =\binom{14}4$. As in the OP. So far nothing new.

---

To get the number $C'$ of partitions with at most $6$ candles consider instead: $$ \left(\ x+x^2+x^3+x^4+x^5+x^6\ \right)^5\ . $$ and isolate the coefficient of $x^{15}$ in it. Equivalently, find the coefficient of $x^{10}$ in $$ \left(\ 1+x+x^2+x^3+x^4+x^5\ \right)^5=\frac {(1-x^6)^5}{(1-x)^5}\ , $$ which is $$ \Big[\ 1-5x^6+\dots\ \Big] \left[\ \binom 44 + \binom 54 x + \binom 64 x^2 + \binom 74 x^3 + \binom 84 x^4 + \dots + \binom {14}4 x^{10} +\dots\ \right] $$ The coefficient we need is $C'=\binom {14}4-5\binom 84=651$. Again, same as in the OP, after the following small correction.

Step 1 is choosing the one child that becomes $6+$ at least one further candy. So we have to distribute "in the same conditions" the $15-6=9$ further candies. This leads to the binomial coefficient $\binom{9-1}{5-1}$, in the same manner as for the total we have $\binom{15-1}{5-1}=1001$ possibilities.

Check with sage:

sage: R.<x> = QQ[]
sage: P = ( x + O(x^16) ) / (1-x)
sage: P^5 + O(x^16)
x^5 + 5*x^6 + 15*x^7 + 35*x^8 + 70*x^9 + 126*x^10 + 210*x^11 + 330*x^12 
    + 495*x^13 + 715*x^14 + 1001*x^15 + O(x^16)
sage: Q = ( x + O(x^16) ) * (1-x^6) / (1-x)
sage: Q
x + x^2 + x^3 + x^4 + x^5 + x^6 + O(x^16)
sage: Q^5 + O(x^16)
x^5 + 5*x^6 + 15*x^7 + 35*x^8 + 70*x^9 + 126*x^10 + 205*x^11 + 305*x^12 
    + 420*x^13 + 540*x^14 + 651*x^15 + O(x^16)

(Results were manually broken to fit in the width.)

---

(b) Note that the minimal sum of five different positive integers is $$1+2+3+4+5=15\ .$$