## Tuesday 6 August 2024

### The Subfactorial and Some Historical Notes

Subfactorial the name subractorial was created by W. A Whitworth in The Messenger of Mathematics in May of 1877.  The symbol for the subfactorial is !n, a simple reversal of the use of the exclamation for n-factorial. This was not the symbol used by Whitworth, as at this time many people preferred what is called the Jarret symbol for the factorial. Whitworth added an extra line in the L to make the subfactorial. This symbol for the factorial persisted into the 1950's.  (Notes on the History of the factorial and its symbols.)

The subfactorial, or derangement is about counting the number of ways to take objects which have some order, and arranging them so that none is in its right ordered place.  The numbers 1, 2, 3 can be arranged for example, as 2,3,1, or 3,1,2.  The problem was first considered by Pierre Raymond de Montmort in 1708, and first solved by him in 1713.

Cajori mentioned the use by George Chrystal (1851-1911) of a subfactorial symbol using N with an upside down exclamation point, but does not mention at all the !n that is the common present symbol, leading me to believe it was created after 1929.

Crystal's books into the fifties continued to use the inverted exclamation symbol and the National Academy of Sciences used the symbol in 1967.
The earliest used of the !n symbol I have ever found is from 1958, In the MAA questions section:

This was obviously not an instant hit, as I received several comments like the following after a post in 2009.
"  I have several books on my shelf, none of which use !n notation.
D(n)
- Matoušek and Nešetřil, 1998
- Niven, 1965. I teach from this book.

D_n
- Chen and Koh, 1992. Interestingly, they use the notation D(n,r,k) to denote the number of r-permutations of N_n with k fixed points, and (good for them) cite Hanson, Seyffarth and Weston 1982 as the originators of this notation.
- Martin, 2001

- d_m
Goulden and Jackson, 1982.
-----------------------------------------------------------------------------------------

I do not doubt any of these notations, and would applaud any author for any notation IF they simply defined the notation a long the way.

The Niven book is his well known Mathematics of Choice, and he uses the symbol D(n) . In 1997 Robert Dickau used$D_n$ for derangements, another common name for subfactorials.    John Baez used !n  in 2003 without indicating that it was an uncommon symbol.

The formula for subfactorial, also called derangements of a set, is given by $!n = n!( 1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}..... \frac{1}{n!} )$,  The quick approximation is !n = n!/e.

---------------------------------------

SOOOOOOOOOOOO, let's go back to the beginning.  "Euler worked for a king, Frederick the Great of Prussia. When the King asks you to do something, he’s not really “asking.” In the late 1740’s and early 1750’s, the King “asked” Euler to work on a number of practical problems. For example, the King had a party palace named Sans Souci. Euler was asked to design the hydraulics to run the fountains at Sans Souci. He also asked Euler to do the engineering on a canal. Another time, when the King was running out of money, he asked Euler to calculate the probabilities so the King could try to pay his debts by running a lottery.

At about the same time, Euler was turning his talents to analyzing ordinary and frivolous things. He solved the Königsburg Bridge Problem, and the Knight’s Tour problem, as well as analyzing some lotteries other than the one the King asked about. Among these other problems was a card game, called “le jeu de rencontre,” or “the game of coincidence.” He reported his results in a paper, E-201, published in the Mémoires of the Berlin Academy under the title “Calcul de la probabilité dans le jeu de rencontre.” Richard Pulskamp’s translation of this article is available on line, and the original, besides appearing in Series I Volume 7 of the Opera Omnia, is on line through the Euler Archive [EA]and the Berlin Academy [B]. "  [How Euler Did It by Ed Sandifer]

The game, in Euler's paper, was played by two players each with n shuffled cards.  Players A turns over his top card and then B turns over his.  If at any point they match, A wins.  If they never march B wins.  Euler arrived at the conclusion that the Probability of A winning before the n cards are exhausted was $( 1- \frac{1} - \frac{1}{2!} + \frac{1}{3!}..... \frac{1}{n!} )$

Since this is the probability that A wins, the probability that there is no matcjh, and the cards are all mis-matched ia simply none minus the probability that A wins,  (this is why the mysterious switch of + and - from even terms to odd terms).

In counting derangements, we want the number of possible ways that the cards could be mismatched out of the n! ways Player A's cards are arranged.  So we multiply n!(1-P(A)).

For those who may think the !n notation is not still in regular use, I searched Google books and found a short list of the them from the first eight books that came up after the year 2000 on the first page of the search.  [Out of pure curiosity I continued on to the 2nd page and found the first to use Dn,  Enumerative Combinatorics from 2018.

Difference Equations, Discrete Dynamical Systems and ... - Page 135

Numbers Are Forever - Page 31

Mathematica Navigator: Mathematics, Statistics, and Graphics, Heikki Ruskeepää · 2004 page 437

It may be that different advanced disciplines have favorite terminology. I would be curious which terms are used in High School textbooks.  If your text covers the subject, I request the book used an an image of the symbol used if possible. Would also love to receive similar information from pre-university age teachers/students in other countries.  Thanks in advance for any responses.