Double Counting: Part 1 – Mattia Giuri's bizarre blog

Double counting is a widely used technique of combinatorics, which consists of counting the same quantity with two different methods so that you can create an equation. Today I’m going to show you some of its application.

Double Counting In A Polyhedron

Does a polyhedron exist with an odd number of faces each having an odd number of edges?

Let’s try counting the edges this way: for each face, we add up the number of its sides. By doing so, every edge is counted twice, so we have to divide the whole sum by two. Anyway, a sum of an odd number of odd numbers is odd, so when we divide by two, we have a non-integer result.

Hence, a polyhedron with such characteristics doesn’t exist.

Double Counting In A Set

We have a set K of 8 elements. For each ordered triplet $(A, B, C)$ of subsets (which may be not distinct) of K we consider the cardinality of their intersection. Find the sum of all of these.

Now, instead of summing all the possible cardinalities, let’s see how much times a single element of K appears in the sum. Fixed an element, the other 7 elements can be placed in the subsets in 8 ways (in or out of A, in or out of B, in or out of C, which are independent so we multiply 2 times 2 times 2).

Hence, each element weighs $8^7$ . We have 8 elements, so the result is

$8^8 = 16777216$

In general, for a set with n elements and intersections of j subsets, the result is

$n \cdot 2^{(n-1)j}$

Double Counting To Make Estimates

Among 25 people, any 5 may form a committee, but no two committees can have more than one element in common. Prove that there must be at most 30 committees.

So, we consider the total number of couples of people we have in a committee: that’s ${5 \choose 2} = 10$ . On the other hand, if two committees had a couple in common, then their intersection would contain more than one person. So all the couples in all the committees must be different.

Given that the total number of couples is ${25 \choose 2}= 300$ we assume we got all the couples for a certain (maximized obviously) number of committees n, than we have:

$10n \leq 300 \Rightarrow n \leq 30$