# 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 $+1$s and $-1$s 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 $+1$s 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$.

Advertisements