Welcome to NRICH.

 
Emma's Dilemma
By James Swann

Have you ever heard of the problem called Emma's Dilemma?

Emma is playing with the letters of her name, arranging them into different order:

1) Emma
2) Meam
3) Aemm


Investigate the number of different arrangements of the letters of Emma's name.

Investigate the number of different arrangements of the letters of the name Lucy.

Choose some different names and try to work those out too.

A number of X's and a number of Y's are written now in a row such as

XX, XXYY, Y, XXXYYYY etc.

Investigate the number of different arrangements of the letters.

If you could solve this problem I would be most grateful or if you have any
information like a formula to solve it, could you please tell me.

By The Editor:

This is a merger of two threads on the same topic. This problem has been set as GCSE coursework. If you are reading this thread because you have been set the same coursework, please remember that any help you get from any source must be referred to in your write-up. This will not necessarily affect your mark, particularly where we have given only a hint. You may wish not to read the whole thread, but stop as soon as you have enough of a hint to get you going.

By Dave Sheridan (Dms22) on Wednesday, October 6, 1999 - 06:49 pm:

This sounds suspiciously like a bit of homework to me... You should be investigating permutations and combinations. Since the point of this website is to encourage mathematics, I won't solve your problem (it's simple though) and will instead try to get you to solve it yourself.

First, try to solve the problem with the name James. How many ways are there of rearranging this?

Hint: How many ways can you choose the first letter? Once that's chosen, how about the second? Can you see how to extend this to any length of word?

If you can answer that, I'll give you some hints about the problem with a name like Emma.

-Dave

By Aly Crowley (P1162) on Saturday, October 30, 1999 - 02:15 am:

Emma=16
lucy =16

because you time the number of letters by itself

Bye

Aly

By Jonathan Kirby (Pjk30) on Saturday, October 30, 1999 - 11:31 am:

Are you sure, Aly? Can you list the 16 combinations to check? How about the names "Jo" and "Aly" - does your rule work for those too?

Jonathan

By B.A. Lee (T153) on Tuesday, November 2, 1999 - 07:49 am:

A little tool may be useful in addressing Dave's hints.

5 x 4 x 3 x 2 x 1 = 5! (read as 5-factorial)

Look this up on the calculator (and in books?).

Work out a rule and test it on (in order of difficulty):

Lucy,
Emma,
Nann,
Anna, and finally
Aaaa.

Your rule should work for all of them. Hint: look out for repeated letters, they are devious.

By Ashley Lowndes (P1887) on Saturday, January 15, 2000 - 10:50 pm:

Dear mathematicians

I have been set the following problem: -

Emma is playing with arrangements of her name
One arrangement is EMMA

A different arrangement is MEAM

Emma has a friend LUCY, who does the same thing

(1) Investigate the number of arrangments of the letters of the names you have chosen
(2) A number of X's and a number of Y's are written in a row such as XX...XXYY...Y
Investigate the number of different arrangements of the letters

There is a link when you have a two of the same letters, the number of arrangements halves.
For example ANNA has 6 arrangmets and EMMA has 12 arrangments. ANNA has 2 letters the same (A and N) and EMMA has 1 letter the same (M).

Our teahcer mentioned the word 'permutation' may be involved. I cannot quite develope a suitable rule for (1) and I have no idea of how to accomplish (2). Please can you help. There isn't much more information about the project, but I can try and explain it in a different way if it seems unclear.

Sincerely Ashley Lowndes (I am 15 and this problem has been set for a higher tier maths set)
Any help is very welcome

By Andrew Rogers (Adr26) on Sunday, January 16, 2000 - 01:01 am:

Hi Ashley,

OK, while dealing with these sorts of problems it's often quite useful to know the 2 different kinds of "arrangements" that are commonly dealt with in Maths:

The first kind are "combinations". These are used in a situation where you take a set of objects and you select some (or all, or none) of them, and work out how many different ways there are of doing this, but not bothering about what order a particular collection of objects came out.
In your example, the "objects" would be all the letters of the girls' names, and you would be "picking" all of the letters, but since for combinations it doesn't matter which order you select the "objects" in, there would only be one combination of the letters.

The second kind are "permutations" and these are different because this time we decide it does matter what order we pick our objects in. I sometimes think of this like letters from a scrabble board, where you could put the letters from a word like "ARE" into the bag and if you wrote down what you got as you pulled out 3 letters, you'd have:

"ARE" or
"AER" or
"EAR" or
"ERA" or
"RAE" or
"REA".

So now I hope you're fairly clear on these two different kinds of "arrangements". If we ignore duplicate letters for a second (don't worry, we'll come back to them !), we can actually find formulae for these: The number of combinations of r objects from a set of n is called nCr, and the number of permutations of r objects from a set of n is called nPr.

Can you see a strategy for finding a formula for either of these ? (Try the one for nPr, we'll need it, the other one will be useful to you if you do A-level, and it's interesting as well !)

Hint: For nPr, how many different objects can we select for the first "position"? How many "objects" can we then select for the second position, once we have already selected one object ?, ... keep doing this till you have selected r elements, and you will have your formula !

Hint for nCr: Once you know how many permutations there are of r objects, think of the following: for each combination, how many different ways are there of arranging it (use the same method as before) ? If there are x different ways of arranging a particular combination, then why is (nCr) * x = (nPr)? So find the formula for nCr. (Optional !!)

Phew !

Once we've done all that, we really are quite happy until someone goes and thows the twist in at the end! (Why do teachers always seem to do that?) Anyway, it's making us think, and all we have to do now is work out what happens to our permutations when we allow two (or more) of the same character to come along and spoil our nice formulae !

OK, what we know just now is that looking at combinations for "AL1L2", we have:

"AL1L2"
"AL2L1"
"L1AL2"
"L1L2A"
"L2AL1"
"L2L1A"

Which would just look like:

"ALL"
"LAL"
"LLA"

If we ignored the subscripts. (i.e. Ignored the duplicate permutations, so L's are interchangeable)

Can you see what happens to the number of our permutations when we drop the subscripts in the above?

Or for a character repeated 3 times:

"L1L2L3"
"L1L3L2"
"L2L1L3"
"L2L3L1"
"L3L1L2"
"L3L2L1"

Becomes

"LLL"

How does the number of permutations reduce for 3 characters the same? Or n characters the same ?

Hint: Think of the permutations of L1, L2, ..., Ln

If we had more than one repeated character, what would happen?

Hint: Think of permutations of A1, A2, ..., An, B1, B2, ..., Bm

So now we'll have no problem with your names, and if you've managed to fill in all the gaps (including the last one above !), you'll also have a formula for your rows of X's and Y's.

Just in case you are wanting to completely blow your teacher's sock off, you could look at doing the above with not only A's and B's (or X's and Y's) but with any number of letters. You might even want to have a think about what repeating letters would do to the "combinations" we talked about earlier.

Gosh, it's getting late, isn't it? It's just gone 1am, and even Scottish 1st Year Mathematicians have to sleep sometime !

Hope this helps you get through the work. I have left what I feel is a fairly steady guide, so that you won't go too far wrong, but you'll still have to do most of the legwork (but then again so did I while I was writing ths post!). If you do get stuck, or want to find out more about any of the things I have mentioned (there are many interesting applications in probability theory...), then just stick another post up, and I'll get back ASAP. (Though my reply will probably be shorter than this mammoth post !)

Bye for now,


Andrew R

By Alan Parr (T736) on Sunday, January 16, 2000 - 07:15 pm:

Given that a word of four different letters has 24 permutations, what combination of four letters has the greatest number which form allowable English words?

The best I can discover is EILV, which gives VILE, EVIL, LIVE, VEIL, and LEVI

Can anyone beat five?

Alan Parr

By Dan Goodman (Dfmg2) on Sunday, January 16, 2000 - 07:42 pm:

The best I can manage is EATS which has 7, they are:

EAST
EATS
ETAS (plural of eta the greek letter h)
SATE
SEAT
TEAS
SETA (a bristle)

I think that is the best you can do without allowing acronyms and so forth.

By Ashley Lowndes (P1887) on Tuesday, January 18, 2000 - 08:44 pm:

Dear Andrew Rogers
I would just like to say how grateful I am for your help in the maths project. I think 10 GCSE's is a heavy workload, so you must have collosal amounts of work!

I just wanted to know if some of the things I've done (with your help) are on the right tracks.

(n!) gives you the answer for words with different letters, but I'm slightly confused about words with some of the letters the same. I have a rough idea that may look like: -
no. of arrangments = n! / c! where n is the number of letters and c is the number of letters the same. However I foolishly haven't tested this yet. I may be skirting around the issue, I'm not sure. I have other rules to test as well, all involving factorials.

If you have any other bits of advice, again I would be most grateful - but, please if it's late, sleep rather than write a reply as your work load must be huge.

Gratefully
Ashley Lowndes
P.S. as an extra challenge we have been told to work out the no. of arrangments for the name of the town in Anglesey called: -
"Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch"

By Andrew Rogers (Adr26) on Wednesday, January 19, 2000 - 10:24 am:

Dear Ashley, thanks for getting back

You are indeed right that the formula for the permutations of a word without duplicate letters is (n!).

This is the value of nPr when n=r (ie you are using all of the letters).

You have also correctly followed through the bit on duplicate letters, so if there are c duplicate letters, there will be (c!) different permutations of them, and so there will be (n!/c!) different permutations if we ignore the "differences" between duplicate letters (What I mean is that instead of calling letters "L1, L2, ...", you call them "L, L, ...".

Well done !

Note that if you had a name of n characters, and you had 3 repeated "L's" and 2 repeated "R's", then you would have 3 repeated characters and 2 repeated characters, and so the number of arrangements (by your formula) is:

n!/(2!3!)

I won't spoil your fun, but if you follow the same pattern, it's just a case of counting letters to work out the different arrangements of Llanfair PG (as it's known for short !).

Extra Bit !

If we wanted to make your formula a bit more general, so that if we had a name of 6 letters, like "ANDREW", but only wanted to look at unique permutations (unique in the sense we ignore duplicate letters), what would happen ?

If I pick 3 letters (not worrying about duplicates for a second) then I can pick from 6 for the first letter, 5 for the second, etc.

I no longer have n! = n * (n-1) * ... * 2 * 1 permutations but:

n * (n-1) * (n-2) * ... * (n-r)

(where r is the number of letters I pick)

What is the above number on terms of factorials ?

Can you use that to make a formula for "unique" permutations of r letters picked from a name of n characters ? (Do the same thing to this as you did to n!)

End of Extra bit !

See how you get on with Llanfair PG and the XY problem.

If there's anything you're not clear on, then do get back to me. I would have posted yesterday, but I've been busy trying to set up some PCs for my college. We are currently using Windows 3.1, which is very old, and I'm trying to set up Windows NT4.0 (Which is a lot like Windows 95) on them.

I confess I only did the Scottish equivalent of 5 GCSEs, so you are in fact doing a lot more work than I did a mere 4 years ago (oops, that makes me feel old!). Also, most of this problem reminds me of the work I did in my last year of High School, and not before (ie at A-level standard rather than GCSE standard )! Keep working hard, and I'm sure you'll do well, and remember, noone can ask you do to any better that you're capable of, so if like me there are subjects you just can't get A's in (one of mine was Art), then be happy doing your best !

Once again, thanks again for writing back and good luck with rest of the problems !


Yours,


Andrew R

By Andrew Rogers (Adr26) on Wednesday, January 19, 2000 - 02:01 pm:

A bit more about when you have more than one repeated character:

When you have 2 (or more) characters that are duplicated, you look at the permutations for each character, so for "LLLRR" we would have:

n!/(3!2!) permutations

So there are 5!/(3!2!) = 10 different ways of arranging "LLLRR":

"LLLRR"
"LLRLR"
"LLRRL"
"LRLLR"
"LRLRL"
"LRRLL"
"RLLLR"
"RLLRL"
"RLRLL"
"RRLLL"

I'll illustrate how to do this the right way for multiple characters, because earlier I confused myself, and I 'd like to double-check I've explained clearly. Let's look at "A man, a plan, a canal, Panama!", which is palindromic (ie it reads the same backwards as forwards !)

AMANAPLANACANALPANAMA has 21 characters, with the following repeated characters:

A, 10 times
L, 2 times
M, 2 times
N, 4 times
P, 2 times

so the no. of permutations is:

21! / (10!.2!.2!.4!.2!) = 73,329,656,400

( If you like you could check how many permutations there are. In fact it would take everyone in the world (5 billion people) to find about 14 permutations each which were different from everybody else's before we would have them all written down !)

Yours,


Andrew R