Combination with Repetitions Including Duplication of N Value

Question

Is a Combination with Repetition the correct term for the following problem

N - Letters a, b, c
R - 2

Example Result should equal

aa
ab
ac
bb
ba
bc
cc
ca
cb

Total Results: 9

However, in using every online calculator for combinations with repetitions I receive a total result of 6.

Example calculator: Combination with Repetition Calculator

What is the correct term for the mathematical equation / formula that I am looking for the accomplish the example data set provided from the variables presented?

Thanks!

Answer 1

Assuming you are not limited in the number of each letter which appears and you are asking how many ways you can have a total of $r$ letters appearing (with possible repitition) in a specific order (i.e. "baa" is considered different from "aba" and different from "aab"), this problem is often worded as

"Find the total number of strings of length $n$ from an alphabet with $r$ characters available."

Alternatively, one can think of this as "Find the number of functions from the set $\{1,2,\dots,n\}\to\{1,2,\dots,r\}$"

In either case, the result will be $r^n$.

This can be seen using multiplication principle.

• Pick what the character in the first slot is (equivalently pick what $f(1)$ is).
• Pick what the character in the second slot is
• $\vdots$

In each step there are $r$ possibilities. There are a total of $n$ steps. Multiplication principle says that to get the total number of possibilities, we multiply the number of options at each step, giving a total of $r^n$

---

The calculator you link to answers a related but different question. How many multisets of size $r$ exist with $n$ elements available to choose from?

Equivalently, how many integer solutions are there to the system $\begin{cases} x_1+x_2+\dots+x_n=r\\x_i\geq 0\end{cases}$

Equivalently, how many strings of length $r$ where letters must appear in alphabetical order exist taking characters from a set with $n$ characters available.

Equivalently, how many strings of length $r$ taking characters from a set with $n$ characters available exist where order of characters doesn't matter. (i.e. $ab$ is considered the same as $ba$)

This can be seen via stars and bars to be $\binom{n+r-1}{r}$

In the example in the original post, the possibilities are aa, ab, ac, bb, bc, cc for a total of $6$ possibilities. (ba, ca, and cb were not included since they are already in the list written as ab, ac, and bc respectively)