Convolution Technique in Generating Function (2)

It is quite unexpected that the second part of this passage is posted three months later. Anyway, let me post the link to the first part of this passage. Here, I am going to discuss another counting problem which we can use convolution technique to solve.

Let me recall the key idea again. Convolution of generating functions can be useful when we try to count a class of combinatorial objects, while these objects can be constructed by joining two smaller objects of size k and M-k.

Here comes the question, which looks really unfavourite when you first see it. An n by n square matrix M satisfies the following conditions: (1) every entry is a non-negative integer; (2) the sum of entries in each column is n-1; (3) for any two entries which are both positive, denote the coordinates by and , then .

Below shows a few 4 by 4 matrices which satisfy the three conditions:

, ,

The first two conditions can be easily visualized. The third condition can be visualized as follows: for any non-zero entry, its north-west and south-east direction entries must be all zero.

I will generalize by counting the number of p (number of columns) by q (number of rows) matrices satisfying the three conditions (note: the sum of each column is fixed to be n-1). Let the number of such p by q matrices be . Then our target is finding .

Suppose denote the entry in the first column such that it is the toppest entry in the first column with non-zero entries (i.e. for all .) So the matrix looks like:

The black parts will be with all zero entries (by definition of and by condition 3). So the construction of this matrix can be divided into two parts:
a) constructing a 1 by k sub-matrix such that
with and .

b) constructing the (p-1) by (q-k+1) sub-matrix A such that the three conditions are satisfied.

By simple combinatorics, there are ways to construct part a) (if you do not see why, read the notes "Combinations and Permutations" in Mathematical Database; in particular, it is page 10 to 14) and by definition, there are ways to construct part b). As k can be any value between 1 and q (inclusive), we have the recurrence relation:

Compare this recurrence to the one for Catalan numbers. Do you see the similarity? If so, try to continue. I will complete this passage a few days later (hopefully...).