[Tutor] Calculating a math formula and finding errors

[Danny Yoo]

Hi Jens,

Good grief, this looks like something out of Concrete Mathematics!

    http://www-cs-faculty.stanford.edu/~knuth/gkp.html

Wow.  *grin*


I've looked at the equation that you've listed.  I agree with the marginal
note, because otherwise it makes no sense to iterate through 'j' on the
left hand side of the equation unless 'j' is being used somewhere.  I
don't think it's just a "possibility": i'm almost positively sure the
equation is wrong.

That is, if 'j' weren't being used, we could simplify the inner loop by
just multiplying the whole darn expression by 'n' and be done with it,
without going through the pretensions of doing an iteration.  So I'll
assume that someone mistyped the equation in LaTeX.  *grin*

The equation also doesn't quite make sense until we qualify the domain of
'n'.  What happens if n=0 on the left hand side of the equation?  For what
values of 'n' should we be able to trust this equation?



On Fri, 10 Jan 2003, Michael Janssen wrote:

> > def facul(z):
> >   if z ==1:
> >     return 1
> >   else:
> >     return z*facul(z-1)

This looks like the factorial function, z!, that pops up in a lot of
combinatorial math.  The definition above, though, doesn't define 0!: you
may want to change the base case of the recursion here so that 0! works.



> > def perm(x,y):
> >   w = 1
> >   for i in range(y+1,x+1):
> >       w = w * i
> >   return w/facul(x-y)

> Would you give us some hints what's this formular is about? I havn't found
> it on the webside. What does "perm" stands for?


I'm not quite sure I understand the perm() function yet either... give me
a moment... Let me plug in a value or two and trace the computation in my
head...

    perm(5, 2) = 3 * 4 * 5 / (3!)
               = 5 * 4 / (2!)
               = 5! / (3! * 2!)

Hmmm... Is this the choosing operation?  I remember that

    (n choose k) = n! / (k!)(n-k)!

from a math class a while back.  Let me try another set of values...

    perm(10, 3) = 4 * 5 * 6 * 7 * 8 * 9 * 10 / (7!)
                = 10! / (7! * 3!)

Ok, I understand now; perm(n, k) stands for the mathematical operation of
how many ways we can choose k items out of a collection on n.  Beware:
your function is broken on perm(n,n) unless you fix facul(0).
Furthermore, your choise of the name 'perm' may confuse some folks, as it
suggests a "permutation of k objects out of n", which is not what the
function is doing.  I'd recommend renaming this function quick before it
confuses anyone else.  *grin*



> > def MBrechts(n):
> >   b=0
> >   for i in range(0,n):
> >     for j in range(0,n-i):
> >       betrag = n + 1 - (2*i) - (2*j)
> >       if betrag < 0:
> >         betrag = betrag * -1
> >       prod = betrag * perm(n-i,j)



The statements:

> >       betrag = n + 1 - (2*i) - (2*j)
> >       if betrag < 0:
> >         betrag = betrag * -1

can be rewritten by using the abs() absolute value function that Python
provides.  Let's revise MBrecths(n) to use abs():


###
def MBrechts(n):
    b=0
    for i in range(0,n):
         for j in range(0,n-i):
             betrag = abs(n + 1 - (2*i) - (2*j))
             prod = betrag * perm(n-i,j)
             b = b + prod
    return b
###

The calculation of the betrag variable doesn't follow the expression that
I'm reading from the PDF document.  Are you sure that it's not:

   abs(n+1 - 2*(i+1))

instead?  The PDF document you pointed us to uses '1' in place of 'i' in
several places of the equation, so there's something screwy going on here.
Can you clarify which is correct?


Good luck!