0

I was doing a question where I was distributing $15$ identical candy to four people, with the restriction that a specific person had at most 4 candy.
I did this in two ways: first way by subtracting the ways of having at least 5 candy for that person from the number of total unrestricted ways.
The second way was by counting the number of ways I can distribute the candy after giving that special person only 0 candy, 1 candy, ..., 4 candies.

Then I saw that it could be generalised to form some sort of identity by counting:
Number of non-negative integer solutions to
$$x_1+x_2+\ldots+x_m = n$$
where $m\leq n$, $x_i \geq 0$ for $i=1,2,\ldots,m-1$ and $x_m\geq a$ for $a<n$.

The first method I counted
$$\binom{n+m-1}{m-1} - \binom{n+m-a-2}{m-1}$$ and the second method I counted
$$\sum_{k=0}^a \binom{n+m-2-k}{m-2}.$$

Then $$\sum_{k=0}^a \binom{n+m-2-k}{m-2}=\binom{n+m-1}{m-1} - \binom{n+m-a-2}{m-1} .$$ Could this possibly be generalised even more and is this already a known identity?

Natash1
  • 1,359
  • 9
  • 23
  • One way that you could think about, is having more "special" people, who get atmost some number of candies. This definitely would lead to a generalization. – Sarvesh Ravichandran Iyer Nov 11 '17 at 04:08
  • What about using inclusion-exclusion principle or generating functions? – Bergson Nov 11 '17 at 04:10
  • 1
    "*Is this already a known identity?*". Almost certainly. At a glance, it looks like just a special case of the [hockey-stick identity](https://math.stackexchange.com/questions/1490794/proof-of-the-hockey-stick-identity-sum-limits-t-0n-binom-tk-binomn1) and pascal's identity. – JMoravitz Nov 11 '17 at 04:15

0 Answers0