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?

  • 3
    $\begingroup$ You can do this using the stars and bars approach. $\endgroup$ – joriki Feb 22 '12 at 7:36
  • $\begingroup$ Yes, identical means that the order within a shelf doesn’t matter. @joriki’s link tells you everything that you need to know; assuming that you solve the problem, you might write up your solution here and (after a few hours) accept it yourself. $\endgroup$ – Brian M. Scott Feb 22 '12 at 8:03
  • $\begingroup$ @joriki - if you turn your comment into an answer, I will upvote it. $\endgroup$ – user22805 Feb 22 '12 at 9:55
  • $\begingroup$ @David: Thanks, but I'm not sure it would be appropriate for just a name and a link. $\endgroup$ – joriki Feb 22 '12 at 10:14

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.

| cite | improve this answer | |
  • $\begingroup$ What's wrong with $\binom{-1}{-1}$? You can cancel the two $-1!$s to get $\frac{1}{0!}$ (and Wolfram Alpha agrees that this is ok, so I'm not entirely alone). $\endgroup$ – Peter Taylor Feb 22 '12 at 9:27
  • 1
    $\begingroup$ @PeterTaylor: Since $(-1)!$ is undefined, or infinity if you like, cancelling two of them makes no sense. The most common and useful convention for extending binomial coefficients is to define $\binom\alpha k=0$ when $k$ is a negative integer, regardless of $\alpha$. What computer algebra software does is not authoritative; their authors don't care much since few people will actually will use negative $k$ in order to obtain $0$. But mathematically one wants Pascal's rule to hold: $1=\binom00=\binom{-1}{-1}+\binom{-1}0$, so the two binomial coefficients on the right cannot both be $1$. $\endgroup$ – Marc van Leeuwen Feb 22 '12 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.