1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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$ $\endgroup$ – JMoravitz May 24 '15 at 0:23
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How did you arrive at the denominator? $\endgroup$ – austinian May 24 '15 at 0:23
  • 2
    $\begingroup$ @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$. $\endgroup$ – JMoravitz May 24 '15 at 0:26
  • 1
    $\begingroup$ @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$ $\endgroup$ – David Quinn May 24 '15 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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