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

$\endgroup$
1
  • 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, 2015 at 0:23

1 Answer 1

Reset to default
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}$$

$\endgroup$
3
  • $\begingroup$ How did you arrive at the denominator? $\endgroup$
    – austinian
    May 24, 2015 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, 2015 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, 2015 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.