Lesson 2

It will be convenient for us to solve this problem in terms of coins (this way the solution will be more visual). We will place our \(k\) coins in a row and agree that first we give some coins to the first person, then some to the second, then to the third, and so on. To visually mark how many coins each person gets, we will place dividers between them. In the example below, ten coins are divided among six people: the first gets all the coins before the first divider (four coins), the second gets all the coins between the first and second (one), the third gets the coins between the second and third (none), the fourth gets the coins between the third and fourth (three), the fifth gets the coins between the fourth and fifth (two), and the sixth gets all the coins after the fifth divider (none).

It remains to notice that such a configuration is simply a word of length \(n+k-1\) in the alphabet \(\{\text{coin}, \text{divider}\}\), in which there are exactly \(n-1\) dividers and \(k\) coins (or simply binary words of length \(n+k-1\), in which there are exactly \(k\) zeros: these coins and dividers are specially made to resemble zeros and ones). It is easy to see that such words are in one-to-one correspondence with all combinations with repetition. Therefore, their number is \[\binom{n+k-1}{k}=\binom{n+k-1}{n-1}\ .\]

If it is additionally required that each person gets at least one coin (or even more generally: each person gets no fewer than some specified number of coins), then we just give one coin to each person, after which there will be \(k-n\) coins left and we are left with the previous problem. Therefore, the answer is \(\binom{k-1}{n-1}\). This answer also has a natural physical interpretation: there are \(k\) coins, but each person must now receive at least one coin, so all the dividers must be in different places and cannot be located at the edges (left or right of all the coins); thus, we need to place \(n-1\) dividers in \(k-1\) positions.