Raney’s Lemma

Raney’s Lemma: Given an integer sequence (a_0, a_1, \dots, a_{m-1}) whose sum equals unity, there exists a unique j such that every partial sum of the sequence (a_j, a_{j+1}, \dots, a_{j+m-1}) is positive, indicies being computed \mod m.

The standard proof for this fact is geometric. It starts by extending the above sequence to an infinite periodic sequence, b_n, for all non-negative integers such that b_p = a_q, whenever p \equiv q \mod m. Since the new sequence of partial sums obeys s_{km+n}=k+s_n, where 0 \le n < m, the plot of s_n for n \ge 0 has an average slope of \frac{1}{m}. In fact, the sequence s_n can be completely contained within two lines of slope \frac{1}{m}. But lines of slope \frac{1}{m} meet integer points only once every m units. Thus, the lower line meets the integer partial sum sequence exactly once in the canonical period 0 \le n < m, which is the required point (j, s_j).

The above lemma, sometimes also called the Cycle Lemma, immediately solves the following problem: How many sequences of length 2n+1 consisting only of +1s and -1s and summing to unity have all positive partial sums? A straightforward generalization of the above enumeration problem asks us to count the number of m-Raney sequences: How many sequences of length mn+1 consisting only of +1s and (1-m)s and summing to unity have all positive partial sums?

qchu uses Raney’s Lemma to find the number of k-ary trees with n nodes, making use of a bijection with k-Raney sequences of length kn + 1.

About these ads

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