## Montmort's Problême du Treize

 Let N denote the ordered set of n elements, 1, 2, 3, ..., n. A derangement of N is a permutation of the set N which leaves no element in its original position. How many derangements are there of the set N? In his famous book Essay d'analyse sur les jeux de hazard (1708) Pierre Rémond de Montmort called this 'le probleme de rencontre'. Now in this 1708 edition, Montmort poses this problem for n = 13, so is often called the Problême du Treize. Let us solve an easy case of n = 4. 1 cannot be in the first place, so there are 3 possible places for 1. Any of the remaining 3 numbers can be in the first place. Now it is easy to see that the final two numbers have only one possible position to avoid their original positions, so there are 9 possible derangements of (1, 2, 3, 4). Montmort discussed the Problême du Treize with Nicolas(I) Bernoulli and, to a much lesser extent, with Johann Bernoulli. In the second edition Essay d'analyse sur les jeux de hazard published in 1713, the problem is solved but generalisations are given which are left unsolved. Here is the version of the Problême du Treize that appears in the 1713 edition:

The players draw to see who will be the dealer. Let us call the dealer 'Pierre', and let us suppose that there are as many other players as you like. Pierre takes a full deck of 52 cards, shuffles them, and deals them out one after the other, calling out 'one' as he turns over the first card, 'two' as he turns over the second, 'three' as he turns over the third, and so on up to the thirteenth. Now if, in this whole series of cards, he never once turns over the card he is naming, he pays out what each other player has put up for the game, and the deal passes to the player sitting to his right. But if in this sequence of thirteen cards he happens to turn over the card he is naming, for example, if he turns over an ace as he calls out 'one', or a two as he calls out 'two', or a three as he calls out 'three', etc., he collects all the money that is in play, and begins over as before, calling out 'one', and then 'two', etc. It may happen that Pierre, having won several times, and beginning again at 'one', does not have enough cards in his hand to reach all the way to 'thirteen'; then he must, when he runs out of cards, shuffle the cards, allow them to be cut, and take from the deck as many cards as he needs to continue the game, starting again where he left off in the preceding hand. For example, if in turning over the last card he called out 'seven', in turning over the first card of the new deck, after it has been cut, he must call out 'eight', and then 'nine', etc., up to 'thirteen' - unless he wins again, in which case he begins over, calling out 'one', and then 'two', and so forth, as has already been explained. Thus it appears that Pierre may win several hands in a row, and may even continue the game ad infinitum.

 Montmort asks, "Find in general the expected value to the dealer of the game of Treize." Montmort solves a number of simpler versions of the problem, such as the one stated at the beginning of this page. He includes in the second edition his correspondence on this problem. However, the general problem remained unsolved. Many mathematicians examined the problem, and have given generalisations of it. For example Leonhard Euler in Calcul de la probabilité dans le jeu de rencontre (1743), Abraham de Moivre in The Doctrine of Chances (1756), Johann Lambert in Examen d'une espèce de superstition ramenée au calcul des probabilités (1773), Edward Waring in An Essay on the Principles of Human Knowledge (1794), and Pierre-Simon Laplace in Théorie Analytique des Probabilités (1812).

JOC/EFR January 2015