# Number of combinations with repetition

For normal combination, which subset is unique, there is a requirement $k{\le}n$, wondering for combination with repetition, I think there is no such requirement, and $k$ could be greater than n, correct? Thanks. ${}{}{}{}{}$

Here is what context I am referring to,

https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition

thanks in advance, Lin

• Your observation is correct. Jun 4, 2016 at 0:56
• @AndréNicolas, thanks, vote up and if you could add a reply, I will mark it as answer to benefit other people. Jun 4, 2016 at 0:58
• Thanks Arbuja for the edit. :) Jun 6, 2016 at 2:36

## 1 Answer

Your observation is correct. To count the $k$-multisets, that is, combinations with possible repetition, where the objects are taken from a set with $n\ge 1$ elements, we are in effect counting the number of solutions of $x_1+x_2+\cdots+x_n=k$ in non-negative integers. The only restriction on $k$ is that it be non-negative. In particular, we can have $k\gt n$.

By a Stars and Bars argument, the number of such multisets is $\binom{n+k-1}{k}$, or equivalently $\binom{n+k-1}{n-1}$.

• Thanks AndréNicolas, vote up and mark your reply as answer. :) Jun 4, 2016 at 1:21