janmr blog

Where Did pi Come From?

The Catalan number CnC_n denotes the number of forests with nn nodes. In fact, the Catalan numbers relate to many different structures, see, e.g., the pages linked to above and the references on those pages.

A formula for the Catalan numbers is given by

Cn=(2n)!n!(n+1)!C_n = \frac{(2n)!}{n! (n+1)!}

with the asymptotic behaviour

Cn4nπn(n+1).C_n \sim \frac{4^n}{\sqrt{\pi n} (n+1)}.

But where did that pi come from? What do trees have to do with pi? That was the subject of Donald E. Knuth's 16th Annual Christmas Tree Lecture, given on December 6, 2010.

As it turns out, a connection between the asymptotic behaviour of Catalan numbers and circle areas can be found through the Wallis product formula,

π2=212343456567.\frac{\pi}{2} = \frac{2}{1} \cdot \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \cdot \frac{6}{7} \cdots.

In 2007, Johan Wästlund from Linköping University published a paper called An Elementary Proof of the Wallis Product Formula for pi (The American Mathematical Monthly, 2007, volume 114, issue 10, pp. 914). He shows a beautiful elementary proof that relates the infinite product on the right-hand side above to the area of circles. The paper is also available online.

Knuth uses this result to show how pi appears in the asymptotic formula for Catalan numbers. In fact, the same result also explains why pi appears in Stirling's formula,

n!2πn(ne)n.n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n.

See, e.g., exercise–5 in The Art of Computer Programming, Volume 1.

You can watch the lecture by Knuth online. I highly recommend it.