2009年3月9日 星期一

Convolution Technique in Generating Function (1)

When I was the TA of the course "Combinatorial Analysis" in HKUST, I told students that one of the powerful properties of generating function is "convolution".

(*)To combinatorially construct an object of size n, it is a common way to first construct two smaller objects of size k and M-k (where M is a function of n, say, n or (n-1)), and then join the two smaller objects together.

The most famous example must be finding the Catalan Number. Catalan Number is counting the number of ways to write n "+1" and n "-1" in a row such that the for , the sum of the first k terms (we denote it by ) is NOT negative. For example, when , "+1 +1 -1 -1 +1 -1" and "+1 +1 +1 -1 -1 -1" satisfy the requirement while "+1 +1 -1 -1 -1 +1" does not (the first five terms sum to -1, which is negative).

Now we find out a recurrence of using the technique mentioned in (*). We denote the ith term be .

You know, and . So there exists a smallest such that . ( is impossible if a is odd.)

The terms between and (inclusive) must itself form a Catalan sequence of size 2k. The reason is, if it is not a Catalan sequence, then for some , and then , , i.e. contradicting to the assumption that k is the smallest integer such that . Hence, there are ways to fill in to .

Similarly, the terms between and (inclusive) must itself form a Catalan sequence of size 2n-2k-2. Hence, there are ways to fill in to .

Hence, if k is the smallest integer such that , there are ways to construct a Catalan sequence of size 2n. The value of k can be varied from 0 to n-1. So we have the "convolution recurrence":



Now define the generating function . Reader can check that (by comparing coefficients)



This is what we called "convolution" in the first paragraph. When someone multiplies two polynomials, to find the coefficient of , he has to multiply the term in the first polynomial to the term in the second polynomial. This "one increase, one decrease" property for polynomial multiplication gives the great convenience for the generating function to handle the convolution recurrence for Catalan numbers.

Now, the remaining task is purely algebraic. For , treat as a variable, then it becomes a quadratic equation. By quadratic formula, we have



Requiring has no pole at , we reject and hence


Lastly, apply Newton's binomial theorem to , we arrive at the fact that

沒有留言: