In combinatorics, there is a formula "$n$ multichoose $k$", which is the way of making a multiset having $k$ elements choosing out of $n$ options. "$n$ multichoose $k$" is the same as "$(n+k-1)$ choose $k$". Why is that?

  • $\begingroup$ Just to clarify, are you asking in how many $k$ objects can be selected from a multiset containing $n$ different types of objects? $\endgroup$ – N. F. Taussig Jun 26 '15 at 21:18
  • $\begingroup$ See mathworld.wolfram.com/Multichoose.html $\endgroup$ – Amy B Jun 26 '15 at 21:25
  • 1
    $\begingroup$ See Theorem Two here; the explanation is quite clear. $\endgroup$ – Brian M. Scott Jun 26 '15 at 21:28
  • $\begingroup$ @Taussig: what I have in mind is wolfram's example, someone who wants 5 pinches out of 9 spices $\endgroup$ – user207032 Jun 26 '15 at 22:00
  • $\begingroup$ Somehow I explained where the formula comes from in an answer to this question. It is not a proof but rather the intuition. $\endgroup$ – Carlos Mendoza Nov 25 '15 at 12:56

Let's say you have $N$ items (all alike for now) and $K-1$ vertical bars (all alike for now).

How many unique ways can you line up the $N$ items and the $K-1$ vertical bars?

Now pretend that everything to the left of the first bar is Type $1$, everything between the first and second bar is Type $2$ ... and everything to the right of the last $(K-1)$th bar is Type $N$.

Do you see the connection?

  • $\begingroup$ I have seen this argument before, but it still isn't clear to me. I am learning from Ardila [link]youtube.com/… and he gives a proof from 5:30 from 7:30. Claiming a bijection between multichoose and weak compositions. Nevertheless, this bijection is not very clear to me $\endgroup$ – user207032 Jun 26 '15 at 22:03

Your Answer

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