[Edu-sig] Speaking of factorials...

[Kirby Urner]

While we're on the subject, I just wanted to go over 
something about the combination function, defined as

                      n!
   combo(n,k) =    --------
                   k!(n-k)!

You find this guy all over in math.  You can use it to 
derive the kth term in row n of Pascal's [famous] Triangle 
for example.

Citations:
  http://www.mathforum.com/epigone/math-learn/zulphingyee/
  http://www.mathforum.com/epigone/math-learn/snoipumkhee/

But it's wasteful to implement this expression literally,
without interpretation.  Terms on the bottom inevitably
cancel with terms on the top, so you end up "throwing away" 
some of the multiplications -- so why do 'em in the 
first place?

For example, consider combo(10,4) =

    1*2*3*4*5*6*7*8*9*10
    --------------------
    1*2*3*4 * 1*2*3*4*5*6

You can use either the k! or the (n-k)! to cancel 
multiplications in the numerator.  One should take one's
pick and do so, rather than carry out all multiplications
both above and below.

Using Guido's little timer guy from his excellent essay at 
http://www.python.org/doc/essays/list2str.html (scroll down),
we can test the relative efficacy if canceling (goodcombo), 
vis ignoring the opportunity (badcombo):

 >>> def goodcombo(n,k):
        return reduce(mul,range(n,n-k,-1))/reduce(mul,range(1,k+1))

 >>> def badcombo(n,k):
	 return (reduce(mul,range(1,n+1))/
     	       (reduce(mul,range(1,k+1))*reduce(mul,range(1,n-k+1))))

  >>> import time
  >>> def timing(f, n, a, b):
         print f.__name__,
         r = range(n)
         t1 = time.clock()
         for i in r:	    
             f(a,b); f(a,b); f(a,b); f(a,b); f(a,b); f(a,b)
             f(a,b); f(a,b); f(a,b); f(a,b)
         t2 = time.clock()
         print round(t2-t1, 3)

  >>> timing(goodcombo,500,10,6)
  goodcomb 0.275
  >>> timing(badcombo,500,11,6)
  badcomb 0.453

I rest my case.

You'll frequently find variants of badchoice in Python modules,
e.g. here in in Robert Kern's totally awesome and way cool clifford.py
at http://starship.python.net/crew/kernr/source/clifford.py

 def comb(n, k):
      """\
      Returns /n\\
              \\k/
    
      comb(n, k) --> PyInt
      """

      def fact(n):
          return Numeric.multiply.reduce(range(1, n+1))

      return fact(n) / (fact(k) * fact(n-k))

Easier to read, maybe, but not faster to run.

Speaking of Clifford Algebra, that's the next big thing in geometric
algebra (GA) these days and finding a way to bring GA to secondary 
schools is a front lines curriculum writing challenge.  Maybe Python
can help, as per this post to a Community Colleges list (one of mine, 
of yesterday):

http://www.mathforum.com/epigone/mathedcc/lorswinbleh

Kirby