Introduction to Combinatorics

A long-term project is to turn my combinatorics course, lectured since 2010 at Royal Holloway, into a textbook. I finally sent off the first two chapters to a potential publisher the other day. Any comments would be very welcome. The emphasis in these earlier sections is on establishing the basic principles of enumeration: adding and multiplying choices, bijective proofs, and some fairly basic binomial coefficient identities.

My experience from the course is that students found these things surprisingly difficult, but were also often pleasantly surprised how much they could do (even inventing their own proofs), once they made the effort to think.

My Ph.D student Bill O’Donovan mentioned a rather nice binomial limit to me: let P_n = \prod_{r=0}^n \binom{n}{r} be the product of all entries in row r of Pascal’s Triangle. Then

\lim_{n \rightarrow \infty} \displaystyle \frac{P_{n-1}P_{n+1}}{P_n^2} = \mathrm{e}.

There is a very simple proof using the team-and-leader binomial identities
(n+1)\binom{n}{r} = (r+1)\binom{n+1}{r+1} and its equivalent form
s \binom{n}{s} = n \binom{n-1}{s-1}. The name comes from the one-line bijective proof: either pick a leader from n+1 people and let them choose r followers in \binom{n}{r} ways, or pick a team of r+1 people in \binom{n+1}{r+1} ways and let them elect a leader in r ways. Using these we get

\begin{aligned} P_{n-1} &= \frac{1}{n} \binom{n}{1} \ldots \frac{s}{n}\binom{n}{s} \ldots \frac{n-1}{n} \binom{n}{n-1} \\ P_{n+1} &=  \frac{n+1}{1} \binom{n}{0} \ldots \frac{n+1}{r+1}\binom{n}{r} \ldots \frac{n+1}{n+1}  \binom{n}{n}\end{aligned}

so by mass-cancellation the quotient is simply (n+1)^n/n^n = (1+1/n)^n which, by the miracle of compound interest, tends to \mathrm{e} as n \rightarrow \infty.


Leave a Reply

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

You are commenting using your 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

%d bloggers like this: