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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


Then remove duplicates from the sorted list above:


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|cite|improve this question
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


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


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|cite|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

Your Answer


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.