Combinatorics/Counting

It might seem strange, but counting is one of the most difficult things in mathematics sometimes. In fact, it won't be far from the truth to call combinatorics the art of arranging objects and counting them. Brute force techniques, when objects are counted by enumerating all possibilities usually are doomed to fail in combinatorics and we are forced to rely on various techniques and mathematical ideas. Sometimes when even these ideas fail us we have to be content with establishing giving estimates or bounds of the objects to be counted.

Double Counting

In combinatorics, double counting, also called two-way counting, is a proof technique that involves counting the size of a set in two ways in order to show that the two resulting expressions for the size of the set are equal. We describe a finite set X from two perspectives leading to two distinct expressions. Through the two perspectives, we demonstrate that each is to equal |X|.

Let us look at two examples. The first is called the handshaking lemma and can be stated succinctly as:

At a convention the number of delegates who shake hands an odd number of times is even.

To see this, let $D_{1},\cdots D_{n}$ be the delegates. Let $x_{i}\,$ be the number of times $D_{i}\,$ shakes hands and $y\,$ the total number of handshakes that occur. Clearly the total number of times hands were extended is

$\sum _{i=1}^{n}x_{i}$.

But counting another way it's just $2y\,$ - two extended hands for each handshake $y\,$. So,

$\sum _{i=1}^{n}x_{i}=2y$.

Now how many odd $x_{i}\,$ can be there in the sum. If the number of odd $x_{i}\,$ was odd then their total must have been odd too (say 2a+1). This when added to the sum of the even $x_{i}\,$ (say 2b) would have given an odd number (2a+2b+1). But we just saw that $\sum _{i=1}^{n}x_{i}$ was even. So the number of odd $x_{i}\,$ was even. But that's just another way of saying that the number of delegates who shook hands an odd number of times was even.

Let's take a look at another example. We want to derive the formula for the sum of the first n natural numbers. Suppose we have an (n + 1)×(n + 1) square of points. The number of points on the diagonal is exactly n + 1, and clearly the number of points S that are strictly above the diagonal equals the number of points strictly below the diagonal, so the total number of points in the square is n + 1 + 2S. On the other hand, the total number of points in the square is (n + 1)², so

$(n+1)^{2}=n+1+2S\,$,

thus

$n(n+1)=2S\,$,

so

$S=\sum _{k=1}^{n}{k}={\frac {n(n+1)}{2}}.$