An Interesting Counting Problem...

I came across an interesting problem on a video from Shai Simonson about Discrete Math. The question was to count all the possible permutations of a subset drawn from n items.

The count would seem to be direct enough. Just take every possible subset, and count the permutations of that subset. There would only be one subset with n-items and it has n! permutations.. there are n choose k permuations with n items, and they can be permuted in k! ways.. so we could write the whole sum as P(n)= If we enumarate a few we see a pattern: P(0)=1; P(1)=2, P(2) = 5, P(3) = 16, P(4) = 65.... and from that we sense that P(n)= n P(n-1)+1...

Shai had a nice way to show this is true. Here is my illustration of his approach:

can be rewritten as

and here he does something very clever... he factors n out of each of these terms in the new expression to get

which is just 1+ P(n-1)...

But what do you do with P(n)= n P(n-1)+1. It doesn't seem to have a close form expression that lets you calculate the nth term directly.

Once more Simonson gets creative. He points out that the derangements of n follow a similar recursive sequence, except that d(n)= n [d(n-1)] + (-1)ⁿ .

He points out that this is known to be equal to n! (1/1 - 1/1+ 1/2! - 1/3! + 1/4!... 1/n!)

He then suggests that P(n) could be written as n! (1/1 + 1/1+ 1/2! + 1/3! + 1/4!... 1/n!) which matches the values of all the P(n) I checked, and of course, as n goes to infinity, that is just P(n)= n! e .

Ok, pretty interesting, and in fact, it seems that in all the cases I have tried, the actual value of P(n) is just Int(n! e) . It even works at P(1), and gets closer as n increases.

Try a few, tell me if I overlooked something...

I just thought it was a very pretty math. The comparison to d(n) leading to a really clever limiting value... nice job Sir.

http://www.mathvids.com/subtopic/show/116-combinatorics

More on the SubFactorial Search

My cry for help on locating a use of !n (which I consider to be the most usual symbol currently in use for the number of derangements of n things) was answered in the most usual of places. My great research pal, Dave Renfro, who has read more journals than any three people I know, sent me a link to:
which comes from the questions section of the MAA in 1958. It was obvioulsy not an immediate success, as I also found the use of Chrystal's inverted exclamation mark in "A Note on Derangements", by M. T. L. Bizley © 1967 The Mathematical Association. A UK based association. If any of my British readers know what symbol is currently in use in the UK I would appreciate a note.

Dave also sent me a copy of the (original?) use by Whitworth of his symbol. It clearly indicates that he was modeling it on the Jarrett symbol for factorial...

Even though he was writing only about 40 years after the symbol was created, he was mistaken in assuming that the name came after the symbol. The word factorial was the creation of Louis François Antoine Arbogast Who died in 1803. The symbol now commonly used for factorial seems to have been created by Christian Kramp in 1808, and Jarrett, who created the symbol that Whitworth thought might have been the forerunner of the name, was born two years after Arbogast died, making him three years old when Kramp first used !n. Jarrett invented his symbol in 1827. It occurs in a paper "On Algebraic Notation" that was printed in 1830 in the Transactions of the Cambridge Philosophical Society.
I should add that it is often the case in modern usage, that writers choose to ignore all these symbols for a function approach, with the most common being a D(r), perhaps for Derangements. If you have a book from any period that addresses the topic, I would be grateful for a short comment telling me what symbol (if any) they used, and the year, title and author... (and if your symbol is not shown here, or your date of !n preceedes the 1958 one above, and electronic image would earn my deep gratitude and a mention in some future post).

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)ⁿ. 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.

But That Would Almost NEVER Happen, Would It?

Click on images to see higher resoultion images

A young man in one of my classes, obviously trying to improve his A+ by sucking up to the teacher, mentioned that he had read my recent blog on the pigeon-hole principle. He went on to suggest that he really doubted the idea that 39 people could randomly seat themselves and ALL be in the wrong seat. "It just seems VERY unlikely." he suggested.

Rather than tell him the answer, I set him the task of simulating the activity with a deck of cards. Pull out any suit, say the spades, and really shuffle the remaining cards well. Now we need to decide on an order for the remaining suits, so let clubs be the numbers one to thirteen in order from Ace, two, up to King for thirteen. Then the ace of diamonds can be 14, up through the King of diamonds for 26. Finally the ace of hearts is 27 up to the king of hearts for 39. Now turn over the cards and as you do count, one, two, etc... and if you get a card that is where it should be, stop.. they didn't all sit in the wrong chairs. You need not go on forever, just ten or so trials should give you an idea of whether the event is really, really uncommon, or not so very uncommon.

I didn't tell him that I knew the probability, and that he should probably get three or four trials in a string of ten shuffles in which none of the cards landed in the right place. Such a mis-ordering of the cards was just the idea behind the first critical study of the idea we now call derangements by Leonhard Euler, the great Swiss mathematician. Euler was studying 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 and the original document can be seen here.

So what did Euler discover? Well for larger values of N, say 39 or so, the probability of having a perfect mis-sorting of the items approaches 1/e, or about 36.8%, more than a third of the time. It is not an unusual event at all. For smaller numbers you can find the probability by using the idea shown here for six items..
. This can be rewritten more easily using the factorial notation as P= 1/2! - 1/3! + 1/4! - 1/5! + 1/6! which is only a tiny bit above 36.8%, already very close to the 1/e value given above for the limiting value. If the number of items is even, the series will be a little more than 1/e, and if it is odd (and the last term is subtracted) then the probability will be a little below 1/e, with the propbability approaching 1/e as a limit as n gets greater and greater.

I decided to simulate a lot more times than would be practical with a deck of cards, so I cranked up Fathom, a wonderful simulation software by the folks at Key Curriculum, and had it repeat the experiment of seating the 39 people at random 1000 times, and then count how many landed in the right place. The results are shown in the graph below.

It happened that no one landed in the right place 371 times.... Hmmmm, I guess Euler got it right.