COMBINATORIAL PROOF

 COMBINATORIAL PROOF

or "TELL ME A STORY"

 

Proofs can be approached either as algebraic solutions that show one side can be manipulated to look just like the other (Trig and Inductive proof are common examples) or as ‘stories’ describing how the left side counts the same thing as the right side (combinatorial proof, aka combinatorial agruments).  The clue to story telling is restating the math symbols in some form that explains what’s going on.

Here are some examples with principles that often apply.

----------------------------------------------------------------------

AN EXAMPLE OF THE RULE OF SUMS

First, describe the math purpose.
In how many ways can r items be chosen from a sample of n items? 

Next, tell a simple story.  
The Story:  There are n people in the Math club and you need a committee of r people to organize the Awards Dinner. That's all that's needed for the left side, but (n-1) needs to be addressed for the right side, so...  One member is named Laurel.  In how many ways can the committee be chosen? 

LEFT HAND SIDE (FHS):  (n,r) counts the number of ways a committee of r people can be chosen from all club members.  This situation tells how many different committees are possible, with or without a particular member.

RIGHT HAND SIDE (RHS): The committee could include Laurel or not include Laurel and the total number of ways to set up the committee is all those WITH Laurel plus all those WITHOUT Laurel.

If Laurel IS already on the committee, there are n-1 people left to choose from and r-1 seats left to fill for the other committee members (n-1,r-1).  If Laurel is NOT on the committee, there are only n-1 people to choose from and r places on the committee to fill (n-1,r).

CONCLUSION:  Using the Rule of Sums, the LHS and RHS count the same thing. Ergo, the sides are equal.

-------------------------------------------------------------------------

AN EXAMPLE OF COMMITTEE CHOSEN FROM A SUBGROUP OF THE POPULATION

USING THE RULE OF PRODUCT

To make this story create itself, I would "label" each of the variables:
n = the total population
m = the subgroup 
k = the committee

A STORY:  In how many ways can you select a committee of k people out of a subgroup of m members from a total population of n people?


LHS:  First select the subgroup (n,m).  From these group members, select k to be on the committee (m,k).  This part often seems easy.

RHS:  First select a k-member committee out of the n-member population (n, k).  Next, from the population NOT chosen for the committee (n-k), count the number of possible groups (m) that DO NOT contain people already chosen for the committee (m-k): (m-k) out of (n-k).  (n-k,m-k)  Labeling the variables helps to make this side easier to explain. OK, so even THAT doesn't appear obvious, but it's a direct translation of the term labels.  The problem is defined by applying the math symbols and the labels.  The Rule of Products states that if there are A ways of doing something (selecting committee members) and B ways of doing another thing after that (selecting non-committee subgroup members), then there are A times B ways of performing both actions.  This problem includes both selecting the subgroup AND the committee, just in an order that seems counter-intuitive.  The best bet is to just describe the math as it happens in the problem.


CONCLUSION:  Since both sides count the same thing, they must be equal.

------------------------------------------------------------------------

ANOTHER EXAMPLE USING DIALOGUE AND ALGEBRA

In a problem like this, labeling is a vital part of creating a story.  Start by defining that pesky 2n.
Assume there is a bag of n red marbles and n blue marbles.  Total marbles = 2n

THE STORY:  In how many ways can 3 marbles be chosen?

LHS:  Total number of ways to pick 3 marbles out of a group of 2n.

RHS:  Option 1 - all red (n,3)
          Option 2 - all blue (n,3)
          Option 3 - 2 red and 1 blue (n,2)(n,1)
          Option 4 - 1 red and 2 blue (n,1)(n,2)

All possible options =
          (n,3)+(n,3)+(n,2)(n,1)+(n,1)(n,2) =
                2(n,3) + n(n,2) + n(n,2) =
                2(n,3) + 2n(n,2)

CONCLUSION:  Since both sides count the same thing, they must be equal.

---------------------------------------------------------------------

In combinatorial proof, the conclusion is always that both sides count the same thing.  The trick to EXPLAINING (in common terms) why the sides are equal is to create a story, a situation, from the math symbols displayed.  The LHS and RHS are just different ways to count the same number.

If one side involves a SUM,  describe cases that include a segment of the total PLUS the remainder of the total (as in Laurel's case where the committee either includes her or doesn't).

If products are involved, then the counting likely involves a sequence of steps using Rule of Product.  The RHS involves doing the steps in a different order as in the subgroup-committee example.

As the process becomes more obvious, the stories can become more creative.  But to start, let's just keep it simple.