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.

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 *n*C*m* or
, and generally verbalized as “*n*
choose *m*.”
It is equal to .

You may also know *n*C*m* as the elements of
Pascal’s Triangle.

The binomial theorem states:

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 *m*_{i}*p*_{i} and the sum
of terms is just the sum of the product of
*m*_{i}*p*_{i} 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*, *i* from 0 to *n*-1, *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 *m**i* 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 *p*^{n-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 *m*_{0} 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 5

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 1

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

0→B

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

For 1→C To A

The calculator provides a combinatorial function, *n*C*m*,
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)→D

Then we multiply by *m*_{i}.

DList 4[C]→D

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)

Then (-)D→D

IfEnd

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→B

Next

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

If Frac (A÷2)

Then (-)B→B

IfEnd

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

B→List 5[A]

Next

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 ]

Copyright © 2002 Brian Hetrick

Page last updated 10 April 2006.