# How do I prove the formula for multichoose?

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?

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