1
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ Thanks AndréNicolas, vote up and mark your reply as answer. :) $\endgroup$
    – Lin Ma
    Jun 4, 2016 at 1:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .