[Math] Number of ways to distribute $N$ coins among $M$ people, when each person can only have a maximum of $C$ coins

combinationspermutations

A person can however receive $0$ coins.
Example – Number of ways of distributing $3$ coins among $2$ people such that no person receive more than $2$ coins is $2$.

My approach –
For a simpler version if we do not have restriction of each person having a maximum of C coins.

We know that $$ \sum coins(\{ (c_1,…,c_M) \}) = N $$

Then Number of ways to distribute N coins among M people will be $$ {{N+M -1}\choose{M-1}} $$

I fail to understand how to include restriction of each person having having a maximum of C coins.

Best Answer

This answer is actually incorrect, but I will leave it here in case anyone makes the same mistake I did in reasoning this out. Take a look at saulspatz's response for the right answer :)


I am assuming that $N<MC$, otherwise there are zero ways.

The idea is the following: first give each person $C$ coins, and then take away $MC-N$ coins by choosing from the $M$ people with repetition allowed and order not important.

This corresponds to the number $\big(\!\!\binom{M}{MC-N}\!\!\big) = \binom{M+MC-N-1}{MC-N}$, where $\big(\!\!\binom{n}{k}\!\!\big)$ denotes multichoose.

Related Question