# Combinations Of Several Trials

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?

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

## 1 Answer

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

$$\frac{(n+o-1)!}{n!(o-1)!}=\binom{n+o-1}{n}$$

such arrangements.