Combinations and binomials

Definition. For each positive integer n and each integer r between 0 and n, C(n,r) is defined as the number of combinations of n things taken r at a time. More formally, C(n,r) is the number of r element subsets of a set with n elements.

Computation of C(n,r) How can we compute C(n,r) for a specific n and r? The classical method is to first prove the binomial theorem and then use Pascal's triangle.

Binomial Theorem. For each pair of integers i and n with 0 <= i <= n, the ith coefficent in the expansion of the binomial is : that is,

Proof. When is multiplied out by the distributive law, the result before like terms are collected is a sum of terms each of which is a product of n things, so many y's and the rest x's. Each of the terms containing i y's can be written in the form and is obtained by choosing the i factors of that will contribute a y to the term. Choosing a set of i factors from a set of n factors is the same a taking a combination of n things taken i at a time. Hence the number of those terms is C(n,i). QED.

Theorem on the compuation of C(n,i) . For a positive integers n and all integers i between 0 and n, .

Proof: The proof is by induction on n. The formula holds for n = 1 since . Now suppose the formula holds for n = k. We want to establish that the formula holds for n = k+1. Write

= = .

Now by the binomial theorem, , so the right hand side can be written

=

=

+ +

Now, by our inductive assumption, and , so with a little algebra,

= = + =

+ = + =

= =

This shows that formula holds for n = k+1 for all i between 0 and k+1. Thus the formula is true in all cases.

QED.

Maple has the word binomial in its vocabulary.

> binomial(80,41);

Problem. We can define the same function in several ways. Fill in the blanks below so that the resulting word will give the same answers as binomial(n,r)

1. By the binomial theorem, using coeff (twice), and expand

> binom1 := proc(n,r)
local x,y;
coeff(`---put something here---`,y^(n-r))
end;

>

> binom1(80,41);

2. By the theorem on computing C(n,r)

> binom2 := (n,r) -> `---put something (the factorial formula) here ---`;

> binom2(80,41);

3. Recursively, using the identity C(n,r) = C(n-1,r) + C(n-1,r-1)

> binom3 := proc(n,r)
options remember;
if n = 0 or r = 0 or r = n then 1 else
`---put something (binom3(---) + binom3(---)) here---` fi end;

> binom3(80,41);

>

Problem. Test these various definitions for range and efficiency. Which one gives faster results for large n and r towards the middle? Use the time() function. Do any of them break down before Maple does? Below is a timed test of binomial.

> restart;
ti := time();
binomial(590,247);
time() - ti;

We put the restart in because Maple saves computations and uses them again if it can.

>

Problem. Make a Pascal triangle with Maple.

Combinations and trinomials

Trinomial theorem. .

Proof. Use the binomial theorem.

Problem. Suppose you want to choose two committees from a group of 100. The steering committe will have 5 members and the cleanup committee will have 15 members. Of course, no one on the steering committee will be on the cleanup committee. How many different ways to do that?

Problem. Analogize (sic) the trinomial theorem to a theorem about the expansion of and make up a problem you could use the theorem to solve.

>