2
$\begingroup$

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?

  • 2
    Please explain what part of the Wikipedia sections ([here](http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition) and [here](http://en.wikipedia.org/wiki/Multiset_coefficient#Counting_multisets)) on counting multicombinations you don't understand; otherwise we'd just be rewriting them for you from scratch.2012-09-18

2 Answers 2

4

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.)

  • 0
    It took me a while, but it's starting to make sense now. Thank you!2012-09-18
0

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)