Permutations of Non-Distinguishable Objects and Circular Permutations

Okay, so its that time again, time for a class blog. I doubt this one will be as long or epic as say, a blog by Justus or Francis (seriously, just make a book or something), but hopefully it will be just as informative.

Today's topic was "Permutations of Non-Distinguishable Objects and Circular Permutations."

Whoa, that's pretty long. Someone, create Tinytopic.com, quick!

So does everyone remember what a permutation is?

(As defined by Mr. K)
Permutation - An ordered arrangement of objects without repetition.

Or (as defined by me)
Permutation - A set of objects where the order matters.

A permutation is not to be confused with a combination as we discussed in the last class. In short, a combination is a set of objects where the order does not matter. A permutation is a set of objects where the order does matter. That's why a "combination lock", should technically be a "permutation lock."

Remember that? Yeah, you better, because it's important for our formula, the aptly named "Pick" formula, which goes like this:

nPr = n!/(n-r)

(n and r are subscript, they are not being multiplied)

Where:

• n is the number of objects to "pick" from
• r is the number of objects to arrange

And when we use this formula, nPr is read as "n 'pick' r."

3P₄ is read as "three pick four."

What's totally awesome though is that this function can be accessed through your calculator!
So it goes something like this...

• Enter your "n" value first
• Press the [MATH] button
• Press the [<] button
• Press [2]
• Enter your "r" value
• Press [ENTER]

Isn't technology wonderful?

So after that, we talked a little bit more, but since there's not much to the "Pick" formula, we went on to talk about really huge permutations.

TinyURL.com is a site that takes immensely long website URLs and turns it into a short and sweet (although probably not so easy to remember) URL. So http://www.internetisseriousbusiness.com/index.html would turn into something like http://www.tinyurl.com/9aidso. Thus, it generates a unique (this means it's a permutation and not a combination) url every time someone wants to make a TinyURL.

So, Mr. K brought up a good point. Just how many URLs can TinyURL generate, and how long would it take to generate all those URLs?

Well, lets think about this for a second, and look at the example url TinyURL generated for us.

http://www.tinyurl.com/4kaqlv

Well, the fact that there is a number and letters there tells us, the value of a slot can be either a number (0 to 9) or a letter (a to z). Lets assume for now that:

a) The number can be in any slot, but there can only be 1 number
b) The letters are not case sensitive, so we can assume they'll always be upper or lower case (if it was a combination, we'd have to count upper and lower case a's as two seperate objects, but more on that later).
c) Letters can repeat (so your string could look like "1aaaaa"). This means you cannot use the "Pick" formula!

Why cant you use the pick formula?
Because the pick formula calculates the number of permutations where once an object or character is placed in the set, it cannot be used again. This is obviously not the case here.

So, we've already determined that a slot can have one of 36 values. 10 of those values are for each of the 10 numbers, and 26 of those values are for each of the 26 letters.

And we have 6 slots. So for every slot, we have 36 possible values. Thus our number of possible permutations is 36*36*36*36*36*36 or36^6 .

Which equals:

36^6 = 2 176 782 336

So thats two billion one hundred seventy six million seven hundred eighty-two thousand three hundred thirty six. (Say that 10 times fast!) And remember, a billion is big. Godzilla big.

Infact, its so big, we determined that it would take ~32 (approximately thirty-two) years to give Lawrence a billion dollars if we gave him 1 loonie (1 dollar) per second consistently. Times that by 2.176782336 and you have approximately how long it would take to generate every possible URL if one URL were generated every second consistently:

2.176782336 * 32 = ~69 years. The one on the slides says 64 years, because there we simply multiplied 32 by 2 (which is how many whole billions we have). I counted the fraction that would have been generated all the way up till the 2 176 782 336th day. However, since the 32 itself is an approximation, this is not completely accurate (hence the tilde [~], which means approxmiately).

And thats just if we're not counting capital letters!

If we did count capital letters, our number would be even huger! Because now our number of possible values in each slot is now larger. Instead of just "t", we now have "T" and "t". Thus, we don't just have 36^6 possible values, no. Now we have 62 possible values, because we have 52 possible letters and 10 possible numbers.

So how many permutations is that? Thats 62^6. Which equals...

5.680023558 x 10^10
Which equals to 56 800 235 580, or fifty-six billion, eight hundred million, two hundred thirty-five thousand five hundred eighty. Permutations.

So, 56 * 32? Thats ~1792. That's how many years it would take to generate all those permutations if one were generated every second!

But enough about that. Lets look at distinguishable objects versus non-distinguishable objects.

(Im going to speed up here because it's now 2am and I'm getting sleepy)

So on slide 7, we have a little example with the word book. How many ways can you rearrange the word book? How many unique permutations are there.

Well, we figure that out easy: 4! (the number of slots) divided by the number or repeating letters in this case, that letter is "o" and it repeats twice). Thus, our solution is 4!/2!, which is 12.

But then there a plot twist. What happens if one of the "o"'s is red, and is counted as a unique letter? Then we have even more permutations! Because now, instead of having only 3 possible values for a slot (where one slot has the same value as another slot due to one of the values repeating), we have 4 possible values. Thus, we have 4x3x2x1 = 24 possible permutations. But if you turn that red "o" back into a regular "o", some of your permutations become repeats. Thus, the number of permutations is halved, and you get your original answer of 12 permutations. Wow!

After being introduced that concept, we do a little practice with some other words. Then its on the the main course. Circular permutations.

Circular permutations looks wacky and complicated, and it takes a while to wrap your head around it, but really its just an expansion of the concept of distinguishable objects. The basic idea here is that when you have a circle, the first point you put on it serves as your reference point, and you work from that point on. Because your reference point is wherever you want it to be, your perspective as to the rotation of the table can be anything you want. Thus, with circular permutations, your duplicates stem from the fact that some permutations are in fact existing permutations that have just been rotated.

Alright, I give up now. This scribe post is incomplete, and I apologise to everyone that I'm posting so late. I'll expand and finish this post properly later today and make sure it's done as it should be, but for now I cant think when I'm half asleep.

Tomorrow's scribe (or should I say, today's scribe) is now Nelsa.

Also, a million points and a PHD to someone who can tell me the adjective of "bracelet." Seriously, a braceular table? I don't think so. I wonder if that's even an actual legitimate shape, or is it just a concept...