Combinatorics/Counting

From Wikibooks, open books for an open world
Jump to: navigation, search

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[edit]

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 at odd number of times are 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 number of handshakes that occur. Clearly the total number of handshake pairs, or the total number of times hands were extended is

\sum_{i=1}^{n}x_i.

But counting another way it's just 2y\, for each handshake entitled two extended hands. 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)2, so

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

thus

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

so

S = \sum_{k=1}^n{k} = \frac{n(n+1)}{2}.