**Raney’s Lemma:** Given an integer sequence whose sum equals unity, there exists a unique such that every partial sum of the sequence is positive, indicies being computed .

The standard proof for this fact is geometric. It starts by extending the above sequence to an infinite periodic sequence, , for all non-negative integers such that , whenever . Since the new sequence of partial sums obeys , where , the plot of for has an average slope of . In fact, the sequence can be completely contained within two lines of slope . But lines of slope meet integer points only once every units. Thus, the lower line meets the integer partial sum sequence exactly once in the canonical period , which is the required point .

The above lemma, sometimes also called the Cycle Lemma, immediately solves the following problem: How many sequences of length consisting only of s and 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 -Raney sequences: How many sequences of length consisting only of s and s and summing to unity have all positive partial sums?

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

### Like this:

Like Loading...

*Related*