# How can I find how many unique strings there are with an equal numbers of elements, given a string length and number of elements to choose from?

The question is all in the title. Here's an example:

Elements: A, B; Length: 4:

AABB
ABAB
ABBA
BABA
BBAA
BAAB


There are 6 such unique strings for 2 elements and length 4.

(I discovered this question when working out the performance of some graph theory algorithms. Please let me know if it's a duplicate! The specific problem I'm working on only has two elements in the strings, but I thought the general case would make a more interesting question.)

• It should be mentioned that the special case of two elements in a string of length $2n$ has the answer $\binom{2n}{n} = \frac{(2n)!}{n!n!}$. The generalized form is correctly given below. In the case of $2n=4$ this is $\binom{4}{2} = \frac{4!}{2!2!} = \frac{4\cdot 3\cdot 2\cdot 1}{2\cdot 1\cdot 2\cdot 1} = 6$ May 24, 2015 at 0:23

Suppose you have $n$ elements $A, B, C...$ and $m$ of each. Then the length of the string has to be $nm$.
So the number of permutations, i.e. strings, is $$\frac{(nm)!}{(m!)^n}$$
• @austinian This is a special case of the multinomial coefficients theorem. Here we have $\binom{nm}{m,m,m,\dots,m} = \frac{(nm)!}{m!m!m!\dots m!} = \frac{(nm)!}{(m!)^n}$. In general $\binom{N}{a,b,c,\dots,k} = \frac{N!}{a!b!c!\dots k!}$ where $a+b+c+\dots+k = N$. May 24, 2015 at 0:26
• @austinian: each of the $n$ letters is being repeated $m$ times, and assuming each of the letters/elements are indistinguishable, since we can arrange for example the As amongst themselves $m!$ times, and since there are $n$ such letters we have to divide by $(m!)^n$ May 24, 2015 at 1:03