Welcome to NRICH.

 
Permutations with repetition
By Anonymous on December 14, 1998:

How many permutations are there for 'EMMA'? -
there are 12 of course!
e.g. MEAM

I got this formula to find out the number of permutations of any word:

P = n!/(a!b!c!....z!)

where P is the number of permutations
n is the number of letters in the word
a is the number of identical letters of one kind
b """"""""""""""""""""""""""""""""" another kind

.....and so on.

The only problem is that I cannot prove this formula by actually looking at the mathematical structure in the abstract - also, can you tell me a more sophisticated way of writing this formula, maybe so that we are not restricted to a 26 letter alphabet, i.e. to include an infinite alphabet.

By Dave (dms22) on December 31, 1998:


Hello!

I am not sure how much you know about this subject, so forgive me if what I'm about to say is obvious or too easy for you.

We should try to understand why the formula works. When faced with a complicated problem like this, we mathematicians try to look at really simple cases first. If we understand these, it's often easier to extend our knowledge to the difficult ones.

The easiest case of this formula is when there are no repeated letters. For example, "ENYA" has four distinct letters. You probably know that the number of rearrangements is n! (in the example, n=4). I'll give you a quick proof in case you haven't seen that before. For the first letter of the rearrangements, we have a choice of any letter, and there are n of them. Then we repeat the process with the remaining n-1 letters.
This means we have n(n-1)(n-2) x ... x 3 x 2 x 1 = n! ways of arranging the word.

Now, consider a simple word which has one repeated letter, like "EMMA". If we wrote one M in emphasised text (M) and the other in normal text (M), it would be clear that there are still n! ways to rearrange the word. But we know that EMMA and EMMA count as the same. How many times does this sort of thing happen though? If you decide on where the Ms go, there are two choices for which comes first in the word, and then the other one is fixed. So every possible word has been repeated 2! times. So the correct answer is n!/2!.

I hope you're still with me. Believe it or not, we're almost there. Generalising this to your formula doesn't take long. So let's do that.

What if there were three Ms? "EMMMA" certainly has 5! rearrangements. But how many times is each word repeated? Think of the Ms being red, green and blue. Decide where the Ms are in the word, and by considering which should go first, second and third when reading from the left, you should see that there are 3 x 2 x 1 = 3! ways of doing this. So each word has been repeated 3! times in the pattern. If we forget the colours of the Ms, there are only 5!/3! ways of rearranging them. In general, this corresponds to n!/3!.

The same argument appplies to any number of times one letter has been repeated. By deciding on the order of the repeated letters (say it has been repeated a times), we see there are a! ways of writing the same word. So in general, there are n!/a! ways to rearrange this.

Now we only need to worry about when there are two or more letters which were repeated. Say there are a repetitions of M and b of L. Decide on which letter goes where, but not the colours. We have a! ways of colouring the Ms, and b! ways of doing the Ls. But how we colour one letter doesn't affect how we can colour the other. So the total number of ways to colour the letters is a!b!. So each word is repeated a!b! times and the total number of arrangements is n!/a!b!. The same applies to three, four, etc different letters which have been repeated.

So now we have that for a general word with n letters, and a,b,c,...,z number of repetitions, the total number of arrangements is n!/a!b!c!...z!.


I hope you've made it here! If you have, you should have a much better idea of why the formula holds. It does only depend on the structure - I've written it in terms of test words simply because it's easier to see what's going on then. It could be done without any examples, but becomes more difficult to understand. If you still can't quite see how it works, go and try rearranging a few words with differently coloured letters and see if that helps. If not, let me know and I'll try to explain it better!

As for a better way to write it, I can't really give you anything better than this: If your language has a countable number of symbols, enumerate it as x1,x2,x3,... and if it's uncountable, you need to decide on some countable subset which will suffice for your purpose (each case only has finitely many elements, but
you can't write a general formula in the case-by-case term). If you don't know what an uncountable set is, don't worry - I can almost guarantee you weren't thinking of it! Now fix the word you wish to rearrange. Let yi be the number of times the letter xi occurs in the word (so yi=0 if xi does not appear in the word). Let N be the number of rearrangements which we're trying to sort out. The formula reads:

N = n! / (Pi=1¥ yi!)

Ok, so it's not the best way to write a formula, but I hope you can see what it's supposed to be. If you haven't seen this use of capital pi before, it means the product of each term when i ranges from 1 to infinity,

so it is actually y1!y2!y3!... and since there are only finitely many terms which aren't equal to 1, this is actually quite a "small" number.

If you didn't understand a word of that, the basic answer is no, there is no real better way of writing it. What I've written is basically the same as your formula, but compacted somewhat. If you want to talk about that some more, let me know!


Finally, if you're not sick to death of this subject yet, you might like to consider the following:

There are n businessmen at a meeting. They sit at a round table. How many different seating plans are there? (there is no 'head' of the table, so we can rotate one configuration without changing the seating plan). How many seating plans are there which specify the company the men come from? (This corresponds to repeated letters in the original question) Can you give a general formula like the one above for this problem?
Even worse! There are n beads to be put on a wire ring. How many different ways are there of doing this? (you can do more than just rotate this!) If some are the same colour, try to work out the formula for this too!

If you want any help with these, please say so.

Hope this was some use!

-Dave.