Before you begin with this lesson, you should have studied the binomial coefficient, and be at least somewhat comfortable with summation notation.
Combinatorics is the branch of mathematics concerned with counting things. A common joke told by combinatorics professors goes something like this: "there are three kinds of mathematicians in the world, those who know how to count, and those who don't." And it sounds funny, but counting can be pretty challenging. This packet will introduce you to one of the most important and far reaching combinatorial facts - the principle of double counting.
If the same set is counted in two different ways, you get the same answer.
The above statement sounds a bit like the famous trick question "Which weights more, 100 pounds of bricks or 100 pounds of feathers?" And as obvious as the principle seems, double counting is a breathtakingly powerful tool, applicable to all sorts of complicated problems.
In the following, we see three examples of double counting.
In this video we use double counting to prove two combinatorial equalities. We then spend time proving a property often referred to as the Handshaking Lemma.
