Count Twice!

In this post we’ll look in some detail a very common and important technique in combinatorics, double counting. Let’s start with an easy example involving binomial coefficient

Example 1 Prove that {r \binom{n}{r} = n \binom{n-1}{r-1}}.

There is an obvious way to prove this by algebraic manipulations using the fact that {\binom{n}{r} = \frac{n!}{r!(n-r)!}}. But we are more intersted in a general idea which not only proves this particular identity but also shows us how to come up with such identities. So, here’s one such proof:

Consider a community of {n} people from which you have to select a committee of {r} members with a designated leader. In how many ways can this be done? One way to do this is to choose the {r} members first in {\binom{n}{r}} ways and then choose a leader from them in {r} ways. This gives a total of {r \binom{n}{r}} ways. Other way of doing this would be to first choose the leader, in {n} ways and then from the remaining {n-1} people choose {r-1} to complete the committe. This gives a total of {n \binom{n-1}{r-1}} ways. Thus, we can see that {r \binom{n}{r} = n \binom{n-1}{r-1}}.

This illustrates the typical “procedure” of double counting in proving identities. You look for an object which when counted in one way gives the left hand side and when counted in another way gives the right hand side. I would like to write it as this:

Let {A}, {B} be finite sets and {S} a subset of {A \times B}. Whenever {(x,y) \in S} we say {x} is incident to {y}. If {a_x} denotes the number of elements that are incident to {x \in A} and {b_y} denotes the number of elements that are incident to {y \in B}, then {\sum_{x \in A} a_x = |S| = \sum_{y \in B} b_y}.

Here’s a famous example from graph theory.

Example 2 Let {G} be a finite simple graph with vertex set {V} and edge set {E}. The degree of a vertex {v}, denoted as {d(v)}, is the number of edges incident to {v}. Then we have

\displaystyle \sum_{v \in V} d(v) = 2|E| .

For the proof consider {S \subseteq V \times E}, where {S} is the set of pairs {(v,e)} such that {v \in V} is an end-vertex of {e \in E}. Counting {S} in two ways gives us on one hand { \sum_{v \in V} d(v)}, since every vertex contributes {d(v)} to the count, and on the other hand {2|E|}, since every edge has two ends.

Next let’s consider an interesting identity in number theory:

Example 3 For any natural number {n}, we have {\sum_{j = 1}^n \tau(j) = \sum_{i = 1}^n [\frac{n}{i}]}, where {\tau} is the divisor function and {[.]} is the floor function.

To prove this, let {A = B = \{1, 2, \ldots, n\}} and {S = \{(i,j) ~:~ i ~divides~j\}}.
This identity can be used to prove a surprising result that even though {\tau} is a wildly jumping function its average {\bar{\tau}(n) = \frac{\tau(1) + \tau(2) + \ldots + \tau(n)}{n}} is quite well behaved. In fact,

\displaystyle log(n) - 1 < \bar{\tau}(n) < log(n) + 1.

Proof of this follows easily from the identity and the properties of harmonic numbers.

In example 1, we had a nice combinatorial view of the number {\binom{n}{r}}, namely, it is the number of ways to choose {r} elements from a set of {n} elements. But it might not be that easy in identities involving some other numbers. For example, consider this:

Example 4 Let {F(n)} denote the {n_{th}} Fibonacci number. Then {F(1) + F(2) + \ldots F(n) = F(n+2) - 1}.

To give a double counting proof of this identity we need a combinatorial view of the Fibonacci numbers. That can be done as follows:
Let {f(n)} denote the number of ways in which you can tile a {1 \times n} rectangular board with squares and domnioes. Clearly {f(1) = 1} as you can put only a square and {f(2) = 2} as you can put two squares or a single domino. Thinking recursively we see that a tiling of {1 \times n} rectangular board will either begin with a square or a domino giving us {f(n) = f(n-1) + f(n-2)} for all {n > 2}.
So, it is not difficult to see that {f(n) = F(n+1)} for all {n \geq 0} (letting {f(0) = 1}). Now, we would prove an equivalent identity involving {f},

\displaystyle f(0) + f(1) + \ldots + f(n) = f(n+2) - 1.

The right hand side is the number of ways to tile {1 \times (n+2)} rectangular board by squares and dominoes minus one particular tiling.
Let’s try this: {f(n) - 1} is the number of tilings with at least one domino.
Can we count it in some other way?
Think about what is the position of the last domino in a tiling. Since after we have put the last domino, it’s all squares! With the last domino at {[i+1,i+2]} we have {f(i)} tilings where {i} ranges from {0} to {n}. Hence, we get a total of {f(0) + f(1) + \ldots + f(n)} tilings with at least one domino.

I’ll list some more examples that one can try using these ideas:

Example 5
Prove that {1 \binom{n}{1} + 2 \binom{n}{2} + 3 \binom{n}{3} + \ldots + n \binom{n}{n} = n 2^{n-1}}.

Example 6 Let {S} be a set of {n} persons such that:

  1. Any person is acquainted with exactly {k} other persons in {S}.
  2. Any two persons that are acquainted have exactly {\lambda} common acquaintances in {S}.
  3. Any two persons that are not acquainted have exactly {\mu} common acquaintances in {S}.

Then show that, {k(k- \lambda - 1) = \mu (n - k - 1)}.

In graph theoretic terms this will be stated as, “Given a {k}-regular graph {S} with the property that any two adjacent vertices have exactly {\lambda} common neighbors and any two non adjacent vertices have exactly {\mu} common neighbors, show that {\ldots}.”
Such graphs are known as strongly regular graphs.

Example 7 Show that for all {n \geq 0}, {\binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \ldots = F(n+1).}

Hint: How many tilings have exactly {k} dominoes?

Example 8 Theorem 3 on this post.

Further reading and references

  1. http://www.amazon.com/Proofs-THE-BOOK-Martin-Aigner/dp/3540636986
  2. http://www.amazon.com/Proofs-that-Really-Count-Combinatorial/dp/0883853337
Advertisements

About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics. Bookmark the permalink.

8 Responses to Count Twice!

  1. Anirban Mandal says:

    Nice

  2. Sanjoy Das says:

    Example 5: I have n red balls and I have to select a non-empty set of balls and color one of them blue. I can either choose r red balls and then choose one out of those r to color blue (LHS). Or I can first choose the ball to color blue (out of n) and then choose a possibly empty set out of the other n-1 (none of which I color).

    Example 7: I want a list of numbers consisting of only 1s and 2s which sum to n. The first element can be 1 or 2 and then we recurse (RHS). Or I can have a list of n 1s (n C 0) or a list of (n-1) 1s, one of which I choose to swap with 2 ((n – 1) C 1) or a list of (n-2) 1s, two of which I choose to swap with 2 ((n – 2) C 2) and so on … (LHS).

    • Example 5: Saying that you have “n red balls” generally gives the impression that those are identical. You can also look at this way: “From a group of n people select a team and pick a team leader”. Since there is always a leader, the team size will be at least one.

      Example 7: That’s a really nice way of looking at it! 🙂

    • Another way to solve 7:
      Start from the left hand side. Try to get combinatorial view of the number C(n-i,i). It is the number of ways to choose i numbers from {1,2,3,…,n-1} such that no two of them are consecutive. You can prove it by noticing it’s similarity with the number C(n+r-1,r-1), i.e., the number of non-negative integer solutions to x_1 + x_2 + … x_r = n.

      Therefore, the left hand side counts the number of ways to choose a subset of {1,2,…,n-1} avoiding any consecutive numbers. Let us denote this number by f(n). Then f(2) = 2, f(3) = 3. Thinking recursively you can get that f(n) = f(n-1) + f(n-2) (*) for all n>3. Hence, f(n) = F(n+1).

      [(*) count separetly the subsets which contain 1 and those which don’t]

  3. Sanjoy Das says:

    Yeah, in 5 I basically wanted to say I’ll select r items and then one out of those r items again. Couldn’t phrase it well.

    Example 6: So I ask everyone I know to get one rupee from people they know and I don’t. This is (LHS =) = the number of people I know \times (number of people they know who aren’t me and aren’t people I know) = k * (k – \lam – 1).

    (RHS) Also, everyone in the room except (the people I know and me ) = (n – k – 1) will have to pay 1 rupee to exactly \mu people.

    • Correct. I think that is how I’ll explain it to kids in that pre RMO workshop. Thanks!

      Another way to put it, fix a vertex in G and count the number of vertices at distance exactly 2 from it.

      • Sanjoy Das says:

        I initially tried that approach, but then ran into this:

        There are k ({n1, n2 .. nk}) nodes one hop away from me. Each of those k nodes have have (k – (\lam \ + 1)) nodes one hop away from them which are one+ hop away from me. But two nodes, ni and nj might have some common nodes one hop away which are one+ hop away from me. k * (k – \lam – 1) counts these more than once.

      • Yes, my bad. And obviously it should over count since we know that anything that is not your neighbor is at distance 2 from you in such graphs. So that gives (n-k-1) people at distance 2 from you.

        What we are counting here is this: fix a vertex u, count the number of ordered pairs (x,y) such that u-x-y is a length 2 path and u,y are not adjacent. Put in another way, count the number of paths of length 2 starting from u.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s