Previous page Next page Navigation bar

Puzzles

In memoriam: Edsger W. Dijkstra

Program Extension 2

Well, the graph of the P(p) function is very nice, and gives us an idea of what is going on. It does not, unfortunately, actually specify the P(p) function: we cannot tell exact values from a graph. It would be really nice to have a straightforward formula for P(p).

So now let us figure out what we need to do.

a merry-go-round

Mathematical Amusements (but not, this time, a diversion)

The number of ways n items can be taken m at a time is called the combinatorial function of n and m, and written either nCm or n choose m, and generally verbalized as “n choose m.” It is equal to n factorial over (m factorial times (n-m) factorial).

You may also know nCm as the elements of Pascal’s Triangle.

The binomial theorem states:

(a + b) to the n-th power equals the sum from i=0 to i=n of nCi times a to the i times b to the (n-i)

Recall our previous equation for the probability function P of p:

The term (1-p) to the n-i power is just a binomial, as with the mathematical amusement above. The two terms being added are 1 and -p. So we can express the n-i power of 1-p as a sum of terms:

Now, what this notations means is that there is a sum of a bunch of terms (that is the leftmost sigma) where each term is the product of an m, a power of p, and a sum (that is the rightmost sigma). But we know multiplication distributes over addition, so the product of mipi and the sum of terms is just the sum of the product of mipi and the terms:

So now we have a sum of a sum of a bunch of things. Addition is commutative, which means it does not matter what order we add things up in, as long as we add them all. So we can switch the order of summation: put the j indexed sum on the outside, and the i indexed sum on the inside. The official mathematical term for this process is interchanging the order of summations. Unfortunately, the range for the index j is expressed in terms of the index i. In order to interchange the order of the summations, we need to figure out how what happens to the bounds for i and j.

As the sum is written, i goes from 0 to n, and j goes from 0 to n-i. So when i is 0, j goes 0, 1, 2, ..., n. When i is 1, j goes 0, 1, 2, ..., n-1. And so forth, until when i is n, j goes from 0 to n-n, or 0. So for every value of i, takes the value 0; for values of i from 0 to n-1, takes the value 1; and so forth. Another way of forming the sum would be for j to take the values 0 to n, and for i to take the values 0 to n-j. So we write the sum this way:

Now, we remember that multiplication distributes over addition, so we can factor the terms inside the sums: we can move all the multiplicative terms that do not depend on the index i from inside the summation with index i to outside that summation, as long as we still multiply by those terms. Now, the combinatorial term depends on i, so that cannot move. The term mi depends on i, so that cannot move. The term (-1)n-i-j can be factored as (-1)n-j(-1)-i, and the (-1)n-j can come outside of the summation over i. The term (-1)-i that is left can turn into (-1)i, as 1/(-1) = -1: for the particular case of -1, the sign of the exponent does not matter. And finally the term pn-j does not depend on i at all, and can come out. So factoring out what we can, we have:

Finally, since j appears primarily in terms of n-j, we substitute k = n-j, which also gives j = n-k. As j goes from 0 to n, k goes from n to 0; but since the order in which terms are summed do not matter, we can have k go from 0 to n. Our expression is finally:

Wowza! You may wonder why we went through all the algebra. We went through the algebra to get to this point. You see, this expression is a polynomial in p. We can compute the coefficients from the vector of counts M.

There is only one more thing. We know that m0 is zero, so the inner sum can be taken from 1 to k instead of 0 to k. But this means the sum for k = 0 has no terms; so the outer sum can also be taken from 1 to n instead of 0 to n. Our program can therefore very easily use 1-based indexes instead of 0-based indexes.

And now we can write a program segment to compute the coefficients of the polynomial. First, we need to put the coefficients somewhere; List 5 is available.

Seq(0,A,1,Dim List 1,1)→List 5End of line

This goes up at the front with the other assignments to the Lists. Now, at the end of the program, we can compute the coefficients. First, we need to sum with index k from 0 to n; we use variable A for k.

For 1→A To Dim List 1End of line

We are going to accumulate a sum; we will put the sum into B.

0→BEnd of line

Now we need to sum for i from 0 to k (B); we put i into C.

For 1→C To AEnd of line

The calculator provides a combinatorial function, nCm, accessed through the probability menu. We first compute the (n-i)C(n-k) value, and put it into D.

(Dim List 1-C)C(Dim List 1-A)→DEnd of line

Then we multiply by mi.

DList 4[C]→DEnd of line

Finally, we multiply by (-1)i: this is -1 if i is odd, and 1 (leaving the value unchanged) if i is even. If i is odd, it will have a fractional part when divided by 2.

If Frac (C÷2)End of line
Then (-)D→DEnd of line
IfEndEnd of line

That is the end of the computation of the term of the innermost sum; we accumulate it and go on to the next term.

B+D→BEnd of line
NextEnd of line

The innermost sum has been computed. All that remains is to multiply by (-1)k; again we use the fact that -1k is -1 or 1 as k is odd or even.

If Frac (A÷2)End of line
Then (-)B→BEnd of line
IfEndEnd of line

We have finished computing the coefficient; we can now store it and go on to the next one.

B→List 5[A]End of line
NextEnd of line

So now the program will compute the coefficients of the polynomial expressing P in terms of p, and leave those coefficients in List 5. We could run the program again, but first we realize there is a very simple way of extending the program yet again!

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 10 April 2006.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

In memoriam: Dijkstra

Introduction

Interpretation

Plan, part 1

Plan, part 2

Code

Extension 1

Extension 2

Final Modification

Bridge Collections

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data