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

Try Our College Algebra Course. For FREE.

Sophia’s self-paced online courses are a great way to save time and money as you earn credits eligible for transfer to over 2,000 colleges and universities.*

Begin Free Trial
No credit card required

28 Sophia partners guarantee credit transfer.

264 Institutions have accepted or given pre-approval for credit transfer.

* The American Council on Education's College Credit Recommendation Service (ACE Credit®) has evaluated and recommended college credit for 25 of Sophia’s online courses. More than 2,000 colleges and universities consider ACE CREDIT recommendations in determining the applicability to their course and degree programs.



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.