Do the shuffle.

I'm in a class this semester called Puzzle, Games and Algorithms. Originally I thought it would just be an easy class that I would take for essentially free Comp. Sci. credit. It hasn't been terribly difficult, but Friday of last week shared some information that rightly blew my mind.

We were discussing a random deck of cards and Professor Snapp made the claim that if he were to shuffle the cards, then the specific permutation of cards that his shuffle would yield would never have been seen before. Most of the class disagreed with him. I agreed with him, but only because I thought he must know something that I didn't and not because I genuinely thought that the average shuffle yielded a unique deck. Well, here was the proof:

Since there are 52 distinguishable cards in a standard deck of playing cards (13 different numbers, repeated four times, but each time in a different suit), then the number of distinguishable permutations for the deck is 52!.

If you aren't sure about factorials, 52! (read 52 factorial) is equal to 52 * 51 * 50 * 49 * ... * 3 * 2 * 1 = 8 * 10^67

To put that in a little perspective he offered us a few estimates for other objects:
• Number of seconds in a century = 4.5 × 10^9.
• Number of human beings alive on Earth = 6.7 × 10^9.
• Number of Oreo cookies sold since 1912 = 4.9 × 10^11.
• Federal debt (est. in US$ on 9/10/07) = 9.0 × 10^12.
• Number of seconds that have elapsed since the Big Bang = 4 × 10^17.
• Number of distinct positions in a 3 × 3 × 3 Rubik’s cube = 4 × 10^19.
• Number of grains of sand on the earth = 10^21.
• Number of stars in the visible universe (Simon Driver, 2003) = 7 × 10^22.
• Number of atoms in a human body = 10^28.
• Mass of the sun (in kilograms) = 10^30.
• Number of legal chess positions = 10^40.
• Number of distinct positions in a 4 × 4 × 4 Rubik’s Revenge = 10^45.
• Number of permutations of 52 playing cards = 8 × 10^67.
• Number of distinct positions in a 5 × 5 × 5 Rubik’s Ultimate Cube = 10^74.
• Number of physical particles in the universe (inflationary model) = 10^80.
• Number of distinguishable games of go = 10^768
(These were copied from the PowerPoint presentation used during the lecture, found at http://www.cs.uvm.edu/~snapp/puzzles/)

Basically, even if everyone (today's population) on the earth had been shuffling a deck of cards once a second from the very instant of the Big Bang, we wouldn't have seen all the possible combinations. In fact, if every star in the visible universe had a planet just like the Earth with exactly as many people and all of those people were shuffling 52-card decks once a second beginning the second of the Big Bang, even then we would have only seen 1.876 * 10^50 diferent shuffles, leaving the rest of the 8 x 10^67 unseen. And that is a great number of unseen permutations.

And that's all I have to say.