Determinants of (generalised) Catalan numbers

C. Krattenthaler^{†}

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

                 WWW: http://www.mat.univie.ac.at/~kratt

Abstract. We show that recent determinant evaluations involving Catalan numbers and generalisations thereof have most convenient explanations by combining the Lindström–Gessel– Viennot theorem on non-intersecting lattice paths with a simple determinant lemma from [Manuscripta Math. 69 (1990), 173–202]. This approach leads also naturally to extensions and generalisations.

1. Introduction. Determinants of matrices containing combinatorial numbers have always been of big attraction to many researchers. The combinatorial numbers which are in the centre of the present paper are the Catalan numbers C_{n}, defined by

C_{n} = \frac{1}{n + 1}\binom{2n}{n},

and extensions thereof. (The reader is referred to [43, Exercise 6.19] for extensive information on these numbers.) Numerous papers exist in the literature featuring determinants of matrices the entries of which contain Catalan numbers or generalisations thereof, see [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 18, 22, 23, 24, 32, 33, 35, 37, 38, 39, 40, 41, 42, 44, 45] (and this list is for sure incomplete). The contexts in which they appear are also widespread, ranging from lattice path enumeration (cf. [2, 3, 5, 6, 7, 8, 12, 13, 23, 18, 32, 35, 37, 45]), plane partition and tableaux counting (cf. [2, 11, 16, 22]), continued fractions and orthogonal polynomials (cf. [13, 15, 40, 44, 45]), statistical physics (cf. [7, 8, 32, 37]), up to commutative algebra and algebraic geometry (cf. [24]).

One of the most popular themes in this context is Hankel determinants of Catalan numbers, that is, determinants of the form det_{0≤i,j≤n−1}(a_{i+j}), where the sequence (a_{i})_{i≥0} involves Catalan numbers. (Cf. [30, Sec. 2.7] and [31, Sec. 5.4] for general information on the evaluation of Hankel determinants.) To be more specific, Hankel determinant evaluations such as

2000 Mathematics Subject Classification. Primary 05A19; Secondary 05A10 05A15 05E10 11C20 15A15 33C45.

Key words and phrases. Hankel determinants, generalised Catalan numbers, Fibonacci numbers, Dodgson condensation, non-intersecting lattice paths.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

det_{0≤i,j≤n−1}(C_{i+j}) = 1,  (1.1)
det_{0≤i,j≤n−1}(C_{i+j+1}) = 1,  (1.2)

or

det_{0≤i,j≤n−1}(C_{i+j+2}) = n + 1  (1.3)

have been addressed numerous times in the literature. More recently, it has been observed in [33] and proved in [15] that

det_{0≤i,j≤n−1}(C_{i+j} + C_{i+j+1}) = F_{2n},  (1.4)

where F_{m} denotes the m-th Fibonacci number; that is, F_{0} = F_{1} = 1 and F_{m} = F_{m−1}+F_{m−2} for m ≥ 2.

Let k be a fixed positive integer. Taking the generalised Catalan number C_{n,k} from [27], given by

C_{n,k} = \frac{n − (k − 1)⌊\frac{n}{k−1}⌋ + 1}{n + ⌊\frac{n}{k−1}⌋ + 1}\binom{n + ⌊\frac{n}{k−1}⌋ + 1}{n + 1},  (1.5)

the determinant evaluation in (1.4) has been generalised in [10] to

det_{0≤i,j≤n−1}(C_{(k−1)i+j,k} + C_{(k−1)(i+1)+j,k}) = ∑_{s=0}^{n} \binom{(k − 1)s + n}{n − s}  (1.6)

and

det_{0≤i,j≤n−1}(C_{(k−1)i+j,k} + C_{(k−1)i+j+1,k}) = ∑_{s=0}^{n} \binom{⌊\frac{s}{k−1}⌋ + n}{n − s}.  (1.7)

Many different methods have been employed to prove the formulae (1.1)–(1.4), (1.6), and (1.7), among which are direct determinant manipulations, non-intersecting lattice paths, orthogonal polynomials, and LU factorisation. However, in the author’s opinion, none of the published approaches explains in a satisfactory and uniform way why these identities exist. This is what we aim to do in this article. We show that the above determinant evaluations are actually special cases of families of more general determinant evaluations, which result from a combination of a simple determinant lemma from [29] (see Lemma 1) and the main theorem on non-intersecting lattice paths (see Theorem 2). In particular, Theorem 3, originally due to Gessel and Viennot [22], shows that one can in fact evaluate the determinant det_{0≤i,j≤n−1}(C_{α_{i}+j}) in closed form, where α_{0}, α_{1}, …, α_{n−1} are arbitrary non-negative numbers, thus largely generalising (1.1)–(1.3). Together with the simple determinant expansion in Lemma 4, this explains as well formula (1.4). Moreover, it also enables us to embed (1.4) in a much larger family of determinant evaluations, see Corollary 5.

Starting point for our “explanation” of (1.6) and (1.7) is the (well-known) observation that the generalised Catalan numbers in (1.5) count lattice paths which stay below a slanted line (see (4.1)). Then, altogether, the main theorem on non-intersecting lattice paths, combinatorial arguments involving paths, and the aforementioned determinant lemma, lead in fact again to much more general determinant evaluations, which we present in Theorem 6 (which generalises Theorem 3, and, thus, identities (1.1)–(1.3)), Corollary 7, and Theorem 9, respectively.

The final section, Section 5, is provided here for the sake of completeness. There, we consider generalised Catalan numbers which are different from those in (1.5). We briefly survey the deep results from [18, 23] which are known on Hankel determinants involving these numbers.

We emphasise that we do not address weighted generalisations in this paper. Sometimes these can also be approached by the method of non-intersecting lattice paths (cf. [13, 32, 37, 45] for examples), but often more refined methods are needed (cf. [7, 8, 12, 14, 32, 37]).

2. Preliminaries. In this section we present the two auxiliary results on which everything else in this paper is based: a general determinant lemma and the Lindström–Gessel– Viennot theorem on non-intersecting lattice paths.

We begin with the determinant lemma, which is taken from [29, Lemma 2.2] (see also [30, Lemma 3]). There are many ways to prove it. The “easiest” is by condensation (once one takes the determinant identity by Desnanot and Jacobi which underlies the condensation method for granted; cf. [30, Sec. 2.3]). For alternative proofs see [9, Theorem 2.9], [29], and [30, App. B].

Lemma 1. Let X_{0}, …, X_{n−1}, A_{1}, …, A_{n−1}, and B_{1}, …, B_{n−1} be indeterminates. Then there holds

det_{0≤i,j≤n−1} ((X_{i} + A_{n−1})(X_{i} + A_{n−2}) ⋯ (X_{i} + A_{j+1})(X_{i} + B_{j})(X_{i} + B_{j−1}) ⋯ (X_{i} + B_{1}))

= ∏_{0≤i<j≤n−1}(X_{i} − X_{j}) ∏_{1≤i≤j≤n−1}(B_{i} − A_{j}).

The other auxiliary result that we need is a determinant formula for the enumeration of non-intersecting lattice paths, originally due to Lindström [34, Lemma 1], rediscovered by Gessel and Viennot [22] (and special cases in [20, Sec. 5.3] and in [28, 26]; for a more detailed historical account see Footnote 6 in [32]). Since, as is the case in most applications, we do not need the theorem in its most general form, we state the special case that serves our purposes. The lattice paths to which we want to apply the theorem are lattice paths in the integer plane consisting of horizontal and vertical unit steps in the positive direction. We make the convention for the rest of the paper that this is what we mean whenever we speak of “lattice paths,” unless it is specified otherwise. A family (P_{0}, P_{1}, …, P_{n−1}) of lattice paths P_{i}, i = 0, 1, …, n − 1, is called non-intersecting if no two paths in the family have a point in common. Examples can be found in Figure 1–5. With the above terminology, we have the following theorem.

Theorem 2. Let A_{0}, A_{1}, …, A_{n−1} and E_{0}, E_{1}, …, E_{n−1} be lattice points in the plane integer lattice such that for i < j and k < l any lattice path from A_{i} to E_{l} has a common point with any lattice path from A_{j} to E_{k}. Then the number of all families (P_{0}, P_{1}, …, P_{n−1}) of non-intersecting lattice paths, P_{i} running from A_{i} to E_{i}, i = 0, 1, …, n − 1, is given by

det_{0≤i,j≤n−1} (P (A_{j} → E_{i})),

where P (A → E) denotes the number of all lattice paths from A to E.

3. Determinants of Catalan numbers. In this section we present evaluations of determinants in which the entries involve Catalan numbers. These determinant evaluations generalise Eqs. (1.1)–(1.4). Our first theorem is a common generalisation of Eqs. (1.1)– (1.3). It is originally due to Gessel and Viennot [22, paragraph between Theorems 21 and 22], who gave essentially the proof that we present below.

Theorem 3. Let n be a positive integer and α_{0}, α_{1}, …, α_{n−1} non-negative integers. Then

det_{0≤i,j≤n−1} (C_{α_{i}+j}) = ∏_{0≤i<j≤n−1}(α_{j} − α_{i}) ∏_{i=0}^{n−1} \frac{(i + n)! (2α_{i})!}{(2i)! α_{i}! (α_{i} + n)!}.

Proof. We use the observation C_{m} = (−1)^{m}2^{2m+1}\binom{1/2}{m+1} to rewrite the determinant in question as

(−1)^{\binom{n}{2}+∑_{i=0}^{n−1} α_{i}}2^{n^{2}+2 ∑_{i=0}^{n−1} α_{i}} det_{0≤i,j≤n−1} (\binom{1/2}{α_{i} + j + 1}) .  (3.1)

Then, by taking some factors out of the i-th row of the matrix of which we want to compute the determinant, i = 0, 1, …, n − 1, we obtain

det_{0≤i,j≤n−1} (C_{α_{i}+j}) = (−1)^{∑_{i=0}^{n−1} α_{i}}2^{n^{2}+2 ∑_{i=0}^{n−1} α_{i}} ∏_{i=0}^{n−1} \frac{(\frac{1}{2} − α_{i})_{α_{i}+1}}{(α_{i} + n)!}

× det_{0≤i,j≤n−1} ( (α_{i} + j − \frac{1}{2}) (α_{i} + j − \frac{3}{2}) ⋯ (α_{i} + \frac{1}{2})

· (α_{i} + j + 2)(α_{i} + j + 3) ⋯ (α_{i} + n)).

Now Lemma 1 can be applied with X_{i} = α_{i}, A_{j} = j + 1, and B_{j} = j − \frac{1}{2}. After some manipulation, one arrives at the claimed result. □

Remarks. (a) Clearly, the determinant evaluations (1.1)–(1.3) are all special cases of Theorem 3.

(b) From a conceptual point of view, the “actual” theorem is the determinant evaluation for the determinant in (3.1). In fact, there holds the determinant evaluation (see [30, Theorem 26, (3.12)])

det_{0≤i,j≤n−1} (\binom{A}{α_{i} + j}) = \frac{∏_{0≤i<j≤n−1}(α_{i} − α_{j})}{∏_{i=0}^{n−1}(α_{i} + n − 1)!} \frac{∏_{i=0}^{n−1}(A + i)!}{∏_{i=0}^{n−1}(A − α_{i})!}.

(The cited theorem in [30] is even a q-analogue of the above identity.) This identity is not restricted to integral A and α_{i}: if one interprets the appearing factorials and binomials as suitable expressions involving gamma functions (cf. [25, §5.5, (5.96), (5.100)]), then it continues to hold for real or complex A and α_{i} as long as there do not appear any singularities.

(c) Gessel and Viennot used Theorem 3 to derive tableaux enumeration results, see [22, Theorems 22 and 23].

(d) The most elegant proof of the special cases (1.1)–(1.3) of Theorem 3 is by using non-intersecting lattice paths. For (1.1) and (1.2), these (one figure) proofs appear as side results already in [45]. For (1.3), a corresponding proof is explained in [5], as well as a non-intersecting lattice path proof for the “next” case, the evaluation of the Hankel determinant det_{0≤i,j≤n−1} (C_{i+j+3}). On the other hand, it seems unlikely that the full statement of Theorem 3 can be explained combinatorially.

(e) An ubiquitous determinant is the Hankel determinant det_{0≤i,j≤n−1} (C_{i+j+β}), where β is some fixed positive integer, which, by Theorem 3 with α_{i} = i + β, i = 0, 1, …, n − 1, has a closed form product evaluation. By Theorem 2 and the standard combinatorial interpretation of the Catalan number C_{m} as the number of lattice paths from the origin to (m, m) which never pass above the diagonal x = y, this determinant counts families (P_{0}, P_{1}, …, P_{n−1}) of non-intersecting lattice paths, where P_{i} runs from (−i, −i) to (i + β, i + β) and does not pass over the diagonal x = y, i = 0, 1, …, n − 1. In [16], Desainte– Catherine and Viennot showed that this counting problem is equivalent to the problem of counting tableaux with a bounded number of columns, all rows being of even length. Desainte–Catherine and Viennot solve the counting problem by evaluating the determinant by means of the quotient-difference algorithm (see also [46]). A weighted version of the tableaux counting problem of Desainte–Catherine and Viennot was solved by Désarménien [17, Théorème 1.2]. The determinant and its associated counting problem arise also in the context of the determination of the multiplicity of Pfaffian rings, see Theorem 2 and the accompanying remarks in [24].

It is a simple observation that, given a determinant in which each entry is the sum of two expressions,

det_{0≤i,j≤n−1}(a_{i,j} + b_{i,j})

say, one can use linearity of the determinant in the rows to expand this determinant into the sum

∑_{S⊆{0,1,...,n−1}} det_{0≤i,j≤n−1} (c_{i,j}^{(S)}) ,  (3.2)

where c_{i,j}^{(S)} = a_{i,j} if i ∈ S and c_{i,j}^{(S)} = b_{i,j} otherwise. This sum consists of 2^{n} terms and, normally, will therefore not be very useful. Should it happen, however, that the (i + 1)-st row of the matrix (a_{i,j})_{0≤i,j≤n−1} and the i-th row of the matrix (b_{i,j})_{0≤i,j≤n−1} agree for all i, i = 0, 1, …, n − 2, then most terms in the sum (3.2) would vanish because, for a given set S, there will always be two identical rows in the determinant det_{0≤i,j≤n−1} (c_{i,j}^{(S)}) if there is an s ∈ {0, 1, …, n − 1} with s ∉ S and s + 1 ∈ S. We summarise this last observation in the following lemma.

Lemma 4. For all positive integers n we have

det_{0≤i,j≤n−1}(a_{i,j} + a_{i+1,j}) = ∑_{s=0}^{n} det_{0≤i,j≤n−1}(a_{i+χ(i≥s),j}),

where χ(S) = 1 if S is true and χ(S) = 0 otherwise.

By combining Theorem 3 and the above lemma, we obtain the following corollary.

Corollary 5. Let n be a positive integer and α_{0}, α_{1}, …, α_{n} non-negative integers. Then

det_{0≤i,j≤n−1} (C_{α_{i}+j} + C_{α_{i+1}+j}) = ∏_{0≤i<j≤n}(α_{j} − α_{i}) ∏_{i=0}^{n−1} \frac{(i + n)!}{(2i)!} ∏_{i=0}^{n} \frac{(2α_{i})!}{α_{i}! (α_{i} + n)!}

× ∑_{s=0}^{n} \frac{α_{s}! (α_{s} + n)!}{(2α_{s})! ∏_{j=0}^{s−1}(α_{s} − α_{j}) ∏_{j=s+1}^{n}(α_{j} − α_{s})}.

Remarks. (a) It can be checked that for α_{i} = i, i = 0, 1, …, n, Corollary 5 reduces to

det_{0≤i,j≤n−1} (C_{i+j} + C_{i+j+1}) = ∑_{s=0}^{n} \binom{n + s}{n − s} = ∑_{s=0}^{n} \binom{2n − s}{s}.

In view of the well-known formula

F_{m} = ∑_{s=0}^{m} \binom{m − s}{s}

for Fibonacci numbers F_{m}, this immediately implies (1.4).

(b) Proofs of (1.4) by using non-intersecting lattice paths can be found in [5] and [13, Sec. 3].

4. Determinants of generalised Catalan numbers, I. The purpose of this section is to show how the determinant evaluation in Lemma 1 and Theorem 2 on non-intersecting lattice paths lead to proofs of (1.6) and (1.7), and, in fact, of generalisations thereof.

Let μ be a positive integer. We denote by P ((0, 0) → (c, d) | x ≥ μy) the number of lattice paths starting at the origin and ending at (c, d), which never pass above the line x = μy. Then it is well-known (see [36, Theorem 3]) that

P ((0, 0) → (c, d) | x ≥ μy) = \frac{c − μd + 1}{c + d + 1}\binom{c + d + 1}{d}.  (4.1)

The generalised Catalan numbers in (1.5) are a special case: by (4.1), the number C_{n,k} is equal to the number of lattice paths starting at the origin and ending at (n, ⌊\frac{n}{k−1}⌋), which never pass above the line x = (k − 1)y.

Theorem 6. Let n and k be positive integers and β, α_{0}, α_{1}, …, α_{n−1} non-negative integers with 0 ≤ β ≤ k − 1. Then

det_{0≤i,j≤n−1} (C_{(k−1)α_{i}+j+β,k}) = ∏_{0≤i<j≤n−1}(α_{j} − α_{i}) ∏_{i=0}^{n−1} \frac{((k − 1)i + β + n)! (kα_{i} + β)!}{(ki + β)! α_{i}! ((k − 1)α_{i} + β + n)!}.

Proof. By (4.1) and Theorem 2, we can interpret the determinant in the theorem as the number of families (P_{0}, P_{1}, …, P_{n−1}) of non-intersecting lattice paths, where P_{i} runs from (−(k − 1)α_{i}, −α_{i}) to (i + β, ⌊\frac{i+β}{k−1}⌋) and does not pass over the line x = (k − 1)y, i = 0, 1, …, n − 1.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; ∘; ∘; A_{0}; A_{1}; A_{2}; A_{3}; E_{0}; E_{1}; E_{2}; E_{3}; P_{0}; P_{1}; P_{2}; P_{3}]

A family of non-intersecting lattice paths

Figure 1

If we would directly apply Theorem 2 together with the formula on the right-hand side of (4.1) to the above problem of counting non-intersecting lattice paths, then we would have to deal with a determinant which is not easy to handle directly. However, we may use combinatorics to simplify the determinant. (The following simplifications could also be achieved by row and column manipulations of the determinant. However, they become much simpler and much more transparent in terms of non-intersecting lattice paths.) The simplification is best explained with an example at hand. Let us consider the case k = 3, n = 4, α_{0} = 0, α_{1} = 1, α_{2} = 2, α_{3} = 3, β = 5. Then the starting and end points A_{0}, …, A_{3}, E_{0}, …, E_{3} are as shown in Figure 1, which at the same time shows an example of a family of non-intersecting lattice paths with these starting and end points. (That portions of some paths are indicated by thick lines and some points are circled should be ignored for the moment.) Since the path family is non-intersecting, and since the paths P_{1}, P_{2}, …, P_{n−1} must stay (weakly) below the line x = (k − 1)y and must avoid E_{0}, they must pass to the right of E_{0}. Hence, they must all end with vertical steps above the height at which we find E_{0}, that is, above y = ⌊\frac{β}{k−1}⌋. These vertical steps (in our example in Figure 1 they are indicated by thick lines) can therefore be deleted without changing the enumeration problem. Thus, we may equivalently count families P′_{0}, P′_{1}, …, P′_{n−1} of non-intersecting lattice paths, where P′_{i} runs from

A_{i} = (−(k−1)α_{i}, −α_{i}) to E′_{i} = (i + β, ⌊\frac{β}{k−1}⌋) and does not pass over the line x = (k−1)y, i = 0, 1, …, n − 1. The modified family of paths which corresponds to our example in Figure 1 is shown in Figure 2.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{0}; A_{1}; A_{2}; A_{3}; E′_{0}; E′_{1}; E′_{2}; E′_{3}; P′_{0}; P′_{1}; P′_{2}; P′_{3}]

The non-intersecting lattice paths of Figure 1 without forced vertical steps

Figure 2

If we now use Theorem 2 and (4.1), then we obtain

det_{0≤i,j≤n−1} (C_{(k−1)α_{i}+j+β,k}) = det_{0≤i,j≤n−1} (\frac{j + β + 1}{kα_{i} + j + β + 1}\binom{kα_{i} + j + β + 1}{α_{i}}) . (4.2)

By taking some factors out of the i-th row of the matrix of which the determinant on the right-hand side is taken, i = 0, 1, …, n − 1, we obtain

det_{0≤i,j≤n−1} (C_{(k−1)α_{i}+j+β,k}) = \frac{(β + n)!}{β!} ∏_{i=0}^{n−1} \frac{(kα_{i} + β)!}{α_{i}! ((k − 1)α_{i} + β + n)!}

× det_{0≤i,j≤n−1} ((kα_{i} + β + 1)(kα_{i} + β + 2) ⋯ (kα_{i} + β + j)

· ((k − 1)α_{i} + β + j + 2)((k − 1)α_{i} + β + j + 3) ⋯ ((k − 1)α_{i} + β + n))

= k^{\binom{n}{2}}(k − 1)^{\binom{n}{2}} \frac{(β + n)!}{β!} ∏_{i=0}^{n−1} \frac{(kα_{i} + β)!}{α_{i}! ((k − 1)α_{i} + β + n)!}

× det_{0≤i,j≤n−1} ( (α_{i} + \frac{β + 1}{k}) (α_{i} + \frac{β + 2}{k}) ⋯ (α_{i} + \frac{β + j}{k} )

· (α_{i} + \frac{β + j + 2}{k − 1}) (α_{i} + \frac{β + j + 3}{k − 1}) ⋯ (α_{i} + \frac{β + n}{k − 1}) ).

Now Lemma 1 can be applied with X_{i} = α_{i}, A_{j} = (β + j + 1)/(k − 1), and B_{j} = (β + j)/k. After some manipulation, one arrives at the claimed result. □

Remark. Again, from a conceptual point of view, the “actual” theorem is the determinant evaluation for the determinant on the right-hand side of (4.2). In an equivalent form, this is

det_{0≤i,j≤n−1} (\binom{kα_{i} + j + β}{α_{i} − 1})

= \frac{β!}{(β + n)!} ∏_{0≤i<j≤n−1}(α_{j} − α_{i}) ∏_{i=0}^{n−1} \frac{((k − 1)i + β + n)! (kα_{i} + β)!}{(ki + β)! (α_{i} − 1)! ((k − 1)α_{i} + β + n)!}. (4.3)

By observing that

\binom{kα_{i} + j + β}{α_{i} − 1} = \binom{kα_{i} + j + β}{(k − 1)α_{i} + j + β + 1} = (−1)^{(k−1)α_{i}+j+β−1}\binom{−α_{i}}{(k − 1)α_{i} + j + β − 1},

one sees that the determinant evaluation (4.3) is equivalent to [30, Theorem 26, (3.13)]. In particular, for the validity of (4.3), the restriction on β in the statement of Theorem 6 is not necessary. Moreover, the identity (4.3) continues to hold for real or complex β and α_{i} if one interprets the appearing factorials and binomials as suitable expressions involving gamma functions (cf. [25, §5.5, (5.96), (5.100)]), as long as there do not appear any singularities.

By combining Theorem 6 and Lemma 4, we obtain the following corollary.

Corollary 7. Let n and k be a positive integers and β, α_{0}, α_{1}, …, α_{n} non-negative integers with 0 ≤ β ≤ k − 1. Then

det_{0≤i,j≤n−1} (C_{(k−1)α_{i}+j+β,k} + C_{(k−1)α_{i+1}+j+β,k})

= ∏_{0≤i<j≤n}(α_{j} − α_{i}) ∏_{i=0}^{n−1} \frac{((k − 1)i + β + n)!}{(ki + β)!} ∏_{i=0}^{n} \frac{(kα_{i} + β)!}{α_{i}! ((k − 1)α_{i} + β + n)!}

× ∑_{s=0}^{n} \frac{α_{s}! ((k − 1)α_{s} + β + n)!}{(kα_{s} + β)! ∏_{j=0}^{s−1}(α_{s} − α_{j}) ∏_{j=s+1}^{n}(α_{j} − α_{s})}.

Remark. It can be checked that for α_{i} = i, i = 0, 1, …, n, Corollary 7 reduces to (1.6).

Finally, we address the determinant evaluation (1.7). We shall actually consider the more general determinant

det_{0≤i,j≤n−1}(C_{(k−1)i+j+β,k} + C_{(k−1)i+j+β+1,k}),  (4.4)

where β ≤ k−1. Clearly, we can again apply Lemma 4 (with the roles of rows and columns interchanged) to obtain

det_{0≤i,j≤n−1}(C_{(k−1)i+j+β,k} + C_{(k−1)i+j+β+1,k}) = ∑_{s=0}^{n} det_{0≤i,j≤n−1}(C_{(k−1)i+j+χ(j≥s)+β,k}). (4.5)

By Theorem 2, for any fixed s, the determinant on the right-hand side has a combinatorial interpretation in terms of non-intersecting lattice paths in a manner completely analogous to the one in the proof of Theorem 6: it counts families (P_{0}, P_{1}, …, P_{n−1}) of non-intersecting lattice paths, where P_{i} runs from (−(k − 1)i, −i) to (i + χ(i ≥ s) + β, ⌊\frac{i+χ(i≥s)+β}{k−1} ⌋) and does not pass over the line x = (k − 1)y, i = 0, 1, …, n − 1. Figure 3 shows an example with n = 4, k = 3, β = 1 and s = 2.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; ∘; ∘; ∘; A_{0}; A_{1}; A_{2}; A_{3}; E_{0}; E_{1}; E_{2}; E_{3}; P_{0}; P_{1}; P_{2}; P_{3}]

Another family of non-intersecting lattice paths

Figure 3

Again, if the paths want to stay below the line x = (k − 1)y (being allowed to touch it) and to be non-intersecting, then there are forced path portions. These come in three different flavours. First, for 0 ≤ i < s, the path P_{i} must start with ki + β horizontal steps, followed by as many vertical steps as necessary to reach the end point E_{i}. (See the paths P_{0} and P_{1} in Figure 3.) Second, for s ≤ i ≤ n − 1, the path P_{i} must start with (k − 1)i + s + β horizontal steps. (See the thick portions of P_{2} and P_{3} below the x-axis in Figure 3.) Third, the paths P_{s}, P_{s+1}, …, P_{n−1} must all end with vertical steps above the height at which we find E_{s}, that is, above y = ⌊\frac{s+β+1}{k−1}⌋. Moreover, if E_{s} should lie on the line x = (k − 1)y (that is, if k − 1 divides s + β + 1), then all of P_{s}, P_{s+1}, …, P_{n−1} must have an additional vertical step from height \frac{s+β+1}{k−1} − 1 to \frac{s+β+1}{k−1}. (See the thick vertical parts of P_{2} and P_{3} in Figure 3. In the example, we have indeed that E_{s} = E_{2} lies on x = (k − 1)y = 2y.) The last observation can also be succinctly rephrased by saying that the paths P_{s}, P_{s+1}, …, P_{n−1} must all end with vertical steps above y = ⌊\frac{s+β}{k−1}⌋.

We may delete the forced portions without changing the enumeration problem. (See Figure 4 for the resulting path family after the forced portions have been removed in Figure 3.) The boundary x = (k − 1)y may also be removed without changing the enumeration problem. (See Figure 5 for the result in case of our running example from Figures 3 and 4. The dotted path should be ignored at the moment.) In that manner, we see that the determinant on the right-hand side of (4.5) is equal to the number of families (P′_{s}, P′_{s+1}, …, P′_{n−1}) of non-intersecting lattice paths, where P′_{i} runs from (s + β, −i) to

(i + β + 1, ⌊\frac{s+β}{k−1}⌋), i = s, s + 1, …, n − 1.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A′_{2}; A′_{3}; E′_{2}; E′_{3}; P′_{2}; P′_{3}]

The non-intersecting lattice paths of Figure 3 after removing forced path portions

Figure 4

• _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} . . . . ....... . . . ._{.....}. . . . . • • • • ∘ ∘ A′_{2} A′_{3} E′_{2} E′_{3} S  T

The dual path for the non-intersecting lattice paths of Figure 4

Figure 5

A more general enumeration problem can actually be solved in closed form. We formulate the corresponding result in the proposition below.

Proposition 8. Let a, b, c and α_{0}, α_{1}, …, α_{n−1} be integers with a ≤ α_{0} ≤ α_{1} ≤ ⋯ ≤ α_{n−1} and b ≤ c. Then the number of families (P_{0}, P_{1}, …, P_{n−1}) of non-intersecting lattice paths, the path P_{i} running from (a, b − i) to (α_{i}, c), i = 0, 1, …, n − 1, is given by

∏_{0≤i<j≤n−1}(α_{j} − α_{i}) ∏_{i=0}^{n−1} \frac{(α_{i} + c − a − b)!}{(α_{i} − a)! (c − b + i)!}.

Proof. By Theorem 2, the number in question is equal to the determinant

det_{0≤i,j≤n−1} (\binom{α_{j} − a + c − b + i}{c − b + i}) .

By taking some factors out of the j-th column of the matrix of which we want to compute the determinant, j = 0, 1, …, n − 1, we obtain the equivalent expression

∏_{j=0}^{n−1} \frac{(α_{j} + c − a − b)!}{(α_{j} − a)! (c − b + j)!}

× det_{0≤i,j≤n−1} ((α_{j} + c − a − b + 1)(α_{j} + c − a − b + 2) ⋯ (α_{j} + c − a − b + i)).

This determinant is of the form det_{0≤i,j≤n−1} (p_{i}(α_{j})), where p_{i}(x) is a polynomial in x of degree i with leading coefficient 1, i = 0, 1, …, n − 1. Such a determinant can be easily reduced to the Vandermonde determinant det_{0≤i,j≤n−1} (α_{j}^{i}) by using elementary column operations (see also [30, Proposition 1]). The evaluation of the Vandermonde determinant being well-known, the assertion of our proposition follows immediately. □

We now apply Proposition 8 to obtain the announced generalisation of (1.7).

Theorem 9. Let n and k be positive integers and β a non-negative integer with 0 ≤ β ≤ k − 1. Then

det_{0≤i,j≤n−1} (C_{(k−1)i+j+β,k} + C_{(k−1)i+j+β+1,k}) = ∑_{s=0}^{n} \binom{⌊\frac{s+β}{k−1}⌋ + n}{n − s}.  (4.6)

Proof. Coming back to the enumeration problem which is illustrated in Figure 5, we apply Proposition 8 with n replaced by n − s, a = s + β, b = −s, c = ⌊\frac{s+β}{k−1}⌋, and α_{i} = s+i+β+1, i = 0, 1, …, n−s−1. The claimed result follows upon little simplification. □

Remarks. (a) Clearly, Eq. (1.7) is the special case β = 0 of Theorem 9.

(b) It should be clear that, from a conceptual point of view, Proposition 8 represents the actual key result which is behind Theorem 9. On the other hand, if we are just interested in proving Theorem 9, then we do not need the determinant evaluation in the proof of Proposition 8. Namely, for Theorem 9, we only need the special case of Proposition 8 in which the end points of the paths P_{i} are successive lattice points on a horizontal line, and the first end point is by one unit to the right of the vertical line on which we find the starting points (see Figure 5). The reader is referred to the proof of Theorem 9 for the exact choices of the starting and end points.

There is an elegant argument using the concept of dual paths, an idea which is again due to Gessel and Viennot [21, Sec. 4], to see that the number of families of non-intersecting lattice paths with starting and end points as described above is a binomial coefficient. In order to explain the idea, we let S be the lattice point one unit to the left of the first end point, that is, S = (s + β, ⌊\frac{s+β}{k−1}⌋), and we let T be the lattice point exactly below the last end point, the height of which is by one unit lower than the height of the last starting point, that is, T = (n + β, −n). See Figure 5. We now connect S with T by moving vertically downwards, unless we hit one of the existing paths. If the latter happens, then we continue by a diagonal step (1, −1), etc. The “dual” path which results for our example in Figure 5 is indicated by dotted line segments.

It is easy to see that families of non-intersecting lattice paths connecting the starting and end points as above are in bijection with all paths from S to T consisting of vertical down steps (0, −1) and diagonal down steps (1, −1). However, each such path from S to T has exactly s + ⌊\frac{s+β}{k−1}⌋ vertical steps and n − s diagonal steps, the order of which can

be chosen freely. Thus, there are \binom{⌊ \frac{s+β}{k−1} ⌋+n}{n−s} such paths and, therefore, as many families of non-intersecting lattice paths with the starting and end points as above, in accordance with (4.6).

For a slightly different lattice path proof of (1.5) see [6].

5. Determinants of generalised Catalan numbers, II. Let again k be a fixed positive integer. Rewriting the Catalan number C_{n} in the form

C_{n} = \frac{1}{2n + 1}\binom{2n + 1}{n + 1} = \frac{1}{2n + 1}\binom{2n + 1}{n},  (5.1)

another way to construct “generalised” Catalan numbers is by considering numbers of the form

\frac{l}{kn + l} \binom{kn + l}{n}.

Tamm [44] has studied Hankel determinants involving such numbers to considerable extent. It seems that, beyond k = 3, one cannot expect any closed form results (see also [19]). On the other hand, for k = 3 there exist several beautiful results, with many variations, due to Eğecioğlu, Redmond and Ryavec [18] (for some of them) and Gessel and Xin [23] (for most of them). As the proof methods show, these results lie on a much deeper level than their counterparts in Theorems 3 or 6. In the theorem below, we present the determinant evaluations involving generalised Catalan numbers of the form (5.1). For a complete list see [31, Theorem 31].

Theorem 10. For any positive integer n, there hold

det_{0≤i,j≤n−1} (\frac{1}{3i + 3j + 1}\binom{3i + 3j + 1}{i + j}) = ∏_{i=0}^{n−1} \frac{(\frac{2}{3})_{i} (\frac{1}{6})_{i} (\frac{4}{3})_{i} (\frac{5}{6})_{i}}{(\frac{1}{2})_{2i} (\frac{3}{2})_{2i}} (\frac{27}{4})^{2i} ,  (5.2)

det_{0≤i,j≤n−1} (\frac{1}{3i + 3j + 4}\binom{3i + 3j + 4}{i + j + 1}) = ∏_{i=0}^{n−1} \frac{(\frac{4}{3})_{i} (\frac{5}{6})_{i} (\frac{5}{3})_{i} (\frac{7}{6})_{i}}{(\frac{3}{2})_{2i} (\frac{5}{2})_{2i}} (\frac{27}{4})^{2i} ,  (5.3)

det_{0≤i,j≤n−1} (\frac{1}{3i + 3j + 2}\binom{3i + 3j + 2}{i + j + 1}) = ∏_{i=0}^{n−1} \frac{(\frac{4}{3})_{i} (\frac{5}{6})_{i} (\frac{5}{3})_{i} (\frac{7}{6})_{i}}{(\frac{3}{2})_{2i} (\frac{5}{2})_{2i}} (\frac{27}{4})^{2i} ,  (5.4)

det_{0≤i,j≤n−1} (\frac{1}{3i + 3j + 5}\binom{3i + 3j + 5}{i + j + 2}) = ∏_{i=0}^{n} \frac{(\frac{2}{3})_{i} (\frac{1}{6})_{i} (\frac{4}{3})_{i} (\frac{5}{6})_{i}}{(\frac{1}{2})_{2i} (\frac{3}{2})_{2i}} (\frac{27}{4})^{2i} ,  (5.5)

det_{0≤i,j≤n−1} (\frac{2}{3i + 3j + 1}\binom{3i + 3j + 1}{i + j + 1}) = ∏_{i=0}^{n} \frac{(\frac{2}{3})_{i} (\frac{1}{6})_{i} (\frac{4}{3})_{i} (\frac{5}{6})_{i}}{(\frac{1}{2})_{2i} (\frac{3}{2})_{2i}} (\frac{27}{4})^{2i} ,  (5.6)

det_{0≤i,j≤n−1} (\frac{2}{3i + 3j + 4}\binom{3i + 3j + 4}{i + j + 2}) = ∏_{i=0}^{n} \frac{(\frac{4}{3})_{i} (\frac{5}{6})_{i} (\frac{5}{3})_{i} (\frac{7}{6})_{i}}{(\frac{3}{2})_{2i} (\frac{5}{2})_{2i}} (\frac{27}{4})^{2i} ,  (5.7)

where (α)_{i} := α(α + 1) ⋯ (α + i − 1) is the usual Pochhammer symbol. Let a_{0} = −2 and a_{m} = \frac{1}{3m+1} \binom{3m+1}{m} for m ≥ 1. Then

det_{0≤i,j≤n−1}(a_{i+j}) = ∏_{i=0}^{n−1}(−2)\frac{(\frac{1}{3})_{i} (−\frac{1}{6})_{i} (\frac{5}{3})_{i} (\frac{7}{6})_{i}}{(\frac{1}{2})_{2i} (\frac{3}{2})_{2i}} (\frac{27}{4})^{2i} .  (5.8)

Let b_{0} = 10 and b_{m} = \frac{2}{3m+2} \binom{3m+2}{m} for m ≥ 1. Then

det_{0≤i,j≤n−1}(b_{i+j}) = ∏_{i=0}^{n−1} 10\frac{(\frac{2}{3})_{i} (\frac{1}{6})_{i} (\frac{7}{3})_{i} (\frac{11}{6})_{i}}{(\frac{3}{2})_{2i} (\frac{5}{2})_{2i}} (\frac{27}{4})^{2i} .  (5.9)

Furthermore,

det_{0≤i,j≤n−1} (\frac{2}{3i + 3j + 5}\binom{3i + 3j + 5}{i + j + 1}) = ∏_{i=0}^{n} \frac{(\frac{4}{3})_{i} (\frac{5}{6})_{i} (\frac{5}{3})_{i} (\frac{7}{6})_{i}}{(\frac{3}{2})_{2i} (\frac{5}{2})_{2i}} (\frac{27}{4})^{2i} .  (5.10)

Let c_{0} = \frac{7}{2} and c_{m} = \frac{2}{3m+1} \binom{3m+1}{m+1} for m ≥ 1. Then

det_{0≤i,j≤n−1}(c_{i+j}) = ∏_{i=0}^{n} \frac{(\frac{4}{3})_{i} (\frac{5}{6})_{i} (\frac{5}{3})_{i} (\frac{7}{6})_{i}}{(\frac{3}{2})_{2i} (\frac{5}{2})_{2i}} (\frac{27}{4})^{2i} .  (5.11)

References

1. M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A 87 (1999), 33–51.

2. M. Aigner, Lattice paths and determinants, Computational discrete mathematics, Lecture Notes in Comput. Sci., 2122, Springer, Berlin.

3. M. Aigner, Catalan and other numbers: a recurrent theme, Algebraic Combinatorics and Computer Science (H. Crapo, D. Senato, ed.), Springer–Verlag, Berlin, 2001, pp. 347–390.

4. A. T. Benjamin and N. T. Cameron, Counting on determinants, Amer. Math. Monthly 112 (2005), 481–492.

5. A. T. Benjamin, N. T. Cameron, J. J. Quinn and C. R. Yerger, Catalan determinants — a combinatorial approach, Applications of Fibonacci Numbers, vol. 11 (W. Webb, ed.), Utilitas Mathematica Publ. Co., Winnipeg, 2010 (to appear).

6. A. T. Benjamin, N. T. Cameron, J. J. Quinn and C. R. Yerger, in preparation.

7. R. Brak and J. W. Essam, Return polynomials for non-intersecting paths above a surface on the directed square lattice, J. Phys. A: Math. Gen. 34 (2001), 10763–10782.

8. R. Brak and J. W. Essam, Bicoloured Dyck paths and the contact polynomial for n non-intersecting paths in a half-plane lattice, Electron. J. Combin. 10 (2003), Article #R35, 18 pages.

9. D. M. Bressoud, Proofs and confirmations — The story of the alternating sign matrix conjecture, Cambridge University Press, Cambridge, 1999.

10. M. Chamberland and C. French, Generalized Catalan numbers and generalized Hankel transformations, J. Integer Seq. 10 (2007), Article 07.1.1, 7 pp.

11. S. H. Choi and D. Gouyou–Beauchamps, Enumération de tableaux de Young semi-standard, Theoret. Comput. Science 117 (1993), 137–151.

12. J. Cigler, Operatormethoden für q-Identitäten VII: q-Catalan-Determinanten, Sitz.ber. d. ÖAW Math.- naturwiss. Klasse 208 (1999), 123–142.

13. J. Cigler, Some relations between generalized Fibonacci and Catalan numbers, Sitz.ber. d. ÖAW Math.-naturwiss. Klasse 211 (2002), 143–154.

14. J. Cigler and C. Krattenthaler, Some determinants of path generating functions, Adv. Appl. Math. (to appear).

15. A. Cvetković, P. Rajković and M. Ivković, Catalan numbers, the Hankel transform, and Fibonacci numbers, J. Integer Seq. 5 (2002), Article 02.1.3, 8 pp.

16. M. Desainte–Catherine and X. Viennot, Enumeration of certain Young tableaux with bounded height, Combinatoire énumérative (G. Labelle, P. Leroux, eds.), Springer–Verlag, Berlin, Heidelberg, New York, 1986, pp. 58–67.

17. J. Désarménien, La démonstration des identités de Gordon et MacMahon et de deux identités nouvelles, Séminaire Lotharingien Combin. 15 (1987), Article B15a, 11 pp.

18. Ö. Eğecioğlu, T. Redmond and C. Ryavec, From a polynomial Riemann hypothesis to alternating sign matrices, Electron. J. Combin. 8 (2001), Article #R36, 51 pp.

19. Ö. Eğecioğlu, T. Redmond and C. Ryavec, Almost product evaluation of Hankel determinants, Electron. J. Combin. (2007), (to appear).

20. M. E. Fisher, Walks, walls, wetting, and melting, J. Statist. Phys. 34 (1984), 667–729.

21. I. M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300–321.

22. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint, 1989, available at

http://www.cs.brandeis.edu/~ira.

23. I. M. Gessel and G. Xin, The generating function of ternary trees and continued fractions, Electron. J. Combin. 13 (2006 Article #R53, 48 pp).

24. S. R. Ghorpade and C. Krattenthaler, The Hilbert series of Pfaffian rings, Algebra, Arithmetic and Geometry with Applications (C. Christensen, G. Sundaram, A. Sathaye and C. Bajaj, eds.), Springer-Verlag, New York, 2004, pp. 337–356.

25. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

26. H.-D. O. F. Gronau, W. Just, W. Schade, P. Scheffler and J. Wojciechowski, Path systems in acyclic directed graphs, Zastos. Mat. 19 (1988), 399–411.

27. P. Hilton and J. Pedersen, Catalan numbers, their generalization, and their uses, Math. Intelligencer 13 (1991), 64–75.

28. P. John and H. Sachs, Wegesysteme und Linearfaktoren in hexagonalen und quadratischen Systemen, Graphs in research and teaching (Kiel, 1985), Franzbecker, Bad Salzdetfurth, 1985, pp. 85–101.

29. C. Krattenthaler, Generating functions for plane partitions of a given shape, Manuscripta Math. 69 (1990), 173–202.

30. C. Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (“The Andrews Festschrift”) (1999), Article B42q, 67 pp.

31. C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 64–166.

32. C. Krattenthaler, Watermelon configurations with wall interaction: exact and asymptotic results, J. Physics: Conf. Series 42 (2006), 179–212.

33. J. W. Layman, The Hankel transform and some of its properties, J. Integer Seq. 4 (2001), Article 01.1.5, 11 pp.

34. B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90.

35. M. E. Mays and J. Wojciechowski, A determinant property of Catalan numbers, Discrete Math. 211 (2000), 125–133.

36. S. G. Mohanty, Lattice path counting and applications, Academic Press, New York, 1979.

37. A. L. Owczarek, J. W. Essam and R. Brak, Scaling analysis for the adsorption transition in a watermelon network of n directed non-intersecting walks, J. Statist. Phys. 102 (2001), 997–1017.

38. P. Peart, Hankel determinants via Stieltjes matrices, Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), Congr. Numer. 144 (2000), 153–159.

39. C. Radoux, Calcul effectif de certains déterminants de Hankel, Bull. Soc. Math. Belg. Sér. B 31 (1979), 49–55.

40. C. Radoux, Déterminants de Hankel et théorème de Sylvester, Séminaire Lotharingien Combin. 28 (1992), Article B28b, 9 pp.

41. C. Radoux, Nombres de Catalan généralisés, Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 289–292.

42. C. Radoux, Addition formulas for polynomials built on classical combinatorial sequences, J. Comput. Appl. Math. 115 (2000), 471–477.

43. R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.

44. U. Tamm, Some aspects of Hankel matrices in coding theory and combinatorics, Electron. J. Combin. 8 (2001), Art. #A1.

45. X. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, UQAM, Montréal, Québec, 1983.

46. X. Viennot, A combinatorial interpretation of the quotient-difference algorithm, Formal Power Series and Algebraic Combinatorics (Moscow, 2000), Springer–Verlag, Berlin, 2000, pp. 379–390.

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

WWW: http://www.mat.univie.ac.at/~kratt