Read Nonplussed! for Free Online Page B

this, write

    which means that

    and pairing the terms after the first makes clear that

    Now, if n is even, the above expression for D n shows that D n > n ! / e and so

    provided that

    and since n ≥2 we require
    If n is odd, D n < n ! / e and now

    provided thatand this means that
    Take these two results together and we have the result. Of course, it can be convincingly argued that m = 0 provides the nicest expression

    and so

    It can also be shown that

    is a generating function for the p n , but that is another story!
    A Generalization
    We have seen that derangements are permutations without a fixed point. The obvious generalization of this is to allow a specific number of fixed points, in which case we approach the general form of rencontres numbers D n (k) , the number of permutations of n objects which have precisely k fixed points,Since the work involved in finding an expression for D n (k) is now trivial, we may as well do just that. If we have k fixed points, which can be chosen inways, we must have a derangement of the remaining n - k numbers and this can be achieved

    in ways. Thus

    And these can be conveniently displayed as a triangular array,

    with the numbers in the leftmost vertical column the number of derangements, of course.
    This means that the probability that a permutation has exactly k fixed points is

    Summing this last expression from k = 0 to ∞ gives the answer 1, essential for a probability distribution. And this has connections with moments of distributions, which have connections with Bell Numbers, and these with partitions – none of which we will enter into here!
    1 Available at www.rose-hulman.edu/mathjournal/archives/2003/vol4-n1/paper2/v4n1-2do.doc .

Chapter 6

    CONWAY’S CHEQUERBOARD ARMY
    Games are among the most interesting creations of the human mind, and the analysis of their structure is full of adventure and surprises.
    James R. Newman
    John Horton Conway is very hard to encapsulate. He is universally acknowledged as a world-class mathematician, a claim strongly substantiated by his occupation of the John von Neumann Chair of Mathematics at Princeton University. His vast ability and remarkable originality have caused him to contribute significantly to group theory, knot theory, number theory, coding theory and game theory (among other things); he is also the inventor of surreal numbers, which seem to be the ultimate extension of the number system and, most famous of all in popular mathematics, he invented the cellular automata game of Life. In chapter 14 we will look at him putting fractions to mysterious use, but here we will be concerned with another cellular game, typically simple, and typically deep.
    The Problem
    Imagine an infinite, two-dimensional chequerboard divided in half by an infinite barrier, as in figure 6.1 . Above the barrier thehorizontal levels are numbered as shown. Chequers are placed on the squares below the barrier and can move horizontally or vertically below it or above it by jumping over and removing an adjacent piece. The puzzle Conway associated with this simple situation is to find starting configurations entirely below the barrier which will allow a single chequer to reach a particular target level above the barrier. It’s very instructive to experiment with the pieces and, having done so, figure 6.2 shows the minimal configurations required to reach levels 1 to 3; in each case the target square T is reached by a single chequer.

    Figure 6.1. The playing area

    Figure 6.2. Reaching (a) level 1, (b) level 2, (c) level 3
    The minimal number of chequers needed to reach levels 1, 2 and 3 is then 2, 4 and 8, respectively. The answer for level 4 is more complicated and, in what might be thought of as our firstsurprise, figure 6.3 discloses that it is not 16 but a full 20 pieces that are needed to reach the target square T.

    Figure 6.3. Reaching level 4
    Table 6.1. The level/chequer-count comparison.

    The second surprise, and the one which will