Enumerating positive walks

In my last post, we saw that the number of positive up-down walks (going either up by $1$ or down by $1$ at each step) of length $2n$ starting from $(0,0)$ is $\binom{2n}{n}$. Furthermore, the number of these that return to height $0$ at the end is the $n$th Catalan number $\frac{1}{n+1}\binom{2n}{n}$. It is natural to ask, then: how many positive walks of length $2n$ end at height $h$ for a given $h$?

This question was brought up at the dinner table last week by Carlos Shine, who leads the Brazilian IMO team and was also one of my coworkers at the IdeaMath summer camp last week in San Jose. In classic mathematician style, we asked the waiter for a pen and began scribbling on the nearest napkin.

Table of values and a recursion

The first thing we noticed was that the ending height is always even, since we change the parity by $1$ at each of the $2n$ steps. So let the ending height be $2k$, and define $f(n,k)$ to be the number of positive up-down walks of length $2n$ ending at height $2k$. We can simply list out the possibilities for the first few values of $n$ to make the following table of values of $f(n,k)$.

Positive and recurrent walks

It is rather well-known that the number of up-down walks that start at $0$ and stay nonnegative until ending at $0$ after $2n$ steps is the $n$th Catalan number, $C_n=\frac{1}{n+1}\binom{2n}{n}$. Such paths, in which we either go up by $1$ or down by $1$ at each step and never fall below the $x$-axis, are called Dyck paths. An example for $n=5$ is shown below.

What is not so well-known is that:

The number of up-down walks of length $2n$ that stay nonnegative, but do not necessarily return to $0$ at the end, is simply $\binom{2n}{n}$.

This fact came up in my research a few days ago, and I figured that this had to be a trivial theorem that was easy to prove. Several hours of failed attempts later, I found myself googling “positive walks central binomial coefficients” and came across a wonderful recent paper of M. van Leeuwen.

Symmedians and circumcircles

Classical Euclidean geometry is one of the oldest branches of mathematics, and in my opinion still as beautiful as ever. Here is a cute little geometric gemstone that was introduced to me recently by a fellow staff member at MOSP.

Consider a triangle $ABC$ drawn in the plane. Let $M$ be the midpoint of $BC$, and let $O$ be the circumcenter of triangle $ABC$, that is, the center of the circle $\Omega$ passing through $A$, $B$, and $C$.

Now let $\omega$ the circumcircle of triangle $BOC$, and let $D$ be the point on $\omega$ outside of $ABC$ for which $MD$ is perpendicular to $BC$. Then it turns out that the line $AD$ can be obtained by reflecting the median $AM$ across the angle bisector of angle $A$! This reflection of $AM$ is called a symmedian of the triangle.

How can we go about proving this? Well, it suffices to show that angle $BAD$ is congruent to angle $CAM$. One way to go about showing angle measures are equal is by finding similar triangles. Triangles $AMC$ and $ABD$ look promising; let’s start by calculating angle $ABD$. This is equal to angle $B$ plus angle $CBD$, which is an inscribed angle on circle $\omega$. By the inscribed angle theorem (there is a beautiful interactive demonstration at that link!) angle $CBD$ is equal to angle $DOC$, which is half the arc $BC$ on circle $\Omega$. Thus angle $DOC$, and hence angle $CBD$, is equal to angle $A$ of the triangle.

Olympiad vs. research mathematics

Recently, some interesting discussions on math education and mathematical philosophy have taken place on, of all places, my Facebook wall. Since Facebook is a rather restrictive medium, I feel it’s time to widen the scope of my blog to include such topics.

I am currently sitting in the main common area in our residence halls at the Math Olympiad Summer program (abbreviated MOP) in the middle of Lincoln, Nebraska. It is rather quiet, as the students are all taking their 5th “MOP test” in the last two weeks, and my fellow instructors and graders are either proctoring the tests or preparing more material to teach these brilliant kids.

It got me thinking about a topic that is often discussed among mathematicians and among those in math contest circles: How correlated is mathematical contest ability with mathematical research ability? Does one help or hinder the other? Is the social environment that math competitions create hostile to noncompetitive students, especially women?

Geometry of the real projective plane

I’ll be flying to Nebraska tomorrow to teach at the Math Olympiad Summer Program. One of my more advanced classes will be on projective geometry and how it can help us understand Euclidean geometry. I thought I would share the introduction from my handout, since it is an attempt to demonstrate one of the many reasons projective geometry is such a gemstone:

General projective planes

Let’s start with some general theory. A projective plane is any set $P$, which we call the set of points, and a nonempty collection $L$ of subsets of $P$ called lines, such that the following four axioms hold:

P1: Every pair of distinct points are contained in exactly one line.

P2: Every pair of distinct lines intersect in exactly one point.

P3: There are four distinct points $a,b,c,d\in P$ no three of which lie on a line.

P4: Every line contains at least three points.

Axiom P2 raises some alarms. In Euclidean geometry, we assume that there are parallel lines that never meet, but here, we’re requiring that every pair of lines intersect. So the usual Euclidean plane is not a projective plane.