[Edu-sig] <FUN>more math with Python</FUN>

[Tim Peters]

]Kirby Urner]
> ...
> Euler found an way to get the total number of possible
> derangements of n as a function of n (a breakthrough!).
> The formula is [1]:
>
> drs(n) = n! * [1/0! - 1/1! + 1/2! - 1/3! + ... + ((-1)^n)/n!]

Note that the sum in brackets consists of the first n+1 terms of the Taylor
expansion of e**-1 around 0, so is a good approximation to 1/e (e being
2.71828..., of course).  In fact, it's such a good approximation that

    drs(n) == round(n!/e)

where round(x) rounds x to the nearest integer, for all n >= 1.  An old
probability teaser asks:  "N gentlemen check in their hats at the country
club.  If the hats are given back to them at random, what's the probability
that no gentleman gets back his own hat?".  Because of the equality above,
the probability approaches 1/e ~= 37% as N increases, and is already within
spitting distance of 37% for N==4.

If the students are advanced enough, it's an interesting exercise to find
the smallest n for which the limitations of floating-point arithmetic cause
round(n!/e) to return a different result than your exact computation using
rationals.

>    ...
>    >>> def drs(n):
>           """
>           Return the number of derangements of n things
>           """
>           f = 0       # f: running total of fractions
>           flip = 0    # sign changer
>           for t in range(n+1):  # t = 0 thru n
>              if flip:
>                 f -= F(1,fact(t))
>                 flip = 0
>              else:
>                 f += F(1,fact(t))
>                 flip = 1
>        return fact(n) * f

And later you flipped in a different way, by testing the parity of t.  A
common idiom in numeric programs is to multiply by 1 or -1 instead, like so:

    f = 0
    sign = 1
    for t in range(n+1):
        f += sign * F(1, fact(t))
        sign = -sign
    return fact(n) * f

As a *programming* issue, it's thus interesting to consider whether
F.__mul__ should or shouldn't try to recognize the special cases of
multiplication by 1 and -1.  There's isn't a "one size fits all" answer, so
it's not for students with low tolerance for uncertainty <wink>.