Let '$n$' be the number of trials. Let '$o$' be the number of outcomes for each trial. Let '$a$' be the first outcome for each trial, let '$b$' be the second, '$c$' the third, etc.

How many combinations (not permutations) are there of $a, b, c, d$ (and so on) when only '$o$' and '$n$' are defined?

Let '$x$' be the number of combinations. Let '$y$' be the number of permutations.

For example, when $o = 2$ and $n = 2$ the four permutations are: $aa, ab, ba, bb$. The number of permutations ($y$) is always $o^n$ (which here is $y = 2^2 = 4$).

But there are three combinations: two $a$'s, an $a$ and a $b$, and two $b$'s (where $ab$ and $ba$ are one combination but two permutations).

For more examples of $o$ and $n$:

  • $o=2,\, n=3,\, y=8,\, x=4\qquad (aaa, aab, abb, bbb)$
  • $o=2,\, n=4,\, y=16,\, x=5\quad\:\: (aaaa, aaab, aabb, abbb, bbbb)$

So when $o=2$, $y=o^n$ and $x=n+1$ But when $o\gt 2$, I don't see a pattern or formula and I don't see the ${}^n\text{C}_r$ formula helping at all.

So for more examples of $o$ and $n$:

  • $o=3,\, n=2,\, y=9,\, x=6\qquad (aa, ab, ac, bb, bc, cc)$
  • $o=3,\, n=3,\, y=27,\, x=10\quad (aaa, aab, aac, abb, abc, acc, bbb, bbc, bcc, ccc)$
  • $o=3, n=4, y=81, x=15\:\:\:\:\:\: (aaaa, aaab, aaac, aabb, aabc, aacc, abbb, abbc, abcc, accc, bbbb, bbbc, bbcc, bccc, cccc)$

So it looks like when $o=3$, $x = (n+1)+(n)+(n-1)+(n-2)+...+3+2+1$. That's the sum of all natural numbers up to $n+1$ which would just simplify to $\frac{1}{2}(n+1)(n+2)$.

I don't know how that links to when $o=2$, but I'll continue. The $n+1$ is still there but now that $o=3$ there's an $n+2$ so I'll assume that when $o=4$ then there'll be an $n+3$. If that's the case then it would seem that each time another number is being multiplied and that new number is $o-1$ as $o$ increases. Which could be rewritten as $(n+(o-1))(n+(o-2))...(n+1) = (n+o-1)!/n!$. And since there's now a $1/2$ in front of the equation when $o=3$, I'd guess that when $o=4$, the number in front (regardless of $n$) would be either $1/3$ or $1/3!$. Which means overall the equation would either have a $1/(o-1)$ or a $1/(o-1)!$ in front of it.

So for more examples of $o$ and $n$:

  • $o=4,\, n=2,\, y=16,\, x=10\qquad (aa, ab, ac, ad, bb, bc, bd, cc, cd, dd)$
  • $o=4,\, n=3,\, y=64,\, x=20\:\:\:\:\:\:\: (aaa, aab, aac, aad, abb, abc, abd, acc, acd, add, bbb, bbc, bbd, bcc, bcd, bdd, ccc, ccd, cdd, ddd)$

It looks like both of these examples apply to $(1/(o-1)!)((n+o-1)!/n!)$.

And that simplifies to $\binom{n+o-1}{n}$ ... what?

So I guess my question has now changed to, can someone confirm this (that I haven't made a mistake or it doesn't apply to greater values) and why is this the case?

  • 2
    $\begingroup$ Please see the help menu for a guide on how to typeset math on this site. $\endgroup$ – joriki Jul 26 '18 at 13:07

What you have deduced is correct:

$$\#(\text{choices with repeats allowed})= \binom{n+o-1}{n}\, .$$

See this by establishing the $o$ categories (bins) separated by $o-1$ bars '$\mid$' and placing $n$ balls '$\bullet$' in those bins, e.g.

$$\begin{array}{ccccccc}a && b && c &&\cdots\\ \bullet\bullet &\mid& \bullet &\mid & \bullet\bullet\bullet &\mid &\cdots\end{array}$$

gives a combination with repeats allowed:

$$aabccc\cdots\, .$$

Now you can see that each placement of balls in bins will yield a selection with repetition and vice versa.

Also you can see that a placement of balls in bins is just an arrangement of $o-1$ identical bars and $n$ identical balls, there are clearly


such arrangements.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.