Combinatorics Principles: Double Counting

Combinatorics Principles: Double Counting

Author: c o

To introduce the subjet of combinatorics
To apply the technique of double counting to several interesting examples

We learn one of the most important mathematical techniques - proof by double counting - and see several examples of the technique in practice.

See More
Introduction to Psychology

Analyze this:
Our Intro to Psych Course is only $329.

Sophia college courses cost up to 80% less than traditional courses*. Start a free trial now.



Before you begin with this lesson, you should have studied the binomial coefficient, and be at least somewhat comfortable with summation notation.

Combinatorics In General

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.

The Double Counting Principle

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.

Double Counting In Practice

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.