Combinatorial Proofs of Two Hagen-Rothe Identities in Concrete Mathematics

There are two binomial coefficient identities in Concrete Mathematics that have bothered me for years:  They look they should have combinatorial proofs, but I couldn’t for the life of me think of what those might be.  (In Concrete Mathematics they are proved with generating functions.)  Well, I just recently found those combinatorial proofs I was looking for.

Here are the identities. [2, p. 202]

(1)  \displaystyle \sum_k \binom{tk+r}{k} \binom{tn-tk+s}{n-k} \frac{r}{tk+r} = \binom{tn+r+s}{n}.

(2)  \displaystyle \sum_k \binom{tk+r}{k} \binom{tn-tk+s}{n-k} \frac{r}{tk+r} \cdot \frac{s}{tn-tk+s} = \binom{tn+r+s}{n} \frac{r+s}{tn+r+s}.

The key idea I didn’t have before is the general ballot theorem, which states that the number of lattice paths from (0,0) to (n,m), m > rn, that never touch the line y = rx after (0,0) is given by \frac{m-rn}{m+n} \binom{m+n}{m}. This can be proved combinatorially; see, for example, Renault’s paper [5].

Identity (1) counts the number of lattice paths from (0,0) to (n, (t-1)n + r+ s).  The right-hand side is straightforward, since \binom{n+m}{n} counts the number of lattice paths from (0,0) to (n,m).  For the left side, condition on the number of right steps k a lattice path takes after touching the line y = (t-1)x+s for the last time.  By the general ballot theorem, the number of paths from (n-k, (t-1)(n-k)+s) to (n, (t-1)n + r + s) that never touch the line y = (t-1)x + s after the initial point is \frac{r}{tk+r} \binom{tk+r}{k}.  (This is because there are k right steps and (t-1)k + r up steps.)  Also, the number of lattice paths from (0,0) to (n-k, (t-1)(n-k) + s) is \binom{t(n-k)+s}{n-k}.  Summing over all possible values of k gives the left side of Identity (1).

Identity (2) is similar, although it counts the number of lattice paths from (0,0) to (n, (t-1)n + r + s) that never touch the line y = (t-1)x after (0,0).  The right side follows from the general ballot theorem.  For the left side, condition on the last place (k, (t-1)k + r) a lattice path touches the line y = (t-1)x + r.  By the general ballot theorem, there are \frac{r}{tk+r} \binom{tk+r}{k} paths from (0,0) to (k, (t-1)k + r) that never touch the line y = (t-1)x after (0,0).  Also by the general ballot theorem, there are \frac{s}{tn-tk+s} \binom{tn-tk+s}{n-k} lattice paths from (k, (t-1)k + r) to (n, (t-1)n + r + s) that never touch the line y = (t-1)x + r after the initial point.  Multiplying these together and summing over all values of k gives the left side.

I don’t think these proofs are new; for example, Chu [1] mentions lattice path proofs of these identities in books by Mohanty [3] and Narayana [4].

References

  1. Wenchang Chu, “Elementary Proofs for Convolution Identities of Abel and Hagen-Rothe,” Electronic Journal of Combinatorics 17, Note #N24, 2010.
  2. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.
  3. S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, 1979.
  4. T. V. Narayana, Lattice Path Combinatorics with Statistical Applications, Univ. of Toronto Press, 1979.
  5. Marc Renault, “Lost (and Found) in Translation: André’s Actual Method and Its Application to the Generalized Ballot Problem,” American Mathematical Monthly 115 (4), 2008, pp. 358-363.
Advertisements
This entry was posted in combinatorics, lattice paths. Bookmark the permalink.

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