1
$\begingroup$

Consider some text $T$

How many different permutations of this text can we achieve ?

The easiest case is when every letter appears only once in the text, so the answer is $|T|!$

But when we have for example $T=aab$ the number of different permutations is 3, because $aab$ $aba$ $baa$

How can we solve this problem without actually generating all possible permutations of this text ?

3 Answers 3

0

The general formula for a permutation of a text with length $n$ with $n_1$ indistinguishable objects of one type, $n_2$ of the next type is:

$\frac{n!}{n_1!n_2!\dots n_k!}$

For your text: aab n=3, $n_1$(the number of times a appears)=2 and $n2=1$(Since b appears once). This formula simply divides out all of the objects that $n!$ overcounts.

3

An example might help. Consider the text $probability$. If we thought of all letters as distinct: $p\ r\ o\ b_1\ a\ b_2\ i_1\ l\ i_2\ t\ y$, then there would be $11!$ permutations.

But this overcounts, as not all letters are distinct. In particular, amongst the $11!$ factorial arrangements above, we have both $\eqalign{ &r\ p\ o\ b_1\ a\ b_2\ \color{maroon}{i_1}\ l\ \color{maroon}{i_2}\ t\ y\cr &r\ p\ o\ b_1\ a\ b_2\ \color{maroon}{i_2}\ l\ \color{maroon}{i_i}\ t\ y\cr} $ For any particular arrangement amongst the $11!$ arrangements of the letters, we can find one other (by permuting the $i$'s) that is the same when we regard the $i$'s as indistinguishable.

So we've over counted by a factor of 2. Similarly, because there are two $b$'s, we overcounted by another factor of 2.

So, the correct number of arrangements is $11!\over 2\cdot2$.

A similar argument can be made to establish the formula that Hooked gives in his answer. In particular if one letter was repeated thrice, then if we found the number of arrangements where we thought of all letters as distinct, we would have over counted by a factor of $3!$; since there are $3!$ ways to permute the three repititions of the letter.

1

It is given by the multinomial theorem:

$ \frac{N!}{m_1! m_2! m_3! \ldots m_k!} = \text{choose}(n, (m_1,m_2, \ldots, m_k)) $

Here $N$ is the number of elements in $T$, $|T|=N$. If there are $k$ unique elements in $T$, $m_i$ is the number of times that element shows up. From your example, $N=3$, $m_1 = 2$, $m_2 = 1$, so we get

$ \frac{3!}{2! \cdot 1!} = \frac{6}{2} = 3 $

  • 0
    Thank you, i didn't know it's that easy :)2012-02-01