Given a set of $m$ unique elements to choose from, and using at most $n$ elements in a combination, how many combinations can I have? A combination can repeat an element more than once, as long as the number of items does not exceed $n$ elements. Order of elements does not matter.
For example, say I have $100$ elements, and I want to find out how many combinations I could make of $10$ elements or fewer, if a combination can include repeats?
$\endgroup$ 31 Answer
$\begingroup$If the order doesn't matter, then you need the fact that the number of ways to choose $r$ objects from a set of $m$ is $C(m+r-1,r)~~$. Then your answer will be $$\sum_{i=0}^n C(m+i-1,i).$$ (This is an abbreviation for $C(m+0-1,0) + C(m+1-1,1) + \cdots + C(m+n-1,n)~~~~$.)
$\endgroup$ 7
