[Edu-sig] More Lesson Planning

Kirby Urner pdx4d@teleport.com
Fri, 04 Feb 2000 20:19:15 -0800

More re Kirby's Lesson Plan thread:

Been continuing with my lesson planning.  Those of you who 
followed links from my initial two posts (Feb) know that I'm 
essentially using a functional programming approach to talk 
about numeric series, then switching to object-oriented for 

Numeric series (e.g. odd numbers, square numbers) are a 
well-explored topic. If my curriculum is new in some way, it's 
simply that my focus is on series which have simple geometric 
pictures to go with them: square and triangular numbers, cubic 
and tetrahedral numbers.  Even cuboctahedral numbers, with 
1,12,42,92,162... spheres in successive layers of the 
cuboctahedron, with this animated GIF to go with it:


All of these series may be modeled by packing spheres together 
-- a hands-on activity or computer-graphical application 
(I use Povray and VRML) to go with the purely algebraic 

To tie my series together, I go to Pascal's Triangle, already a 
rich source of math topics.[1] The entries result from evaluating 
n!/k!(n-k)! so you can use Python to develop Factorial (fact):

Recursive [2]:

def fact(n):
    # factorial of n, recursive
    if n <= 1: return long(1)
    else: return long(n) * fact(n-1)


def fact(n):
    # factorial of n, non-recursive
    reduce(lambda x,y: long(x*y), range(1,n+1))  

Notice, mathematicians have no problem with:

   5 * 4 * 3 * 2 * 1
   -----------------  i.e. n!/k!(n-k)! where n=5, k=2
   2 * 1 * 3 * 2 * 1

but, from a computational point of view, this is inefficient, 
as a lot of terms "cancel".  We'd do a lot better starting with:

   5 * 4
   2 * 1

In other words, I'd like to start down the factorial path, but 
depending on my value for k, not go all the way down to 1.  
That way I'll get n!/(n-k)! without redundant ops, leaving only 
the final division by k! for n!/(n-k)!k!

def kfact(n,k):
    # n!/(n-k)!
    if k < 1: return 1
    else: return n * kfact(n-1,k-1)

With kfact in place, I have what I need to generate Pascal's 

def pascal(n,k):
    # row n, column k
    return kfact(n,k) / fact(k)
def showpascal(n):
    # print successive rows of pascal's triangle to row n
    for r in range(0,n+1):
        row = []
        for c in range(0,r+1):
        print row

>>> reload(series)
<module 'series' from 'G:\Python\series.py'>
>>> series.showpascal(10)
[1L, 1L]
[1L, 2L, 1L]
[1L, 3L, 3L, 1L]
[1L, 4L, 6L, 4L, 1L]
[1L, 5L, 10L, 10L, 5L, 1L]
[1L, 6L, 15L, 20L, 15L, 6L, 1L]
[1L, 7L, 21L, 35L, 35L, 21L, 7L, 1L]
[1L, 8L, 28L, 56L, 70L, 56L, 28L, 8L, 1L]
[1L, 9L, 36L, 84L, 126L, 126L, 84L, 36L, 9L, 1L]
[1L, 10L, 45L, 120L, 210L, 252L, 210L, 120L, 45L, 10L, 1L]

I suppose all those Ls will be annoying to some. Factorial 
blows up quickly and I didn't want to cap it with mere integers.

I note that in Scheme I wouldn't need to explicitly 'type' my 
return values to make them long.  But most other languages 
don't even support the long integer type, allowing 1000! 
without overflow.[3]

You'll see the triangular and tetrahedral numbers appear as 
diagonals in Pascal's triangle.  Alternative functions might 
therefore return tri(n) or tetra(n) simply by going to the 
relevant (row,col) entry in Pascal's:

def tri2(n):
    # lookup nth triangular number in pascal's triangle
    return pascal(n+1,n-1)
def tetra2(n):
    # lookup nth tetrahedra number in pascal's triangle
    return pascal(n+2,n-1) 

There's also a way to get the Fibonacci's as sums of yet other 
diagonals.  This is my link to PHI, which also figures in my 
geometric bridge from the cuboctahedron to icosahedron via the 
jitterbug transformation.[4]



[1] http://www.inetarena.com/~pdx4d/ocn/binomial.html

[2] I notice the Scheme books do a 'tail-recursive' 
    version of factorial that doesn't require two 
    separate calls to a recursive function, as per
    the above Python def.  This is accomplished by
    embedding a function inside of fibbo.  I know
    Python allows defs within defs -- but can the
    inner defs be recursive?

[3] cite thread on AMTE listserv:

[4] http://www.teleport.com/~pdx4d/volumes2.html
    (all animated GIFs on this page done using Python)