0

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?

Luke Taylor
  • 103
  • Did you mean to say using at most $n$ elements in a combination? – N. F. Taussig May 09 '16 at 23:37
  • @N.F.Taussig Sorry, yes. Already edited. – Luke Taylor May 09 '16 at 23:39
  • @N.F.Taussig I've kind of been stumped from the start. This is just a small problem I faced in a personal programming project, but it's not really programming-related on its own so I think it belongs here. I have only a basic knowledge of mathematics. – Luke Taylor May 09 '16 at 23:45

1 Answers1

2

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)~~~~$.)

Christopher Carl Heckman
  • 4,458
  • What does C stand for? – Luke Taylor May 09 '16 at 23:43
  • 1
    @LukeTaylor : $C(n,r)$ is the notation for the number of subsets of an $n$-element set that have exactly $r$ elements in them. It also is the binomial coefficient ${n\choose r}$ and is also sometimes written as $nCr$. Formula: $\displaystyle C(n,r) = {n! \over r! (n-r)!}$ – Christopher Carl Heckman May 09 '16 at 23:44
  • 1
    @hardmath : The $C(m+r-1,r)$ formula allows repetition of elements. (See https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition ) – Christopher Carl Heckman May 09 '16 at 23:45
  • Perhaps I've misinterpreted the problem. I thought the repetitions were included in the $m=100$ items, and might vary with the distinct items included, e.g. letters of "Mississippi". But if unlimited repetitions of $m=100$ distinct items is envisioned, then I agree your "stars-and-bars" approach will apply. – hardmath May 09 '16 at 23:50
  • I'm interpretting the problem in the following way: Suppose $m=2$ and $n=3$; then (if the set is ${1,2}$), I'm counting the sets $\emptyset$, ${1}$, ${2}$, ${1,2}$, ${1,1}$, ${2,2}$, ${1,1,1}$, ${1,1,2}$, ${1,2,2}$, ${2,2,2}$. – Christopher Carl Heckman May 09 '16 at 23:54
  • @ChristopherCarlHeckman I clarified in my problem. Have I entered this problem correctly into Wolfram|Alpha: http://i.imgur.com/boHqUkr.png? if $m$ is $3549860$ and $n$ is $10$? – Luke Taylor May 09 '16 at 23:59
  • It looks like it. (BTW, the formula above works even if $n>m$.) – Christopher Carl Heckman May 10 '16 at 00:04