This is known as increasing at a factorial rate. Factorials can be written in short with the factorial number followed by an exclamation mark ( ! ). For example four factorial would be expressed as ‘ 4 ! ’.
The factorial of the total number of different arrangements (y) for any different number of different letters (x) is equal to the number of letters, may be written as:
Y = X!
Part 2 – Investigating Emma:
Part 2 of Emma’s Dilemma is to investigate the number of arrangements for the name Emma. The difference with this name is that one letter is repeated, therefore there are only three different letters. This is obviously going to affect the number of arrangements as it restricts arrangements that could be used if all of the letters was different. So firstly, I listed out all the different arrangements for the name EMMA, there were:
EMMA EMAM EAMM MEAM MAEM MEMA MAME AEMM AMME AMEM MMAE MMEA
There are 12 different arrangements for the name Emma. This is interesting as this is half the number of arrangements of the name Lucy which has an equal number of letters, the only difference being that Emma has a letter that is repeated twice.
Taking this into account, I decided I would investigate the numbers of arrangements for words with repeated letters.
MM:
If we take the word MM and find the number of arrangements it can make, there is only one:
MM
EMM:
EMM is a three letter word with two letters the same. There are 3 arrangements as listed below:
EMM MEM MME
EMMA:
We have already worked out that the word Emma has 12 arrangements as listed below:
EMMA EMAM EAMM MEAM MAEM MEMA MAME AEMM AMME AMEM MMAE MMEA
EMMAB:
The number of different arrangements for the word EMMAB can be worked out by using the permutations for the word EMMA. Basically, when we add an extra letter on, we are expanding the amount of permutations as we can take the new letter and place it on the beginning of the word and you have an extra number of permutations. For the example of EMMAB, you can keep place the B at the beginning and then swap the other letters around and end up with the same amount of permutations as EMMA. Placing the extra letter in the word also allows you to complete this again as there is an extra letter and still the same amount of letters that you are moving around with one letter kept at the beginning. For EMMAB, this process can be completed 5 times but this is complicated as there are two M letters in the word which will restrict the number of different permutations. This can be completed and then the repeated arrangements can be removed giving you the correct number of permutations for the word EMMAB. I worked out that there were 60 different arrangements for this word.
I then, like with Lucy, put this information into a table.
Table 2
From this I noticed there seemed to be a relation between the amounts by which the arrangements increased for words with the same number of letters: 1) one repeated letter 2) words with no repeated letters. So I added an extra row onto the table and tried to find a link between the two.
Table 3
After looking at this table, I could see that there was a pattern. The arrangements of words with different letters had exactly double the arrangements of words with one repeated letter, both words having the same amount of letters.
So when two words have the same amount of letters, one having totally different letters and one having one repeated letter, the one with the different letters will have twice the number of possible arrangements of the one with a repeated letter.
So the formula calculating the number of arrangements (Y) for a word, such as Emma with X letters but X-1 different letters is:
Y = X! / 2
So we can look in general at how having letters the same affects the number of arrangements. So far we have looked at ABCD and ABBC.
AB¹B²C:
When all the letters are different, the amount of permutations is not restricted and you are free to move the letters into any position.
ABBC:
When two of the letters are the same, the number of restrictions is reduced by half. When listing the arrangements you, you can’t complete half of the ones you would do if the two letters were different as the letters have already been in that position, even if it may have been the first B in the word for example and not the second B, the arrangement can’t be completed as the two Bs are not distinguished between.
As it seemed interesting that the number letters that were repeated in the word and the number you had to divide by in the formula were both 2, I thought it might be interesting to investigate if this formula further changed when I changed the number of repeated letters. I decided to investigate the number of arrangements for words with three letters repeated:
BBB:
This word is made of three letters, all of which are the same. Therefore there can be no possible arrangements other than 1:
BBB
ABBB:
This word is made up of four letters, three of which are repeated. This should greatly restrict the number of arrangements as there is only one letter that can move round as the rest are the same. Below are the 4 arrangements that could be produced:
ABBB BABB BBAB BBBA
ABCCC:
The word ‘ABCCC’ is a five letter word comprised of three letters that are the same. The following 20 permutations could be produce using this word:
ABCCC ACBCC ACCBC ACCCB BACCC BCACC BCCAC BCCCA CABCC CACBC CACCB CBACC
CBCAC CBCCA CCABC CCBAC CCACB CCBCA CCCAB CCCBA
So if we put this into a table in order that the data is easier to view:
Table 4
So we can now look at this data in relation to the formula I produced earlier for words with two repeated letters. The formula stated that the number of combinations (y) would be equal to letters in the word (x) factorial, divided by two (y=x!/2). So if we look at the equation and if it would be correct in a word where there are three of the same letters.
Table 5
The formula for words with two letters the same quite clearly doesn’t work for words with three letters the same. This seemed interesting as the formula obviously changed according to the number of repeated letters. I now wanted to find out how the formula changed according to number of the same letters.
So, considering that in the formula for words with two letters the same, you had to divide the factorial by two, I thought that there may be a link between the number of times the letter was repeated and the number you had to divide by in the formula. So I then tried replacing the 2 in the previous formula with 3 as there was a letter that came up in the words 3 times. This gave me the formula:
Y = X! / 3
I then used this equation and worked out if it was correct or not, when looking at words with a letter that occurred three times:
Table 6
This too was not the answer, but did bring up a clear pattern. The answer to the formula ‘Y = X! / 3’, is exactly double the correct answer on all three examples I have used. Therefore if we look at the formula instead of dividing the factorial of x by three, we can divide it by two and get the correct answer as shown below:
Table 7
This was clearly the formula but it seemed too specific for me to develop a general formula so I decided to look at the three formulas I had developed again.
-
For Words with a Letter Occurring Once:
Y = X!
For Words with a Letter Occurring Twice
Y = X! / 2
For Words with a Letter Occurring Three Times:
Y = X! / 6
After studying these equations I noticed that the number in the equations that you divide by is linked to factorials. I then realised that the number you must divide by in the formula is the number of times the repeating letter occurs factorial. So if we look at the equations again:
For Words with a Letter Occurring Once:
Y = X! / 1
Y = X! / 1! (1! being 1)
For Words with a Letter Occurring Twice:
Y = X! / 2
Y = X! / 2! (2! being 2)
For Words with a Letter Occurring Three Times:
Y = X! / 6
Y = X! / 3! (3! being 6)
So I had now worked out the general formula for words with one set of repeated letters, but what if there were words that had different letters repeated a number of times. For example, the formula I had worked out would not work for a word such as AABBBCC. So I wanted to find out a formula that could work out the number of arrangements for a word with any amount of letters, of which any number could be repeated.
After my previous workings, I already had a good idea of how the formula maybe set up, probably including factorials and a division. So I decided to have a look at a number of different words with various amounts of repeated letters and the number of permutations they created:
AABB:
This word is made up of four letters, with two sets of two repeated letters. This word has 6 different arrangements, as you can only begin with either A or B and then there are three letters left that can be swapped round producing three arrangements starting with either A or B. As you can start with both you therefore can create 6 arrangements as shown below:
AABB ABAB ABBA BAAB BBAA BABA
This also proves my previous equation incorrect for this word as it would be:
4! / 2! = No. of Permutations and 4! / 2! = 12 and not 6 – which is the correct answer.
This is interesting however as the correct answer is half the number that my formula produced. So I thought about this when looking at the further variations.
AAABB:
This word has two different letters. A is repeated three times and B is repeated twice. I managed to work out the number of permutations, using help from the above word AABB. As in the word AAABB, there is one extra A, I could then add an A onto the beginning of ‘AABB’s permutations’ giving me 6 permutations. I then worked out that there were 4 more arrangements when the word began with B, as you could only move the letter B as all the other positions were taken up with As. There were four positions so the B could be in four different places and I managed to find 4 extra permutations giving me in total 10 permutations as shown below:
AAABB AABAB AABBA ABABA ABAAB ABBAA BAAAB BAAAB BABAA BBAAA
This also proved the equation from my previous findings incorrect as if the formula was correct, the number of permutations for the word AAABB would be:
5! / 3! = The Number of permutations and 5! / 3! = 150 / 6 = 25. This is the wrong answer as there were only 10 arrangements. So again my previous equation is proven wrong.
AAABBB:
This word is made up of six letters, including two sets of three repeated letters. There are 20 permutations that can be made out of this word as I have already worked out that the word AAABB has 10 different permutations and these arrangements can be repeated again for this word just with a B at the beginning and when starting with an A, exactly the same arrangements occur just with one ‘A’ being replaced with a ‘B’ in the letters that are moving around. The following 20 permutations can be produced for this word:
BAAABB BAABAB BAABBA BABABA BABAAB BABBAA BBAAAB BBAABA BBABAA BBBAAA
BAAABB BAABAB BAABBA BABABA BABAAB BABBAA BBAAAB BBAABA BBABAA BBBAAA
AAAABB:
This word is made up of 6 letters, with A repeated four times and B repeated twice. I managed to work out the following 15 permutations:
AAAABB AAABAB AAABBA AABAAB AABABA AABBAA ABAAAB ABAABA ABABAA ABBAAA BBAABB
BABAAA BAABAA BAAABA BAAAAB
This is interesting as the words AAAABB and AAABBB both have six letters in the word, but one produces 15 permutations and one produced 20 permutations.
Having looked at a few of these words and the number of permutations that each words can create, I started to think of what a general formula may include. Obviously the number of permutations must be affected by the other letters in the words and not just the letter that is repeated most. For example, the words AAABCD and AAABBB both have the same number of letters and A is repeated the same number of times but AAABCD will have a lot more arrangements as the other letters are different.
I was intrigued by the word AABB which had half the number of permutations that my formula produced. In my formula, I was taking into consideration the number of letters in the word and one of the two sets of double letters. For AABB I worked out, I did not take into consideration the second set of double letters. The number of permutations (6) by dividing the number of letters factorial (4! or 24) by 4, that is:
6 (i.e. Y) = 24 (i.e. 4!)
I then looked at the word and realised that the number 4 in the equation may be produced by the fact that there are two sets of letters, both repeated twice. So it may be that as there are two letters you multiply these together to get the number you divided by in the equation. This definitely works for the word AABB. There is also a strong possibility that factorials are involved. For example, when a letter was repeated three times, I divided by 6 to get the correct number of permutations which is 3! In this equation for the word AABB, the number 4 is not a factorial, however the number 2 is and 2 times 2 is equal to 4. This is interesting as there were two sets of letters repeated twice and there may be a link here. The equation works for AABB if it is written as follows:
Y = X! / 2! x 2!
For the word AAABB, there are 10 permutations and as the word is a five letter word, the starting point of 5! = 120. Therefore to get the correct answer, the number you must divide by is 12 which needs to be found in some way by looking at the word. One letter is repeated three times which in my previous equation would have meant that you divided by 6 or 3!. This is half the number I need to divide by which leaves me looking at the other letters in the word. The letter B occurs 2 times and 2 is also 2!. Therefore the number 12 which we need to find somehow can be produced by multiplying 2! and 3! together.
(1 x 2 x 3) x (1 x 2) = 6 x 2 = 12
So having worked this out, it appears that the formula is produced by multiplying the number of times the letters are repeated factorial together, and this is the number that you divide into the maximum number of permutations for any given number of letters i.e. x.
To test if this is correct we can look at a different word that I have already worked out the number of permutations for:
AAAABB has 6 letters in it and can create 15 different arrangements.
So using the information I have just gathered the equation should be set up as follows:
There are 6 letters in the word so we start off by using 6! which is equal to 720.
As the letter is A is repeated four times, you use 4! and as the letter B is repeated 2 times in the word we need to use 2!
The formula is therefore:
Y = 6! / 4! x 2!
Y = 720 / 24 x 2
Y = 720 / 48
Y = 15
This produces the number 15 which is the correct amount of different arrangements.
To make sure that I am working in the right direction to producing a formula for working out the number of permutations for any word, I must try my thoughts on a couple more words and work out if the formula I am working towards is working out the correct number of arrangements:
AABC:
Earlier in my investigation I worked out that for a word with four letters in it, two of which are the same, there are 12 different combinations. As listed below:
AABC AACB ABCA ABAC ACAB ACBA BAAC BACA BCAA CAAB CABA CBAA
Using my formula I can also check the number of different permutations.
There are 4 letters in the word so the first number I need is 4! which is 24. I then work out that there are two letters that are repeated once and therefore I get two sets of 1! which is just one and needs to be included but does not affect anything. There is also a letter (A) which comes up 2 times in the word. Therefore I get 2! which is equal to 2.
So I get ( 1 ) x ( 1 ) x ( 1 x 2 ) = 1 x 1 x 2 = 2
So we get:
24 / 2 = 12
This is the correct number of arrangements for AABC
AABBC:
This word is made up of 5 letters and there are two letters which appear in the word two times. I worked out by listing the permutations that there are 30 different arrangements:
AABBC AABCB AACBB ABBCA ABCBA ABBAC ABCAB ABACB ABABC ACABB ACBAB ACBBA BAABC BABAC BABCA BAACB BACAB BACBA BBCAA BBACA BBAAC BCAAB
BCABA BCBAA CAABB CABAB CABBA CBABA CBAAB CBBAA
So looking at the word I can then apply the same rules for this word. The word is made up of 5 letters so we
The maximum value is 5! which is equal to 120. Then we look at the letters that make up the word. One letter occurs only once so we get the value of 1! which is equal to 1. There are also two letters that occur two times and so we then get the values of 2! and 2! which are both equal to 2. We then multiply the 3 factorial together:
( 1 ) x ( 1 x 2) x ( 1 x 2 ) = 1 x 2 x 2 = 4
So we then put the two values together and workout the answer for the number of permutations for AABBC as follows:
Y = 5! / 2! x 2! x 1!
Y = 120 / 4
Y = 30
This proves that the formula that I came up with is correct for working out the number of different arrangements for any word no matter what letters it contains.
The final general formula is shown below:
Y = X! / A! x B! _ x _ C! Etc.
When-
Y is the number different permutations.
X is the number of letters in the word.
A is the number of repetitions of any letter.
B is the number of repetitions of any second letter.
C, D, E etc. is the number of repetitions of the remaining letters.
So applying this formula I can work out the number of different permutations for any word as shown below:
AAAABBBCC:
Y = X! / A! x B! x C! Etc
Y = 9! / 4! x 3! x 2!
Y = 362880 / 24 x 6 x 2
Y = 362880 / 288
Y = 1260
There are 1260 different permutations for the word AAAABBBCC.
AAABBBBCCCCCDDDD:
Y = X! / A! x B! x C! x D!
Y = 16! / 3! x 4! x 5! x 4!
Y = 1307674368000 / 6 x 24 x 120 x 24
Y = 1307674368000 / 414720
Y = 3153150
There are 3153150 different permutations for the word AAABBBBBCCCCCDDDD