Factorial 52: A Stirling Problem

How many ways can a deck of cards be arranged? It is very easy to calculate the answer, but very difficult to grasp its significance.

Card-Arc

There are 52 cards. Thus, the first one may be chosen in 52 ways. The next one can be any of the remaining 51 cards. For the third, there are 50 choices, and so on until just one card remains, leaving only the option to put it last.

Therefore, the total number of possibilities is

52! \equiv 52 \times 51 \times 50 \times \dots \times 3 \times 2 \times 1 \,.

This number is called factorial 52. To say that it is a large number is an understatement. The program Mathematica can compute to arbitrary precision and entering the command Factorial[52] yields the following result:

80658175170943878571660636856403766975289505440883277824000000000000

In more compressed notation, this is 8.06582\times 10^{67} , or, to just a single figure of accuracy, {10^{68}}; that is, 1 followed by 68 zeros.

Describing 52!

It is difficult to illustrate the size of {52!} in terms of anything practical. People have talked about the number of drops in the ocean or how many grains of sand would fill the Grand Canyon. These numbers come nowhere close to {52!}.

The number of atoms in the observable universe is estimated to be about {10^{80}}, which is a trillion times bigger than {52!}. But does this really help us to visualise what either of these numbers is like? The Wikipedia article on Names of Large Numbers describes {10^{66}} as an unvigintillion. Thus, {52! \approx 8\times 10^{67}} is about eighty unvigintillion. But this is just a name.

The Universe is  4\times 10^{17} seconds old. If a random arrangement of cards were chosen each second during the entire life of the Universe, only a tiny fraction of all possible orderings would be selected. The chance of the same ordering being chosen twice is utterly negligible. Even if a billion arrangements were chosen every second, there would still be no real chance of a duplicate.

For an amusing description of the astounding magnitude of {52!}, see http://czep.net/weblog/52cards.html

Stirling’s Approximation

The calculation of the number {52} is simple. Just multiply 52 by 51, the result by 50 and so on until you reach 1. But how tedious this is, and how error-prone!

There is a beautiful expression giving an approximation to any factorial, named for James Stirling (1692–1770), a Scottish mathematician (although it seems that the result was stated earlier by Abraham de Moivre). The approximation is

n! \approx S_1(n) \equiv \sqrt{2\pi n}\left(\frac{n}{e}\right)^n

This is actually the first term in an asymptotic expansion. Taking the next term we have

n! \approx S_2(n) \equiv \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+\frac{1}{12n}\right)

Plugging in the argument {n = 52}, the first formula gives {S_1(52) = 8.0529\times 10^{67}} which is correct to 2 decimal places. The second formula gives {S_2(52) = 8.06581\times 10^{67}}, with relative error of only one part in a million.

Another approximation was found among the papers of the Indian mathematician Srinivasa Ramanujan and published in his Lost Notebook in 1988:

\ln(n!)\approx n\ln(n)-n+{\frac{1}{6}}\ln(n(1+4n(1+2n)))+{\frac {1}{2}}\ln(\pi ).

This gives {52!} to one part in a billion.

Shuffling and Repeated Orders

With such a vast number of possibilities, one might ask if any randomly-chosen order of a deck of cards occurs more than once. Making very reasonable assumptions, it is easy to argue that a particular ordering will never occur twice during the life of the Universe. Thus, when you thoroughly mix up the cards, you are bound to arrive at an ordering that has never been seen before and will never be seen again.

However, there is a big proviso here. The shuffling of the cards must be sufficiently thorough to ensure true randomization. Mathematical studies have indicated that a small number of effective shuffles suffice to mix up the pack to random order. Bayer and Diaconis (1992) showed that after seven random riffle shuffles, any of the 52! possible configurations is equally probable.

Sources

• Bayer, Dave and Persi Diaconis, 1992: Trailing the dovetail shuffle to its lair. Ann. Appl. Prob., 2, 2, 294-313.

• Wikipedia article on Names of Large Numbers.
http://www.wikipedia.org/

 


Last 50 Posts

Categories