Number of combinations with repetition

Question

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

@AndréNicolas, thanks, vote up and if you could add a reply, I will mark it as answer to benefit other people. — Lin Ma, Jun 04 '16 at 00:58

score 1 · Accepted Answer · answered Jun 04 '16 at 01:09

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. :) — Lin Ma, Jun 04 '16 at 01:21

Number of combinations with repetition

1 Answers1