# Counting Number of Digits in Possible Strings

I'm not sure what this type of problem is called or what the nomenclature is to look it up. I'll give a small example to illustrate the problem.

Let $L = \{A,B\}$, an alphabet having only two characters $A$ and $B$.

You must construct a string of length 3 over $L$.

It is easy to see over such a binary alphabet that the total possible strings we can construct is $2*2*2 = 2^3 = 8$.

I can list them out as: AAA, AAB, ABB, ABA, BAA, BAB, BBA, BBB.

Easiest way to see what I want is to sort each string's digits alphabetically to produce:

AAA -> AAA
AAB -> AAB
ABB -> ABB
ABA -> AAB
BAA -> AAB
BAB -> ABB
BBA -> ABB
BBB -> BBB


Then remove duplicates from the sorted list above:

AAA
AAB
ABB
BBB


In other words, only caring about the total number of A's or B's in the resultant string. Here there are four outcomes: (3A 0B, 2A 1B, 1A 2B, 3B 0A)

In my case here this cuts the $2^3$ possibilities in half to $4$. What I'd like to know is if this type of problem has some kind of name or formula for the general case. Where I have an alphabet of $k$ elements and a string of length $n$.

-

This is one form of a stars-and-bars problem. If you have $k$ symbols and a string of length $n$, there are

$$\binom{n+k-1}{k-1}$$

different combinations. One way to look at it is that you’re counting the solutions to the equation

$$x_1+x_2+\ldots+x_k=n$$

in non-negative integers, where $x_i$ is the number of copies of the $i$-th symbol. The explanation at the linked article is pretty clear, but I’ll be happy to expand on it if you have questions.

-
If I have say string length $k=10$ and alphabet size $n=3$, I can see that I have 10 "stars" ★★★★★★★★★★, and I need to place two bars. I see 11 gaps |★|★|★|★|★|★|★|★|★|★|, so I would think it would be $11\choose2$, but by the theorem it ends up being $12\choose2$. I'm sure you're correct, but I'm not fully seeing it. – user17753 Feb 19 '13 at 20:05
@user17753: The $12$ is the total number of symbols, stars and bars both: $10$ stars and $2$ bars make $12$ symbols. The actual combination is determined by which $2$ of those $12$ symbols are bars, and there are $\binom{12}2$ ways to place them. – Brian M. Scott Feb 19 '13 at 20:09