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?
Best 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.