Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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