Puzzles/Statistical puzzles/Summing n/Solution

< Puzzles < Statistical puzzles < Summing n

The solution is easily found if the problem is restated graphically. Consider n=3, k=2. Possible sums are 3 = 0+3, 3 = 1 + 2. A graphical representation could be:

||ooo
|o|oo

, respectively, with the bars representing seperations between the summands and 'o's representing the value of the summands. Then obviously the problems is equivalent to finding the number of ways to distribute $k - 1$ bars among $n + k - 1$ slots, since we need only $k - 1$ bars to partition the space into $k$ summands. Therefore the solution is $N = {n+k-1 \choose k-1}$ , if $N$ denotes the number of unique sums.

For the next part, set aside $k$ 'o's since each partition has to have atleast $1$ 'o'. Now the problem reduces to the previous one with a reduced value of $n$ i.e. $n-k$ . So the solution is

$N = {n-k+k-1 \choose k-1} = {n-1 \choose k-1}$ ,

if $N$ denotes the number of unique sums.

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.