Take the 2-minute tour ×
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.

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 ?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
Thank you, i didn't know it's that easy :) –  Chris Feb 1 '12 at 16:45

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.