How many ways can we write $N$ as a sum of $K$ strictly positive numbers

combinatoricsinteger-partitions

I know this has been asked before, but most existing answers have been in the form of summations instead of framing this as a stars and bars problem as taught in class.

We were given that the answer is ($n-1$ choose $k-1$), as in $n-k$ stars and $k-1$ bars, but I'm having trouble seeing why the former is the case.

[Edit] This is what I have tried so far: I know that we can make each of the positive numbers into k bins, thus there will be k-1 bars when framing it into a stars and bars problem.

However, when it comes to the n-k stars, the only explanation I can think of is subtracting k (the value we first chose) from n to find the remaining value we need to account for, but I don't think this makes sense. Any help on figuring out why it is n-k stars would be appreciated!

Best Answer

Stars and bars was evolved as a graphical method for easily understanding

Suppose the upper face of ten dice placed on a table show all $6$ numbers appearing at least once: one $1$, one $2$, one $3$, four $4's$, one $5$, and two $6's$

This result could be depicted as $\Large{\;\;\star|\star|\star|\star\star\star\star|\star |\star\star\;\;}$

Make two notes:

  • Only $5$ dividers (bars) are needed to depict $6$ "bins"

  • Since no bin can be empty, no two bars can be adjacent, and the bars must lie between the first and last star

  • It follows that the # of ways for all possible ways of getting a sum of $10$ $=\Large{\binom{10-1}{6-1}}$

  • And in general, $\Large{\binom{n-1}{k-1}}$ where n stars are to be put into k bins

ADDED

If you so prefer, instead of the $10$ stars depicted, you could instead write $x_1+x_2+x_3+x_4+x_5+x_6 = 10,$ over positive integers. The $+$ signs then serve as the $5$ bars

Also note that here we are not counting the sum of $10$ die throws; each die is one object, and we are counting the number of ways die faces may show in $10$ throws

NOTE

For the difference between a "stars and bars" count, and a multinomial coefficient count, look here

PS

If you see the Wikipedia page, there are two formulas with two theorems, but since $(n-k)$ stars was troubling you, and you want to carry only one formula in your head, viz $\large\binom{n+k-1}{k-1}$, a simple ruse is to put one star each in each bin, so now there are only $(n-k)$ non-negative integers to deal with, and you can then use $\large\binom{n+k-1}{k-1}$

Related Question