Read Nonplussed! for Free Online Page A

Binomial Inversion, as described in appendix B.
    The statement of this result is that, if two sets of numbers

    are related by the condition

    then

    The result makes the a r rather than the b r the subject of the formula.
    In our case, writing b n = n ! and a r = D r means that we have our

    and so

    becomes

    This means that

    and so

    Table 5.2. The average number of fixed points of permutations.

    And so we have a nice result proved in three nice ways, but where is the surprise? We can reveal the first of three by looking at the average (or expected) number of correct allocations of the n objects.
    The Expected Number of Fixed Points
    Suppose that we perform the experiment of matching the initial arrangement { 1,2,3, …,n} with a random permutation of itself a large number of times, and on each occasion note the number of fixed points. Each time this number of fixed points will be one of { 0,1,2, …,n} and we can calculate the average number of them, E(n) . It might reasonably be thought that, as n increases, this average number increases – but consider table 5.2 .
    The table was constructed for each n by finding the average number of fixed points over 1000 random permutations and then averaging this number over 100 repetitions of the process: that average number of fixed points is clinging very tightly to the number 1, independently of the size of n . It could be, of course, that the program which was written to generate table 5.2 is in error, but in fact it isn’t: the theoretical average number of fixed values turns out to be precisely 1 and is independent of n . This we prove below.
    The expression E(n) is the standard notation for the average, or expected value, and in particular of the number of fixed values of permutations of { 1,2,3, …,n} and is defined by the standard expression

    where q r is the probability of there being precisely r fixed values, which in our case is given by

    The argument is that of the previous section, with the r fixed values chosen in any ofways, leaving the remaining (n -r) numbers to be deranged. Our average value is, then,

    To evaluate the expression, we will change variable by writing s = n - r to get

    where the middle equality uses the symmetry of the binomial coefficients

    This means that

    Multiplying both sides by (n - 1 ) ! results in

    and this expression is just equation (1) on page 53 with n replaced by n - 1. This means that (n - 1 ) ! E(n) = (n - 1 ) ! and so E(n) = 1, independent of n .
    Asymptotic Behaviour
    We have, then, an attribute, E(n) , which is independent of the number of objects n and, if we look a little more closely at our earlier calculations, we can readily see that

    is also practically independent of n .
    Put more positively, 1 - p n is the probability of at least one match with n objects and simple computer calculations show that

    the two match to six decimal places, so it doesn’t really matter whether we play the original Montmort version of the game or the version considered by Euler.
    Figure 5.1 shows the plot of 1 - p n against n as a continuous function of n with that rapid convergence very evident. Put succinctly, there is about a 63% chance of at least one match, virtually independent of n , which is perhaps higher than one might imagine.
    Finally, we will look a little more closely at the series which gives p n .

    Figure 5.1. Asymptotic behaviour
    An Appearance of e
    That expression

    has a familiar look to it and if we examine the first n terms of the Taylor expansion of

    we can see why. The expansion is valid for all x and, in particular, for x = - 1, and at this value the identity becomes

    Of course, this is an infinite series and p n has only a finite number of terms but it provides a hint that e does appear in formulae for D n , and perhaps the nicest example of its type is

    and so

    where m is any number such that
    (Here, the [·] is the floor function defined by [ x ] = the greatest integer less than or equal to x .)
    To see