[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
polyhedra.
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:
http://www.inetarena.com/~pdx4d/ocn/graphics/cubanim.gif
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
approach.
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)
Non-recursive:
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
Triangle:
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):
row.append(pascal(r,c))
print row
>>> reload(series)
<module 'series' from 'G:\Python\series.py'>
>>> series.showpascal(10)
[1L]
[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]
Kirby
Notes:
[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:
http://forum.swarthmore.edu/epigone/amte/phoxtilteld
[4] http://www.teleport.com/~pdx4d/volumes2.html
(all animated GIFs on this page done using Python)