How do I approach this combinatorics question?
In how many ways may we put k identical books onto n shelves, if
each shelf gets at least one book.
I tried drawing this out first, but it's not helping with the bigger numbers. Identical means that order doesn't matter within each shelf, correct?
Best Answer
After you've put the books on the shelves, you can number them from 1 to $n$ according to their placement (first all those on the first shelf, then those on the second etc.). Now the placement (up to permutations of the books, which are ignored) is entirely determined by the set of $k$ numbers identifying the lowest numbered book on each shelf. Moreover that can be any subset of $k$ chosen among the $n$ available numbers, with the sole condition that $1$ must be in the subset. The number of possibilities is therefore the number of ways to choose the remaining $k-1$ numbers among the remaining $n-1$ values; you probably know how to express that number.
To be totally precise, I should add that this analysis fails in one case, namely $n=k=0$ (there is one solution, but there is no way to choose $-1$ elements out of a collection of $-1$; binomial coefficients with a negative lower index are always taken to be $0$). This is one reason that can be given for using a special notation for these "multiset numbers", rather than using an expresion involving a binomial coefficient. The notation that some use for the answer to this question is $$ \left(\!\binom k{n-k} \!\right) $$ indicating that among $k$ different values available (the numbers of the shelves) one has to choose a multiset of $n-k$ elements (the places actually occupied by books, not counting the first one for each self which is obligatory), where each value (shelf) can be chosen $0$, $1$, $2$, or more times (which is the meaning of "multi" in multiset). See also multiset number and counting surjective functions.