intuition on multicombinations in combinatorics I do not understand the formula for multicombinations:
Multicombination$(n, k)$ = Combination$(n+k-1, k)$
What is the intuition and maybe even proof behind this formula?
 A: Nothing new here, but maybe this helps you understand.
Suppose you must choose, with repetition allowed, $k$ items from $n$ allowed options. You could perform this choice by considering the options in order, at each point making the choice between "take one more of this option" and "pass to the next option" (in the former case you stay at the same option, in the latter case you go definitively past it). You must choose the possibility "take one" exactly $k$ times, and the possibility "pass on" exactly $n-1$ times. In the end you've had a choice $k+n-1$ times, out of which the first possibility must have been chosen $k$ times, for a total of $\tbinom{k+n-1}k$ different possible outcomes.
(Maybe you find the word "choice" confusing, since if at some point you have exhausted either your $k$ times "take one" or your $k+n-1$ times "pass on", then no real choice is left. However, this is not different from what happens when you are choosing $k$ out of $n$ objects without repetition allowed, considering the objects one by one.)
A: Consider this concrete question: what's purchase options to pick k donuts out of n donuts options in the menu?
To solve it, we assume each donut is considered and the consideration is in order from donut1, donut2, ... donut n. A valid purchase option is a sequence of choices we made which meets the following requirement:


*

*We should have made n - 1 choices to pass to the next donuts

*We should have made k choices to pick the one under consideration
(This is the same concept as star & bar representation: * - pick choices / | - pass choices.)
So the problem is transformed into how many are unique valid sequences of choices? Let's compute that. 
There are P(n - 1 + k) permutations for valid sequence of choices. 
We don't care the order for the "pass" choices and we
don't care the order for the "pick" choices. Because they represent the same "purchase solution". For example, the following is the same

{pick1, ..., pick2, ..., pass1, ..., pass2, ..., pass3} 
{pick2, ..., pick1, ..., pass1, ..., pass2, ..., pass3}
{pick1, ..., pick2, ..., pass3, ..., pass2, ..., pass1}
...

So the total number of valid choices are:
P(n - 1 + k) / (P(n - 1) * P(k))
which equals to
P(n - 1 + k) / (P(n - 1 + k - k) * P(k))
and finally
C(n - 1 + k, k)
