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
(in the example,
). 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
of them.
Then we repeat the process with the remaining
letters.
This means we have
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
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
times. So the correct answer is
.
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
ways of doing this. So each word has been
repeated
times in the pattern. If we forget the colours of the Ms, there
are only
ways of rearranging them. In general, this corresponds to
.
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
times), we see there are
ways of writing the same word. So in general,
there are
ways to rearrange this.
Now we only need to worry about when there are two or more letters which were
repeated. Say there are
repetitions of M and
of L. Decide on which
letter goes where, but not the colours. We have
ways of colouring the Ms,
and
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
. So each word is repeated
times and the total number of
arrangements is
. The same applies to three, four, etc different
letters which have been repeated.
So now we have that for a general word with
letters, and
,
,
,
...,
number of repetitions, the total number of arrangements is
.
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
,
,
,... 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
be the
number of times the letter
occurs in the word (so
if
does not appear in the word). Let
be the number of rearrangements which
we're trying to sort out. The formula reads:
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
ranges from 1 to infinity,
so it is actually
and since there are only finitely many
terms which aren't equal to 1, this is actually quite a ßmall" 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
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
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.