Problem Statement:
Given $M$ different numbers, I want to get $N$-sized ($N>M$) combinations by choosing from these numbers. How many different combinations are there for this problem?
Example:
Given numbers $1$ and $2$ ($M = 2$) and $N = 3$, the possible combinations are:
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
My Question:
I know the result is $N + M - 1 \choose M - 1$, but why? How to derive this formula?
Any explanations or suggestions would be appreciated.
This is a standard Stars and Bars problem. The Wikipedia article linked to is quite thorough.
The basic idea is that we think of the number $N$ as the number of identical candies. The different numbers $1$ to $M$ are kids. Your problem is equivalent to the problem of counting the number of ways to distribute $N$ candies among these $M$ kids. Some kid(s) may get no candies.
To use your example, $1,1,1$ means Kid $1$ got all the candies, and $1,1,2$ means Kid $1$ got $2$ candies and Kid $2$ got $1$.
It is easier, except for the crying, to count the number of ways to distribute $N+M$ candies among $M$ kids, at least one candy to each kid, and then take away a candy from each kid.
To count this, we line up the $N+M$ candies like this: $$ C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad C\quad$$
This determines $N+M-1$ intercandy gaps. We choose $M-1$ of these gaps to put a separator into. Then we give all the candies up to the first separator to Kid $1$, the candies from the first separator to the second to Kid $2$, and so on. Each choice of where to put separators gives us a way to distribute the candies among the kids, at least one to each. And each way to distribute the candies, at least one to each, determines where to put the separators.
The number of ways to choose $M-1$ gaps to put separators into from $N+M-1$ gaps is $\binom{N+M-1}{M-1}$.
