Puzzle III.1: Permutations

Not really a new puzzle at this point, just a little background in order to prepare to address the latest puzzle. We’re going to have to learn enough combinatorics to be able to count the edges, subgraphs, colorings, etc. involved.

One intermediate concept that is needed before we actually get going: Permutations, or orderings. For our questions, we actually never care about the order of things (when we see a triangle involving vertices u, v, and w, we don’t consider it different than a triangle formed from w, v, and u), but it turns out that it is more natural to count ordered things, and then adjust our count for the fact that things have been overcounted by showing up repeatedly different orders.

So how many ways can you order n things? To start off with, any ordering needs a first element. And if we’re ordering n things, we have n choices for what that first element can be. After an element has been chosen for slot #1, then we have n-1 choices remaining to fill slot #2 (because 1 guy has already been chosen). Then n-2 choices for slot #3, etc., until there are only two guys left, and we have 2 choices for the next-to-last slot, and then there was one. Contrary to the intuition of every kid ever picked last for a sports team, what we have left is not no choice, but one choice, and that final one choice completes the definition of our ordering. So what do we do with all these numbers of choices we have at each stage of constructing a permutation? A little reflection should show (or you can just hear me now and believe me later) that they need to be multiplied together. So the number of permutations (orderings) of n objects is n(n-1)(n-2)(n-3)…(2)(1). (Note that multiplying by 1 at the end has no effect on the product, which is why the last-picked kid feels bad). There’s a shortcut notation for this, and it looks like “n!”, which is pronounced “n factorial”.

If this is a new concept, it is worth taking a break at this point, and hand-verifying at least up to 4. Here — I’ll even do the first two:

Here are all the ways to order 1 object: 1. Hey, it turns out there is 1 permutation. And 1! = the product of all the numbers from 1, all the way down to, well, 1, which is just 1. Since 1=1, everything checks out OK.

The case of 2 is unfortunately barely more interesting:

Here are all the ways to order 2 objects: 12, 21. Hey, it turns out there are 2 permutations. And 2! = (2)(1) = 2. Since 2=2, everything checks out OK.

(I have colored red the 1 and 2 that are important, because they are easy to get confused with all the other 1 and 2 laying around)

Now you can write out all the permutations of 3 objects, and also compute 3!, and verify that that’s how many permutations there are. A little tricker, compute 4!, verify that that’s how many permutations of 4 objects you can think of. Take care to enumerate the permutations in a methodical way, so that you can convince yourself that you have found them all. At this point, you should compute 5!, and decide whether you want to write down that many permutations of 5 objects, or just accept the lesson as learned. Keep computing more factorials to see how quickly they grow. It might be helpful to switch to a calculator (or a spreadsheet — the Excel function that computes factorials is called FACT). How long before you surpass a million? A billion? How long before you overflow your calculator?

Next time, we’ll ask (and answer) questions of the form: If we were to search all the colorings of K5 (or K6 (or K100)) for one that had no monochromatic K3 (or K10), how long would it take?

Advertisements

4 Responses

  1. […] Puzzle III.1: Permutations […]

  2. R– I’m loving this new series!! It’s great to read your very clear explanations of these number/graph theory concepts. Looking forward to the future installments.

    At one point a while back, I had planned to do a series on the (100+ year old) history of “modern” physics — for the 100th anniversary of Einstein’s Miraculous Year in 1905. But then other things in life intervened, and I never even started the series… If I go back to blogging some day, maybe I’ll bring back that idea.

    Oh, and thanks for giving me an “A for Effort.”

  3. Hey, you earned it! Glad to hear somebody’s reading! And I’m glad to hear you think the explanations are very clear, since I’m aiming these at the middle/high school level for some friends to use with their homeschool kids. Once they get around to guinea pigging their kids for me, I hope to use their feedback to improve the posts. In the end, for this purpose, probably a blog is not the right format, but it’s a place to start.

    I do hope you get around to a series on physics — too bad you missed the 100th anniversary, but if it helps motivate you, maybe you could develop them for undergrad brownbags or something, and persist them in blog form…

  4. […] Puzzle III.1: Permutations […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: