Wednesday, June 2, 2010

Wednesday Math, Vol. 120: The re-arrangements

I have used the phrase "factorial" in a few of my other math posts. Today, I use it to talk about ways of rearranging a list of objects.

The illustration on the left shows the definition of factorial for any positive integer n, but it is also decided that 0! = 1 for reasons we will go into later in the post.

Here is the list of the first 10 factorials from 1 to 10.

1! = 1
2! = 1*2 = 2
3! = 1*2*3 = 6
4! = 1*2*3*4 = 24
5! = 1*2*3*4*5 = 120
6! = 1*2*3*4*5*6 = 720
7! = 1*2*3*4*5*6*7 = 5,040
8! = 1*2*3*4*5*6*7*8 = 40,320
9! = 1*2*3*4*5*6*7*8*9 = 362,880
10! = 1*2*3*4*5*6*7*8*9*10 = 3,628,800

As you can see, factorial grows very fast, even faster than exponential functions. You will also notice that 5! = 120, and this is my 120th Wednesday Math post.

Let's say I have a five letter word, such as PARSE. How many different ways are there to rearrange the letters, like they do in the Jumble puzzles in the newspaper? The idea is that five different letters could be in the first position, and then four different letters could be in the second position, then three, then two then one, so the number of scrambles of PARSE is 5! or 120.

(Note: PARSE would never be used in the Jumble puzzle, because those five letters spell multiple English words, including SPARE, PEARS, PARES, RAPES, REAPS, etc.)

What if there is a repeated letter, like in the word ARENA? If I switched the first A and the second A, the word would look the same. What we do is count the number of times each letter shows up.

A shows up 2 times.
R, E, N, show up 1 time each.

The total number of re-arrangements is 5!/(2!*1!*1!*1!) = 60.

What about the six letter word BANANA? Again, we need to count the appearances in the word of each letter.

B shows up 1 time.
A shows up 3 times
N shows up 2 times.

The total number of re-arrangements is 6!/(1!*3!*2!) = 720/12 = 60.

This may seem like a weird question, but how many times does Q show up in the word BANANA? Obviously, the answer is 0 times, but if we were to include this in the equation, that would mean dividing by 0!. If 0! = 0, our formula would fall apart, but if 0! = 1, the formula works even if we count how many times every letter in the alphabet appears in a word.

In books that introduce this idea, it is very common to ask the question how many different ways are there to rearrange the letters in MISSISSIPPI. You can try this one on your own, if you like. The answer is in the comments.

Matty Boy said...

MISSISSIPPI has eleven letters.

M shows up 1 time
I shows up 4 times.
S shows up 4 times.
P shwos up 2 times.

11!/(1!*4!*4!*2!) = 34,650.

ken said...

Ummm... Hate to break it to you, but your Wednesday Math posting isn't one day late if you post it on Wednesday. Might be 2 weeks late, though ;-)

Matty Boy said...

Thanks, Ken. I'm working graveyard and my body hasn't quite gotten used to the sleep pattern yet.

I actually feel much better today than I felt yesterday, but I still have a lot of disturbing plumes of dumb bubbling up in my gulf of smart, and I don't think they have all been plugged up yet.

namastenancy said...

Sorry to hear about the disturbed sleep patterns. But I doubt if your gulf of smart is in serious danger from the plumes of dumb. Your dumb is probably somebody else's version of genius.
O!

BobManDo said...

Have you tried various top hats or a (baseball) cap to reduce the plume?
You could think of golf or think of other junk you have lying around... and muddy coffee could also help keep the plumes at bay.
===
whoo whoo! I got the right answer!