Sunday 31 May 2009

On The Trail of a Subfactorial Notation



A letter on the AP Statistics EDG last week reminded me that I am still missing a big detail about the notation for Derangements, or Subfactorials. The questions asked something like, how many ways can 5 letters and 5 envelopes be mis-sorted so that exactly two are in the right envelope, or maybe it asked for the probability of such an event... anyway..

The method of placing an ordered set in such a way that no element falls in the correct order is called a derangement. The number of ways of completely mis-sorting all of N objects is often represented with the notation !n and called subfactorial n.

The name subfactorial was created by W A Whitworth around 1877. The symbol for the subractorial is !n, a simple reversal of the use of the exclamation for n-factorial, although this symbol is relativly newer than the word. Whitworth himself used a symbol something like
|| n
in imitation of the symbol for factorial introduced by Jarrett that was then common. Cajori's classic on the symbols of mathematics, (published in 1928) gave no mention of the use of the !n notation, but does credit G Crystal with the use of an inverted exclamation mark after the n. Perhaps the age of the typewriter ushered in the move to placing the exclamation mark at the front.

The formula for !n is often given as


A simple way to compute the value is to round the answer of n!/e. It can also be found by a recursive rule... using F(0) = 1 and for each new value F(n)= n F(n-1) + (-1)n. So F(1) = 1(1) - 1=0 (makes sense, you can't mis-sort if there is only one letter and one envelope), and F(2) = 2(0)+1=1(Put Letter A in envelope B and vice-versa) and F(3)= 3(1)-1=2 etc.

The sequence was first produced by Nicolaus Bernoulli in trying to answer the following problem, which was posed by P R de Montmort (it may be that Montmort already had a solution). If N letters and N Envelopes to contain them are prepared, in how many ways may ALL the letters be placed in the wrong envelopes. The solution is !n, and the first few answers are 0, 1, 2, 9, 44, 265, 1854... .

Euler used the same method to develop the probability of winning in the game of rencontre, now called "coincidences" in his paper "Calcul de la Probabilite dans le jeu de Rencontre", published around 1751. An English translation of the paper by Richard J. Pulskamp is available at this site and the original document can be seen here.

So I know a little, but the most common present day notation is !n, and I don't know who first did it, or when they did it... so if you have a collection of old math books that includes some probability etc... and you come across a usage of this symbol, drop me a note, or better, send me an email with a digital image.. I will make my students name that first-born mathematically inclined child after you.

No comments: