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

[Kirby Urner]

<FUN>

A few moments of math thru programming just for the
fun of it...

<SETUP>

Definition:  A 'derangement' is a rearrangement of
n things such that none is in its original position.

Starting with 3 letters abc, the two derangements
would be bca and cab.  acb would be a permutation
certainly, but not a derangement, since the first
letter (a) didn't move.

n = 3 in this case (3 things).  As you would expect,
as n goes higher, the number of possible derangements
increases dramatically.

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!]

In other words, we have a series of fractions of the
form 1/t! with alternating sign, where t=0,n.  Multiply
by factorial of n and you're done.  Recall 0! = 1.

Since 2.2a4 doesn't require worrying about overflow,
we can write a simpler factorial program:

   >>> import operator
   >>> def fact(n):
          """
          Return n!
          """
	  if n==0 or n==1: return 1
	  return reduce(operator.mul, range(1,n+1))

As for the fractions, many have written rational numbers
modules, including me.  I include a Fraction class in my
mathobjects package (along with matrix and polynomial
objects)[2]:

   >>> from mathobjects import Fraction
   >>> F = Fraction

Fraction objects know how to perform basic operations, like
addition, taking care of the common denominator issue,
reducing to lowest terms, other stuff like that, behind
the scenes:

   >>> F(1,2) + F(2,3) + F(3,7)  # 1/2 + 2/3 + 3/7
   (67/42)

<SIDEBAR>
In my Math Curriculum of Tomorrow, one of the first things
students get to do is write a fraction class, as it implements
basic math ideas, plus is a great intro to operator overriding.
And since the int vs. long dichotomy will be ever less
pronounced as we move towards Python 3.0, the coding of
such will just get easier.
</SIDEBAR>

</SETUP>

With these preliminaries out of the way, it's time for the
main event:

   >>> 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

   >>> drs(1)
   0
   >>> drs(2)
   1
   >>> drs(3)
   2
   >>> drs(4)
   9
   >>> drs(5)
   44
   >>> drs(6)
   265
   >>> drs(12)
   176214841

<VARIATIONS>

If you don't like the 'flip' mechanism for changing sign, you
might test for whether t is even or odd.  t/2 has no remainder
if t is even, i.e. t%2==0.  So a variation of the above would
be:

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

Or, if you want to get even more compressed...

   >>> from operator import add, sub
   >>> def drs(n):
          """
          Return the number of derangements of n things
          """
          f = 0
          for t in range(n+1):
              f = apply([add,sub][t%2],(f, F(1,fact(t))) )
          return fact(n) * f

(You could also improve readability by changing the name
f to something else.  Having f, F and fact all in play
is a bit heavy on the fs -- but I'll just leave it be at
this point).

</VARIATIONS>

<NOTES>

   [1] William Dunham, 'Euler, The Master of Us All'
       (MAA, 1999), p. 167
   [2] mathobjects package at Oregon Tips:
       http://www.oregon-tips.com/
       under Curricula | Python Programming | Source code

</NOTES>
</FUN>