Some determinants of path generating functions

J. Cigler and C. Krattenthaler^{†}

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

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

Dedicated to Dennis Stanton

Abstract. We evaluate four families of determinants of matrices, where the entries are sums or differences of generating functions for paths consisting of up-steps, down-steps and level steps. By specialisation, these determinant evaluations have numerous corollaries. In particular, they cover numerous determinant evaluations of combinatorial numbers — most notably of Catalan, ballot, and of Motzkin numbers — that appeared previously in the literature.

1. Introduction. Determinants (and Hankel determinants in particular) of path counting numbers (respectively, more generally, of path generating functions) appear frequently in the literature. The reason of this ubiquity is two-fold: first, via the theory of non-intersecting lattice paths (cf. [9, 10, 19]), such determinants represent the solution to counting problems of combinatorial, probabilistic, or algebraic origin (see e.g. [3, 11, 12, 15, 16, 19] and the references contained therein). Second, it turns out that such determinants can be often evaluated into attractive, compact closed formulae. This latter theme will be the underlying theme of the present paper.

(Hankel) Determinant evaluations such as

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)
det_{0≤i,j≤n−1}(C_{i+j+2}) = n + 1,  (1.3)

2010 Mathematics Subject Classification. Primary 05A19; Secondary 05A10 05A15 11C20 15A15.

Key words and phrases. Hankel determinants, Catalan numbers, ballot numbers, Motzkin numbers, Motzkin paths, 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”.

where C_{n} = \frac{1}{n+1} \binom{2n}{n} is the n-th Catalan number, and

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

det_{0≤i,j≤n−1}(M_{i+j+1}) = \{ \begin{matrix}(−1)^{n/3} & if n ≡ 0 (mod 3), \\ (−1)^{(n−1)/3} & if n ≡ 1 (mod 3), \\ 0 & if n ≡ 2 (mod 3), \end{matrix}  (1.5)

where M_{n} = ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k} \frac{1}{k+1} \binom{2k}{k} is the n-th Motzkin number, belong to the folklore of (orthogonal polynomials) literature (cf. e.g. [20, 1]). In our paper, we shall consider common weighted generalisations of these determinant evaluations.

It is well-known (cf. [18, Exercises 6.19 and 6.38]) that C_{n} counts the number of lattice paths from (0, 0) to (2n, 0) consisting of up-steps (1, 1) and down-steps (1, −1), which never run below the x-axis (see Figure 1.a for an example with n = 4), and that M_{n} counts the number of lattice paths from (0, 0) to (n, 0) consisting of up-steps (1, 1), level steps (1, 0), and down-steps (1, −1), which never run below the x-axis (see Figure 1.b for an example with n = 11). Our weighted generalisations will feature different weights for the three types of steps in such paths.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

a. A Catalan path b. A Motzkin path

Figure 1

Let us define P_{n}(l, k) as the generating function ∑_{P} w(P), where P runs over all paths from (0, l) to (n, k) consisting of steps from {(1, 0), (1, 1), (1, −1)} (for the sake of simplicity, such paths will in the sequel be referred to as three-step paths), and where w(P) is the product of all weights of the steps of P, where the weights of the steps are defined by w((1, 0)) = x + y, w((1, 1)) = 1, and w((1, −1)) = xy. Furthermore, let P_{n}^{+}(l, k) be the analogous generating function ∑_{P} w(P), where P runs over the subset of the set of the above three-step paths which never run below the x-axis. It should be observed that our choice of edge weights essentially amounts to giving independent weights to the three kinds of steps of the paths. The somewhat unusual parametrisation that we have chosen here will turn out to be useful in presenting our results in more compact forms than would be possible when using a more straightforward parametrisation.

Clearly, if we specialise x = −y = \sqrt{−1} (in which case x + y = 0 and xy = 1, that is, paths consisting entirely of up- and down-steps are weighted by 1, while all other paths acquire vanishing weight), then P_{2n}^{+}(0, 0) reduces to C_{n}. More generally, for this specialisation of x and y, the numbers P_{n}^{+}(0, k) are known as ballot numbers. On the other hand, if we specialise x = \frac{1}{2}(1 + \sqrt{−3}), y = \frac{1}{2}(1 − \sqrt{−3}) (in which case we have x + y = xy = 1, that is, all three kinds of steps are weighted by 1), then P_{n}^{+}(0, 0) reduces to M_{n}. A third kind of specialisation that we shall make use of, which is less intuitive, is x = y = 1. In this case, up- and down-steps are weighted by 1, while level steps are weighted by 2. It is not difficult to see (by either using (2.4) below, or by combinatorial reasoning: each up-step and each down-step is doubled, while level steps are replaced by either an up-step followed by a down-step or by a down-step followed by an up-step) that, for this specialisation of x and y, we have P_{n}^{+}(0, 0) = C_{n+1} and P_{n}(l, k) = \binom{2n}{n+k−l}.

We present our results generalising (1.1)–(1.5) in the two theorems below.

Theorem 1. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (P_{i+j}^{+}(0, k)) = \{ \begin{matrix}(−1)^{n_{1}\binom{k+1}{2}}(xy)^{(k+1)^{2}\binom{n_{1}}{2}} & n = n_{1}(k + 1), \\ 0 & n ≢ 0 (mod k + 1). \end{matrix}  (1.6)

Theorem 2. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (P_{i+j+1}^{+}(0, k))

= \{ \begin{matrix}(−1)^{n_{1}\binom{k+1}{2}}(xy)^{(k+1)^{2}\binom{n_{1}}{2}} \frac{y^{(k+1)(n_{1}+1)}−x^{(k+1)(n_{1}+1)}}{y^{k+1}−x^{k+1}} & n = n_{1}(k + 1), \\ (−1)^{n_{1}\binom{k+1}{2}+\binom{k}{2}}(xy)^{(k+1)^{2}\binom{n_{1}}{2}+n_{1}k(k+1)} \\ ×\frac{y^{(k+1)(n_{1}+1)}−x^{(k+1)(n_{1}+1)}}{y^{k+1}−x^{k+1}} & n = n_{1}(k + 1) + k, \\ 0 & n ≢ 0, k (mod k + 1). \end{matrix} (1.7)

Remark. If k = 0, the formulae in Theorems 1 and 2 have to be read according to the convention that only the first line on the right-hand sides of (1.6) and (1.7) applies; that is,

det_{0≤i,j≤n−1} (P_{i+j}^{+}(0, 0)) = (xy)^{\binom{n}{2}}

and

det_{0≤i,j≤n−1} (P_{i+j+1}^{+}(0, 0)) = (xy)^{\binom{n}{2}} \frac{y^{n+1} − x^{n+1}}{y − x} .

For x = −y = \sqrt{−1} and k = 0, by the factorisation of determinants of “checkerboard matrices” given in Lemma 5 in Section 3, Theorem 1 implies both (1.1) and (1.2). Moreover, if we set x = y = 1, then Theorems 1 and 2 reduce to (1.2) and (1.3), respectively. On the other hand, if we specialise x = \frac{1}{2}(1 + \sqrt{−3}), y = \frac{1}{2}(1 − \sqrt{−3}), then Theorems 1 and 2 reduce to (1.4) and (1.5), respectively. We list further interesting special cases of the above two theorems in Section 7.

We show furthermore that the analogous Hankel determinants, where the “restricted” path generating functions P_{i+j}^{+}(0, k), respectively P_{i+j+1}^{+}(0, k), are replaced by their “unrestricted” counterparts, have as well compact evaluations.

Theorem 3. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (P_{i+j}(0, k)) = \{ \begin{matrix}(−1)^{kn_{1}+\binom{k}{2}}(xy)^{k(n_{1}−1)(2kn_{1}−k+1)} & n = 2kn_{1} − k + 1, \\ (−1)^{kn_{1}}(xy)^{kn_{1}(2kn_{1}−k−1)} & n = 2kn_{1}, \\ 0 & n ≢ 0, k + 1 (mod 2k), \end{matrix}

(1.8)

while for k = 0 we have

det_{0≤i,j≤n−1} (P_{i+j}(0, 0)) = 2^{n−1}(xy)^{\binom{n}{2}}.  (1.9)

Remarks. (1) If k = 1, the first two cases on the right-hand side of (1.8) coincide, so that we have

det_{0≤i,j≤n−1} (P_{i+j}(0, 1)) = \{ \begin{matrix}(−1)^{n_{1}}(xy)^{2n_{1}(n_{1}−1)} & n = 2n_{1}, \\ 0 & n odd. \end{matrix}

(2) By Formula (2.2), the determinant evaluation in Theorem 3 also implies a formula for negative k. We omit its explicit statement for the sake of brevity.

Theorem 4. For all positive integers n and integers k ≥ 2, we have

det_{0≤i,j≤n−1} (P_{i+j+1}(0, k))

= \{ \begin{matrix}(−1)^{k(n_{1}−1)−1}(xy)^{kn_{1}(2kn_{1}−k−3)+k}P_{n−k+2,k}(x, y) \\ n = 2kn_{1} − 1, \\ (−1)^{kn_{1}+\binom{k}{2}}(xy)^{k(n_{1}−1)(2kn_{1}−k+1)}P_{n,k}(x, y) \\ n = 2kn_{1} − k + 1, \\ (−1)^{kn_{1}+\binom{k+1}{2}}(xy)^{k(n_{1}−1)(2kn_{1}−k−1)}P_{n−k,k}(x, y) \\ n = 2kn_{1} − k, \\ (−1)^{kn_{1}}(xy)^{kn_{1}(2kn_{1}−k−1)}P_{n,k}(x, y) & n = 2kn_{1}, \\ 0 n ≢ 0, k, k + 1, 2k − 1 (mod 2k), \end{matrix}

(1.10)

where

P_{m,k}(x, y) = \{ \begin{matrix}\frac{x^{m+k}+(−1)^{m/k}y^{m+k}}{x^{k}+y^{k}} & if k | m, \\ \frac{(x^{k⌊m/k⌋+k}+(−1)^{⌊m/k⌋}y^{k⌊m/k⌋+k})(x^{m−k⌊m/k⌋}+(−1)^{⌊m/k⌋}y^{m−k⌊m/k⌋})}{x^{k}+y^{k}} & if k ∤ m, \end{matrix}

while for k = 1 we have

det_{0≤i,j≤n−1} (P_{i+j+1}(0, 1)) = \{ \begin{matrix}(−1)^{n_{1}}(xy)^{2n_{1}(n_{1}−1)} \frac{x^{n+1}+(−1)^{n}y^{n+1}}{x+y} & n = 2n_{1}, \\ (−1)^{n_{1}+1}(xy)^{2(n_{1}−1)^{2}} \frac{x^{n}+(−1)^{n−1}y^{n}}{x+y} & n = 2n_{1} − 1, \end{matrix} (1.11)

and for k = 0 we have

det_{0≤i,j≤n−1} (P_{i+j+1}(0, 0)) = 2^{n−1}(xy)^{\binom{n}{2}}(x^{n} + y^{n}).  (1.12)

Remarks. (1) Again, by Formula (2.2), the determinant evaluations in Theorem 4 also imply formulae for negative k. We omit their explicit statement for the sake of brevity.

(2) Inspection of those values of n in (1.10) which lead to non-zero determinants shows that it suffices to use the following, restricted, definition for P_{m,k}(x, y):

P_{m,k}(x, y)

= \{ \begin{matrix}\frac{x^{m+k}+y^{m+k}}{x^{k}+y^{k}} & if k | m and m/k is even, \\ \frac{(x^{k⌊m/k⌋+k}−y^{k⌊m/k⌋+k})(x^{m−k⌊m/k⌋}−y^{m−k⌊m/k⌋})}{x^{k}+y^{k}} & if k ∤ m and ⌊m/k⌋ is odd. \end{matrix}

(3) For α > 1, computer calculations show that the evaluations of the “higher order” Hankel determinants

det_{0≤i,j≤n−1} (P_{i+j+α}^{+}(0, k)) and det_{0≤i,j≤n−1} (P_{i+j+α}(0, k))

become increasingly unwieldy. Presumably it would be still possible to work out, and subsequently prove, the corresponding evaluations for α = 2, say. However, we did not actually try this. In any case, we doubt that there is a reasonable formula for generic α.

(4) While, usually, Hankel determinants are intimately related to orthogonal polynomials (cf. e.g. [13, Sec. 2.7] and [14, Sec. 5.4]), it does not seem to be the case here (except for k = 0 and k = 1, where the determinants in Theorems 1–4 are related to Chebyshev polynomials), since the results in Theorems 1–4 follow modular patterns with a frequent appearance of zeroes, something which is not allowed in the theory of orthogonal polynomials.

(5) A similar remark applies to applicability of available computer packages: the evaluations of the determinants that we consider in this paper are certainly not amenable to the condensation method (cf. [13, Sec. 2.3]), and therefore the package DODGSON by Amdeberhan and Zeilberger [2] will not be useful here. Zeilberger’s package DET [21] (which is based on recurrence methods) can do (7.2), but it must necessarily fail if the results follow modular patterns, which is the case for our determinants if k is not 0 or 1. It is conceivable that Zeilberger’s algorithmic approach in [21] can be extended, respectively adapted, to cover also patterns modulo m, say, for a fixed m. However, such an extension could still not treat any of the corollaries in Section 7 for generic k, it could only give hints towards a general proof. An additional new idea is required to be able to attack the determinant identities of our paper in complete generality by algorithmic methods.

It should also be pointed out that the determinants in Theorems 1–4, 8–11 cause yet another problem when attacked by computer packages: these are determinants the entries of which are polynomials in two, respectively in three variables. This slows down computations considerably, up to the effect that it may be impossible to carry them out by current computer technology.

The purpose of the next two sections is to collect preliminary results on our three-step paths and on determinants of “checkerboard matrices,” respectively. We then show in Section 4, that, by the Lindström–Gessel–Viennot theorem, the determinants in Theorems 1 and 2 have natural combinatorial interpretations in terms of non-intersecting lattice paths. In particular, using non-intersecting lattice paths, we reduce the determinants in (1.6) and (1.7) to determinants of a similar, but different kind (see (4.2) and (4.3)). These latter determinants turn out to be special cases of a more general family of determinants which we evaluate in Theorems 8 and 9 in Section 5. In this sense, these two theorems are the first two main results of our article. Likewise, we show in Section 4 that the determinants in Theorems 3 and 4 are equal to determinants that are of a very similar form as those in (4.2) and (4.3) (see (4.4) and (4.5)). The second set of main results then consists of Theorems 10 and 11 in Section 6, in which we evaluate two further families of determinants, which generalise (4.4) and (4.5). Corollaries of our main results are collected in Section 7. We conclude our article by some comments and questions (see Section 8). The most intriguing perhaps is the speculative question on a potential relation between our determinants in Theorems 8–11 and Jacobi–Trudi-type formulae for symplectic and orthogonal characters.

2. Some facts about three-step paths. In order to prepare for the proofs of our theorems, we collect some standard facts about our three-step paths.

By definition of our path generating functions, we have

P_{n}(l, k) = P_{n}(0, k − l)  (2.1)

and

P_{n}(0, k) = (xy)^{−k}P_{n}(0, −k).  (2.2)

We shall use simple facts such as P_{n}(0, k) = 0 for n < k and P_{n}(0, n) = 1 without further reference frequently in the article.

The reflection principle (see e.g. [4, p. 22]) allows us to express the generating functions P_{n}^{+}(l, k) for restricted paths in terms of the generating functions P_{n}(l, k) for unrestricted paths, namely by

P_{n}^{+}(l, k) = P_{n}(l, k) − (xy)^{l+1}P_{n}(−l − 2, k).  (2.3)

By using elementary combinatorial reasoning, the path generating functions P_{n}(0, k) can be expressed in the form

P_{n}(0, k) = ⟨z^{k}⟩ (z + (x + y) + \frac{xy}{z} )^{n} ,
= ⟨z^{0}⟩ z^{n−k} (1 + \frac{x}{z})^{n} (1 + \frac{y}{z} )^{n} ,  (2.4)

where ⟨z^{m}⟩ f(z) denotes the coefficient of z^{m} in the formal Laurent series f(z). From (2.4), it is easy to derive the explicit formulae

P_{n}(0, k) = ∑_{ℓ≥0} \binom{n}{ℓ, ℓ + k}(x + y)^{n−2ℓ−k}(xy)^{ℓ}

= ∑_{ℓ≥0} \binom{n}{ℓ}\binom{n}{n − k − ℓ}x^{ℓ}y^{n−k−ℓ},

where

\binom{n}{k_{1}, k_{2}} = \frac{n!}{k_{1}! k_{2}! (n − k_{1} − k_{2})!}

is a trinomial coefficient. Via (2.1) and (2.3), they imply explicit formulae for P_{n}(l, k) and P_{n}^{+}(l, k).

For later use, we record the specialisations that were essentially already discussed in the Introduction: with ω denoting a primitive sixth root of unity, we have

P_{n}(l, k)|_{x=−y=\sqrt{−1}} = χ(n + l + k even)\binom{n}{\frac{1}{2}(n + k − l)}  (2.5)
P_{n}^{+}(l, k)|_{x=−y=\sqrt{−1}} = χ(n + l + k even) (\binom{n}{\frac{1}{2}(n + k − l)} − \binom{n}{\frac{1}{2}(n + k + l + 2)})(2.6)

P_{n}(l, k)|_{x=y^{−1}=ω} = ∑_{ℓ≥0} \binom{n}{ℓ, ℓ + k − l}  (2.7)

P_{n}^{+}(l, k)|_{x=y^{−1}=ω} = ∑_{ℓ≥0} (\binom{n}{ℓ, ℓ + k − l} − \binom{n}{ℓ, ℓ + k + l + 2})  (2.8)

P_{n}(l, k)|_{x=y=1} = \binom{2n}{n + k − l}  (2.9)
P_{n}^{+}(l, k)|_{x=y=1} = \binom{2n}{n + k − l} − \binom{2n}{n + k + l + 2},  (2.10)

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

3. Determinants of “checkerboard” matrices. By (2.5) and (2.6), if we specialise x = −y = \sqrt{−1} in the determinants in Theorems 1 or 2, then we obtain matrices in which every other entry vanishes; more precisely, either the entries for which the sum of the row index and the columnn index is even vanish, or the entries for which the sum of the row index and the columnn index is odd vanish. The next two lemmas record the well-known (and easy to prove) factorisations of the determinants of such “checkerboard” matrices.

Lemma 5. Let M = (M_{i,j})_{0≤i,j≤n−1} be a matrix for which M_{i,j} = 0 whenever i + j is odd. Then

det_{0≤i,j≤n−1} (M_{i,j}) = det_{0≤i,j≤⌊(n−1)/2⌋} (M_{2i,2j}) · det_{0≤i,j≤⌊(n−2)/2⌋} (M_{2i+1,2j+1}).  (3.1)

Lemma 6. Let M = (M_{i,j})_{0≤i,j≤n−1} be a matrix for which M_{i,j} = 0 whenever i + j is even. Then

det_{0≤i,j≤n−1} (M_{i,j})

= \{ \begin{matrix}det_{0≤i,j≤(n−2)/2} (M_{2i+1,2j}) · det_{0≤i,j≤(n−2)/2} (M_{2i,2j+1}) & if n is even, \\ 0 & if n is odd. \end{matrix} (3.2)

The point here is that, in particular, if we are in the case of Lemma 5, the knowledge of the determinants on the left-hand side of (3.1) suffices to recursively calculate the values of the determinants on the right-hand side of (3.1). The same cannot be done in the situation of Lemma 6 since every other determinant vanishes. The only exception occurs if M is a symmetric matrix. In that case, the two determinants on the right-hand side of (3.2) in the case where n is even are equal to each other. We may therefore solve for them. However, then the question of what the correct sign is remains, since we have to take a square root. Nevertheless, if there should be a “nice” formula for the determinant on the left-hand side of (3.2), then one expects that there are also “nice” formulae for the determinants on the right-hand side of (3.2).

4. Non-intersecting lattice paths. The purpose of this section is to explain how the determinants in Theorems 1 and 2 can be combinatorially interpreted in terms of nonintersecting lattice paths, and to use this interpretation to transform them into different determinants, generalisations thereof will subsequently be evaluated in the next section.

First, we recall the Lindström–Gessel–Viennot theorem on non-intersecting lattice paths, specialised to our context of three-step paths. A family (P_{0}, P_{1}, …, P_{n−1}) of threestep paths P_{i}, i = 0, 1, …, n − 1, is called non-intersecting, if no two paths share a lattice point. The reader should be well aware at this point that, in our context, this notion has to be taken with care since this definition does allow that two paths cross each other in non-lattice points. See Figure 2 for examples. In the figure, the left half shows a pair of non-intersecting paths, while the two paths shown in the right half (regardless how we read them) share one (!) vertex (marked by a circle in the figure), and hence they are not non-intersecting.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘]

a. Non-intersecting (!) paths b. Two paths that intersect

Figure 2

Let us now fix a sublattice L of the plane integer lattice ℤ^{2}. For our purposes, L will be either all of ℤ^{2} or the upper half-plane including the x-axis. Given lattice points A and E, we write P(A → E) for the set of three-step paths from A to E that stay in L. More generally, given n-tuples A = (A_{0}, A_{1}, …, A_{n−1}) and E = (E_{0}, E_{1}, …, E_{n−1}) of lattice points, we write P(A → E) for the set of families (P_{0}, P_{1}, …, P_{n−1}) of three-step paths that stay in L, where path P_{i} runs from A_{i} to E_{i}, i = 0, 1, …, n − 1, and we write P^{nonint}(A → E) for the subset of P(A → E) of non-intersecting path families. In order to not overload notation, we do not make the dependence on L explicit in the symbols P(A → E), etc.

We extend the path weight w( .) of the Introduction to path families by

w((P_{0}, P_{1}, …, P_{n−1})) := ∏_{i=0}^{n−1} w(P_{i}).

Finally, given a set M with weight function w, we write GF(M; w) for the generating function ∑_{x∈M} w(x).

We are now in the position to state the Lindström–Gessel–Viennot theorem. There, the symbol S_{n} denotes the group of permutations of {0, 1, …, n−1}, and, given a permutation σ ∈ S_{n}, we write E_{σ} for (E_{σ(1)}, E_{σ(2)}, …, E_{σ(n)}).

Theorem 7 ([17, Lemma 1], [10, Theorem 1]). Let L be a fixed sublattice of ℤ^{2}. For all positive integers n and n-tuples A = (A_{0}, A_{1}, …, A_{n−1}), E = (E_{0}, E_{1}, …, E_{n−1}) of lattice points, we have

det_{0≤i,j≤n−1} ( GF(P(A_{j} → E_{i}); w)) = ∑_{σ∈S_{n}}(sgn σ) · GF(P^{nonint}(A → E_{σ}); w).  (4.1)

If we specialise the above theorem to L being the upper half-plane, A_{i} = (−i, 0) and E_{i} = (i, k), i = 0, 1, …, n − 1, then we see that the determinant in Theorem 1 can be interpreted in terms of non-intersecting lattice paths. More precisely, with the above choice of L, of the A_{i}’s, of the E_{i}’s, and of the weight w( .) introduced in the Introduction, we have

det_{0≤i,j≤n−1} (P_{i+j}^{+}(0, k)) = ∑_{σ∈S_{n}}(sgn σ) · GF(P^{nonint}(A → E_{σ}); w).

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{0}; A_{1}; A_{2}; A_{3}; A_{4}; E_{0}; E_{1}; E_{2}; E_{3}; E_{4}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A′_{0}; A′_{1}; A′_{2}; A′_{3}; A′_{4}; E_{0}; E_{1}; E_{2}; E_{3}; E_{4}]

a. A family of non-intersecting paths b. Omitting the superfluous initial portions

Figure 3

Now, if we consider a family (P_{0}, P_{1}, …, P_{n−1}) of paths in P^{nonint}(A → E_{σ}) that occurs on the right-hand side (see Figure 3.a for an example with n = 5, k = 3, and σ = 34201), then we see that the first i steps of P_{i}, i = 0, 1, …, n − 1, must all be up-steps since the path family is non-intersecting. Therefore we may equally well omit these steps. Thereby, we obtain again a family of non-intersecting paths, say (P′_{0}, P′_{1}, …, P′_{n−1}), where P′_{i} runs from A′_{i} = (0, i) to E_{σ(i)}. (Figure 3.b shows the family of non-intersecting paths that is obtained in this way from the path family in Figure 3.a). Reading Theorem 7 in the other direction, this argument implies the equality

det_{0≤i,j≤n−1} (P_{i+j}^{+}(0, k)) = det_{0≤i,j≤n−1} (P_{j}^{+}(i, k)) .  (4.2)

An analogous argument establishes the equality

det_{0≤i,j≤n−1} (P_{i+j+1}^{+}(0, k)) = det_{0≤i,j≤n−1} (P_{j+1}^{+}(i, k)) .  (4.3)

The determinants on the right-hand sides of (4.2) and (4.3) will be evaluated in the next section in Theorems 8 and 9, respectively, thereby establishing Theorems 1 and 2.

As we announced in the Introduction, also the determinants in Theorems 3 and 4 can be shown to equal different determinants, which are very close to the determinants in (4.2) and (4.3). We start with the determinant in (1.8). By cutting paths after i steps, it is easy to see that the equation

P_{i+j}(0, k) = ∑_{ℓ=−i}^{i} P_{i}(0, ℓ)P_{j}(ℓ, k)

holds. We substitute this in the determinant in (1.8), to obtain

det_{0≤i,j≤n−1} ( ∑_{ℓ=−i}^{i} P_{i}(0, ℓ)P_{j}(ℓ, k))

= det_{0≤i,j≤n−1} (P_{i}(0, 0)P_{j}(0, k) + ∑_{ℓ=1}^{i} P_{i}(0, ℓ)P_{j}(ℓ, k) + ∑_{ℓ=−i}^{−1} P_{i}(0, ℓ)P_{j}(ℓ, k))

= det_{0≤i,j≤n−1} (P_{i}(0, 0)P_{j}(0, k) + ∑_{ℓ=1}^{i} P_{i}(0, ℓ) (P_{j}(ℓ, k) + (xy)^{ℓ}P_{j}(−ℓ, k))) ,

where we used (2.2) to arrive at the last line. Here, empty sums must be understood as 0, so that the entry in row 0 and column j is equal to P_{j}(0, k). We now use row 0 to eliminate the term P_{i}(0, 0)P_{j}(0, k) in rows i = 1, 2, …, n − 1. Thereby, the entry in row 1 and column j becomes

P_{1}(0, 1)(P_{j}(1, k) + xyP_{j}(−1, k)) = P_{j}(1, k) + xyP_{j}(−1, k).

Hence, row 1 can be used to eliminate the terms for ℓ = 1 in the sums over ℓ in rows 1, 2, …, n − 1. Etc. At the end, we obtain that

det_{0≤i,j≤n−1} (P_{i+j}(0, k)) = \frac{1}{2} det_{0≤i,j≤n−1} (P_{j}(i, k) + (xy)^{i}P_{j}(−i, k)) .  (4.4)

(The reader should note that the fraction \frac{1}{2} comes from the fact that, written in the above form, in the determinant on the right-hand side the entry in row 0 and column j is 2P_{j}(0, k) instead of P_{j}(0, k).)

An analogous argument establishes the equality

det_{0≤i,j≤n−1} (P_{i+j+1}(0, k)) = \frac{1}{2} det_{0≤i,j≤n−1} (P_{j+1}(i, k) + (xy)^{i}P_{j+1}(−i, k)) .  (4.5)

The determinants on the right-hand sides of (4.4) and (4.5) will be evaluated in Section 6 in Theorems 10 and 11, respectively, thereby establishing Theorems 3 and 4.

5. Main theorems, I. In Theorems 8 and 9 below, we evaluate two families of determinants in which the entries are (essentially) differences of path generating functions. By (2.3), (4.2), and (4.3), the special case t = 1 of these two theorems implies Theorems 1 and 2, respectively.

Theorem 8. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (P_{j}(i, k) − t(xy)^{i+1}P_{j}(−i − 2, k))

= \{ \begin{matrix}(−1)^{n_{1}\binom{k+1}{2}}t^{k⌊ \frac{n_{1}}{2} ⌋}(xy)^{(k+1)^{2}\binom{n_{1}}{2}} & n = n_{1}(k + 1), \\ 0 & n ≢ 0 (mod k + 1), \end{matrix} (5.1)

while for k = −1 we have

det_{0≤i,j≤n−1} (P_{j}(i, −1) − t(xy)^{i+1}P_{j}(−i − 2, −1)) = 0.  (5.2)

Remarks. (1) If k = 0, the formula in Theorem 8 has to be read according to the convention that only the first line on the right-hand side of (5.1) applies; that is,

det_{0≤i,j≤n−1} (P_{j}(i, 0) − t(xy)^{i+1}P_{j}(−i − 2, 0)) = (xy)^{\binom{n}{2}}.  (5.3)

(2) By Formula (2.2), the determinant evaluation in Theorem 8 also implies a formula for negative k < −1. More precisely, using as well (2.1), we have

P_{j}(i, −k) − t(xy)^{i+1}P_{j}(−i − 2, −k) = P_{j}(0, −i − k) − t(xy)^{i+1}P_{j}(0, i + 2 − k)
= (xy)^{i+k}P_{j}(0, i + k) − t(xy)^{k−1}P_{j}(0, k − i − 2)

= −t(xy)^{k−1} (P_{j}(i, k − 2) − t^{−1}(xy)^{i+1}P_{j}(−i − 2, k − 2)) . (5.4)

Aside from some trivial factors, the expression in the last line is again in the form as the expression for the matrix element of the determinant on the left-hand side of (5.1). We omit the explicit statement of the resulting formula.

Proof. If k = −1, then the matrix

(P_{j}(i, k) − t(xy)^{i+1}P_{j}(−i − 2, k))_{0≤i,j≤n−1} ,  (5.5)

of which we want to compute the determinant, is upper triangular with zeroes on the main diagonal. Hence, its determinant vanishes.

If k = 0, then the matrix (5.5) is upper triangular, and the entry on the main diagonal in the i-th row is

P_{i}(i, 0) = (xy)^{i},

i = 0, 1, …, n − 1. The assertion in this case, given explicitly in (5.3), follows immediately.

From now on let k ≥ 1. In the matrix (5.5), we replace row (h(2k + 2) + b) by

∑_{ℓ=0}^{h} t^{ℓ−h}(xy)^{(h−ℓ)(k+1)} · (row (ℓ(2k + 2) + b))

− ∑_{ℓ=1}^{h} t^{ℓ−h−1}(xy)^{(h−ℓ)(k+1)+b+1} · (row (ℓ(2k + 2) − b − 2)) (5.6)

if 0 ≤ b ≤ k − 1, and by

∑_{ℓ=0}^{h} t^{ℓ−h}(xy)^{(h−ℓ)(k+1)} · (row (ℓ(2k + 2) + b))

− ∑_{ℓ=1}^{h+1} t^{ℓ−h−1}(xy)^{(h−ℓ)(k+1)+b+1} · (row (ℓ(2k + 2) − b − 2)) (5.7)

if k + 1 ≤ b ≤ 2k. It is easy to see that this can be achieved by elementary row manipulations: one starts with the last row, and one works one’s way up. (The reader should keep in mind that the rows are labelled by 0, 1, 2, . . ..)

Let first 0 ≤ b ≤ k − 1. In the new matrix, the entry in the j-th column of row i = h(2k + 2) + b is equal to

∑_{ℓ=0}^{h} t^{ℓ−h}(xy)^{(h−ℓ)(k+1)}(P_{j}(ℓ(2k + 2) + b, k)

− t(xy)^{ℓ(2k+2)+b+1}P_{j}(−ℓ(2k + 2) − b − 2, k))

− ∑_{ℓ=1}^{h} t^{ℓ−h−1}(xy)^{(h−ℓ)(k+1)+b+1}(P_{j}(ℓ(2k + 2) − b − 2, k)

− t(xy)^{ℓ(2k+2)−b−1}P_{j}(−ℓ(2k + 2) + b, k))

= ∑_{ℓ=0}^{h} t^{ℓ−h}(xy)^{(h−ℓ)(k+1)}P_{j}(0, −ℓ(2k + 2) − b + k)

− ∑_{ℓ=0}^{h} t^{ℓ−h+1}(xy)^{(h+ℓ)(k+1)+b+1}P_{j}(0, ℓ(2k + 2) + b + k + 2)

− ∑_{ℓ=1}^{h} t^{ℓ−h−1}(xy)^{(h−ℓ)(k+1)+b+1}P_{j}(0, −ℓ(2k + 2) + b + k + 2)

+ ∑_{ℓ=1}^{h} t^{ℓ−h}(xy)^{(h+ℓ)(k+1)}P_{j}(0, ℓ(2k + 2) − b + k),

where we used (2.1) repeatedly. If we subsequently apply (2.2) to further simplify this expression, then we obtain

∑_{ℓ=0}^{h} t^{ℓ−h}(xy)^{(h+ℓ)(k+1)+b−k}P_{j}(0, ℓ(2k + 2) + b − k)

− ∑_{ℓ=1}^{h+1} t^{ℓ−h}(xy)^{(h+ℓ)(k+1)+b−k}P_{j}(0, ℓ(2k + 2) + b − k)

− ∑_{ℓ=1}^{h} t^{ℓ−h−1}(xy)^{(h+ℓ)(k+1)−k−1}P_{j}(0, ℓ(2k + 2) − b − k − 2)

+ ∑_{ℓ=2}^{h+1} t^{ℓ−h−1}(xy)^{(h+ℓ−1)(k+1)}P_{j}(0, ℓ(2k + 2) − b − k − 2)

= t^{−h}(xy)^{h(k+1)+b−k}P_{j}(0, b − k) − t(xy)^{(2h+1)(k+1)+b−k}P_{j}(0, (h + 1)(2k + 2) + b − k)

− t^{−h}(xy)^{h(k+1)}P_{j}(0, −b + k) + (xy)^{2h(k+1)}P_{j}(0, (h + 1)(2k + 2) − b − k − 2)

= −t(xy)^{(2h+1)(k+1)+b−k}P_{j}(0, (h + 1)(2k + 2) + b − k)

+ (xy)^{2h(k+1)}P_{j}(0, h(2k + 2) − b + k)  (5.8)

for the (i, j)-entry of the new matrix, with i = h(2k + 2) + b, 0 ≤ b ≤ k − 1. An analogous calculation yields for the case k + 1 ≤ b ≤ 2k that the entry in the j-th column of row i = h(2k + 2) + b in the new matrix equals

− t(xy)^{(2h+1)(k+1)+b−k}P_{j}(0, (h + 1)(2k + 2) + b − k)

+ t(xy)^{(2h+1)(k+1)}P_{j}(0, (h + 1)(2k + 2) − b + k).

The reader should recall that we did not change the (i, j)-entry if i ≡ k (mod k + 1), say i = H(k + 1) + k, so that these entries are still given by

P_{j}(i, k) − t(xy)^{i+1}P_{j}(−i − 2, k)

= (xy)^{H(k+1)}P_{j}(0, H(k + 1)) − t(xy)^{(H+1)(k+1)}P_{j}(0, (H + 2)(k + 1)),

which fits nicely with (5.8) if H = 2h.

In particular, this means that the (i, j)-entry, with i = h(2k + 2) + b, vanishes in the case where 0 ≤ b ≤ k whenever j < h(2k + 2) − b + k, and that it vanishes in the case where k + 1 ≤ b ≤ 2k + 1 whenever j < (h + 1)(2k + 2) − b + k. Hence, if n = h(2k + 2) + b with 1 ≤ b ≤ k, then row h(2k + 2) consists entirely of zeroes since n − 1 < h(2k + 2) + k. Similarly, if n = h(2k + 2) + b with k + 1 ≤ b ≤ 2k + 1, then row h(2k + 2) + k + 1 consists entirely of zeroes since n − 1 < (h + 1)(2k + 2) − 1. Consequently, the determinant equals zero in the case where n ≢ 0 (mod k + 1).

If n = n_{1}(k + 1), then one can transform the matrix which we have obtained by the above manipulations into an upper triangular matrix, using the permutation of the rows given by

i = h(2k + 2) + b ↦ \{ \begin{matrix}h(2k + 2) − b + k & 0 ≤ b ≤ k, \\ (h + 1)(2k + 2) − b + k & k + 1 ≤ b ≤ 2k + 1, \end{matrix}

0 ≤ i ≤ n − 1, or, in simpler terms,

i = H(k + 1) + b ↦ H(k + 1) − b + k,  0 ≤ b ≤ k,  (5.9)

0 ≤ i ≤ n−1. Reading the entries along the main diagonal of this upper triangular matrix, we find

1, 1, …, 1,
(xy)^{k+1}, t(xy)^{k+1} …, t(xy)^{k+1},
(xy)^{2(k+1)}, (xy)^{2(k+1)}, …, (xy)^{2(k+1)},
(xy)^{3(k+1)}, t(xy)^{3(k+1)} …, t(xy)^{3(k+1)},
(xy)^{4(k+1)}, (xy)^{4(k+1)} …, (xy)^{4(k+1)},
...................................................
(xy)^{(n_{1}−1)(k+1)}, t^{χ(n_{1} even)}(xy)^{(n_{1}−1)(k+1)}, …, t^{χ(n_{1} even)}(xy)^{(n_{1}−1)(k+1)},

where, when arranged as above, there are exactly k + 1 entries in each line. The notation χ( .) that we used in the last line has the same meaning as at the end of Section 2: χ(A) = 1 if A is true and χ(A)=0 otherwise. The product of these entries is t^{k⌊n_{1}/2⌋}(xy)^{(k+1)^{2}\binom{n_{1}}{2}}, which is in agreement with our claim.

In order to determine the correct sign in front of the expression on the right-hand side of (5.1), we must compute the sign of the permutation in (5.9). The number of inversions of this permutation is n_{1}\binom{k+1}{2}. Hence, the sign to be determined is (−1)^{n_{1}\binom{k+1}{2}}. □

Theorem 9. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (P_{j+1}(i, k) − t(xy)^{i+1}P_{j+1}(−i − 2, k))

= \{ \begin{matrix}(−1)^{n_{1}\binom{k+1}{2}}t^{k⌊ \frac{n_{1}}{2} ⌋}(xy)^{(k+1)^{2}\binom{n_{1}}{2}} \\ × ∑_{s=0}^{n_{1}} t^{min\{s,n_{1}−s\}}x^{s(k+1)}y^{(n_{1}−s)(k+1)} & n = n_{1}(k + 1), \\ (−1)^{n_{1}\binom{k+1}{2}+\binom{k}{2}}t^{k⌈ \frac{n_{1}}{2} ⌉}(xy)^{(k+1)^{2}\binom{n_{1}}{2}+n_{1}k(k+1)} \\ × ∑_{s=0}^{n_{1}} t^{min\{s,n_{1}−s\}}x^{s(k+1)}y^{(n_{1}−s)(k+1)} & n = n_{1}(k + 1) + k, \\ 0 & n ≢ 0, k (mod k + 1), \end{matrix}

(5.10)

while for k = −1 we have

det_{0≤i,j≤n−1} (P_{j+1}(i, −1) − t(xy)^{i+1}P_{j+1}(−i − 2, −1)) = (1 − t)^{n}(xy)^{\binom{n+1}{2}}.  (5.11)

Remarks. (1) If k = 0, the first formula in Theorem 9 has to be read according to the convention that only the first and second lines (which coincide) on the right-hand side of (5.10) apply; that is,

det_{0≤i,j≤n−1} (P_{j+1}(i, 0) − t(xy)^{i+1}P_{j+1}(−i − 2, 0)) = (xy)^{\binom{n}{2}} ∑_{s=0}^{n} t^{min\{s,n−s\}}x^{s}y^{n−s}. (5.12)

(2) Also here, by Formula (2.2), the determinant evaluation in Theorem 9 also implies a formula for negative k < −1. To see this, all one has to do is to replace j by j + 1 in the calculation (5.4). We omit the explicit statement of the resulting formula.

Proof. If k = −1, then the matrix

(P_{j+1}(i, k) − t(xy)^{i+1}P_{j+1}(−i − 2, k))_{0≤i,j≤n−1} ,  (5.13)

of which we want to compute the determinant, is upper triangular and the entry on the main diagonal in the i-th row is

P_{i+1}(i, −1) = (1 − t)(xy)^{i+1},

i = 0, 1, …, n − 1. The assertion (5.11) follows immediately.

For the remaining cases, we proceed in the same way as in the proof of Theorem 8. Let for the moment k ≥ 1. We apply the row operations described in (5.6) and (5.7). In this way, we obtain a new matrix, where the (i, j)-entry, with i = h(2k + 2) + b, of the new matrix is given by

− t(xy)^{(2h+1)(k+1)+b−k}P_{j+1}(0, (h + 1)(2k + 2) + b − k)

+ (xy)^{2h(k+1)}P_{j+1}(0, h(2k + 2) − b + k) (5.14)

if 0 ≤ b ≤ k, by

− t(xy)^{(2h+1)(k+1)+b−k}P_{j+1}(0, (h + 1)(2k + 2) + b − k)

+ t(xy)^{(2h+1)(k+1)}P_{j+1}(0, (h + 1)(2k + 2) − b + k) (5.15)

if k + 1 ≤ b ≤ 2k, and by

(xy)^{(2h+1)(k+1)}P_{j+1}(0, (2h + 1)(k + 1)) − t(xy)^{(2h+2)(k+1)}P_{j+1}(0, (2h + 3)(k + 1)) (5.16)

if b = 2k + 1. It should be noted that, if k = 0, the definitions (5.14)–(5.16) of the new matrix entries (the case (5.15) being empty) coincide with the original matrix entries for k = 0. This allows us to continue with (5.14)–(5.16), assuming k ≥ 0.

In particular, from our new matrix we can read off that the (i, j)-entry, with i = h(2k + 2) + b, vanishes in the case where 0 ≤ b ≤ k whenever j < h(2k + 2) − b + k − 1, and that it vanishes in the case where k+1 ≤ b ≤ 2k+1 whenever j < (h+1)(2k+2)−b+k−1. Hence, if n = h(2k + 2) + b with 1 ≤ b ≤ k − 1, then row h(2k + 2) consists entirely of zeroes since n − 1 < h(2k + 2) + k − 1. Similarly, if n = h(2k + 2) + b with k + 2 ≤ b ≤ 2k, then row h(2k + 2) + k + 1 consists entirely of zeroes since n − 1 < (h + 1)(2k + 2) − 2. Consequently, the determinant equals zero in the case where n ≢ 0, k (mod k + 1).

Let now n = n_{1}(k + 1). We rearrange the rows of the matrix we have obtained after the above manipulations according to the permutation (5.9). This time, we do not obtain an upper triangular matrix, but an “almost” upper triangular matrix, by which we mean a matrix (M_{i,j}) for which M_{i,j} = 0 if j < i − 1. We now factor t^{χ(h odd)}(xy)^{h(k+1)} from all the entries in rows h(k + 1) + 1, …, h(k + 1) + k, and we factor (xy)^{h(k+1)} from the entries in the rows h(k + 1), h = 0, 1, …, n_{1} − 1. This yields an overall factor of

t^{⌊ \frac{n_{1}}{2} ⌋}(xy)^{(k+1)^{2}\binom{n_{1}}{2}}  (5.17)

by which we have to multiply the determinant of the remaining matrix in the end. We must as well multiply by the sign

(−1)^{n_{1}\binom{k+1}{2}}  (5.18)

of the permutation (5.9).

The remaining matrix is the following matrix: its (i, j)-entry, with i = h(k + 1) + b and 0 ≤ b ≤ k, is given by (see (5.14)–(5.16))

P_{j+1}(0, h(k+1)+b)−t^{χ(h even or b≡0 (mod k+1))}(xy)^{k−b+1}P_{j+1}(0, (h+2)(k+1)−b). (5.19)

We should observe that, for i ≥ 1, the first non-zero entry in row i (which is to be found in column i − 1) equals 1.

In this matrix, we replace the 0-th row by

∑_{h=0}^{n_{1}−1} ∑_{b=0}^{k}(−1)^{h(k+1)+b} ∑_{s=0}^{h} c(h, b, s) x^{s(k+1)}y^{(h−s)(k+1)} · (row (h(k + 1) + b)),  (5.20)

where the coefficients c(h, b, s) are given by

c(h, b, s) = \{ \begin{matrix}t^{min\{s+χ(h odd),h−s\}}x^{b} + t^{min\{s,h−s+χ(h odd)\}}y^{b}, & if b ≠ 0, \\ t^{min\{s,h−s\}}, & if b = 0. \end{matrix}

Since the coefficient of the 0-th row in the linear combination (5.20) is 1, this does not change the value of the determinant.

The (0, j)-entry in the new matrix is then given by

∑_{h=0}^{n_{1}−1} ∑_{b=0}^{k}(−1)^{h(k+1)+b} ∑_{s=0}^{h} c(h, b, s) x^{s(k+1)}y^{(h−s)(k+1)}

· (P_{j+1}(0, h(k + 1) + b) − t^{χ(h even or b≡0 (mod k+1))}(xy)^{k−b+1}P_{j+1}(0, (h + 2)(k + 1) − b))

= ∑_{h=0}^{n_{1}−1} ∑_{s=0}^{h}(−1)^{h(k+1)}t^{min{s,h−s}}x^{s(k+1)}y^{(h−s)(k+1)}

· (P_{j+1}(0, h(k + 1)) − t(xy)^{k+1}P_{j+1}(0, (h + 2)(k + 1))) (5.21a)

+ ∑_{h=0}^{n_{1}−1} ∑_{b=1}^{k} ∑_{s=0}^{h}(−1)^{h(k+1)+b}x^{s(k+1)}y^{(h−s)(k+1)}

· (t^{min{s+χ(h odd),h−s}}x^{b} + t^{min{s,h−s+χ(h odd)}}y^{b})P_{j+1}(0, h(k + 1) + b)

(5.21b)

− ∑_{h=0}^{n_{1}−1} ∑_{b=1}^{k} ∑_{s=0}^{h}(−1)^{h(k+1)+b}x^{s(k+1)}y^{(h−s)(k+1)}

· (t^{min{s+1,h−s+χ(h even)}}x^{k+1}y^{k−b+1} + t^{min{s+χ(h even),h−s+1}}x^{k−b+1}y^{k+1})

· P_{j+1}(0, (h + 2)(k + 1) − b).  (5.21c)

For the double sum (5.21a), we have

∑_{h=0}^{n_{1}−1} ∑_{s=0}^{h}(−1)^{h(k+1)}t^{min{s,h−s}}x^{s(k+1)}y^{(h−s)(k+1)}

· (P_{j+1}(0, h(k + 1)) − t(xy)^{k+1}P_{j+1}(0, (h + 2)(k + 1)))

= ∑_{h=−1}^{n_{1}−2} ∑_{s=0}^{h+1}(−1)^{(h+1)(k+1)}t^{min{s,h−s+1}}x^{s(k+1)}y^{(h−s+1)(k+1)}P_{j+1}(0, (h + 1)(k + 1))

− ∑_{h=1}^{n_{1}} ∑_{s=1}^{h}(−1)^{(h−1)(k+1)}t^{min{s,h−s+1}}x^{s(k+1)}y^{(h−s+1)(k+1)}P_{j+1}(0, (h + 1)(k + 1)).

In this difference of double sums, almost everything cancels, the exceptions being the terms for h = −1 and for h = 0 in the first double sum, the terms for h ≥ 1 and s = 0 respectively s = h + 1 in the first double sum, and the terms for h = n_{1} − 1 and for h = n_{1} in the second double sum. Thus, we obtain the expression

P_{j+1}(0, 0) + (−1)^{k+1} (x^{k+1} + y^{k+1}) P_{j+1}(0, k + 1)

+ ∑_{h=1}^{n_{1}−2}(−1)^{(h+1)(k+1)} (x^{(h+1)(k+1)} + y^{(h+1)(k+1)}) P_{j+1}(0, (h + 1)(k + 1))

− ∑_{s=1}^{n_{1}−1}(−1)^{(n_{1}−2)(k+1)}t^{min{s,n_{1}−s}}x^{s(k+1)}y^{(n_{1}−s)(k+1)}P_{j+1}(0, n_{1}(k + 1))

− ∑_{s=1}^{n_{1}}(−1)^{(n_{1}−1)(k+1)}t^{min{s,n_{1}−s+1}}x^{s(k+1)}y^{(n_{1}−s+1)(k+1)}P_{j+1}(0, (n_{1} + 1)(k + 1))

= −P_{j+1}(0, 0) + ∑_{h=0}^{n_{1}−1}(−1)^{h(k+1)} (x^{h(k+1)} + y^{h(k+1)}) P_{j+1}(0, h(k + 1))

− (−1)^{n_{1}(k+1)} ∑_{s=1}^{n_{1}−1} t^{min{s,n_{1}−s}}x^{s(k+1)}y^{(n_{1}−s)(k+1)}δ_{j,n−1}  (5.22)

for the double sum in (5.21a), where we used the fact that j < n = n_{1}(k + 1) to see that P_{j+1}(0, (n_{1} + 1)(k + 1)) = 0 and P_{j+1}(0, n_{1}(k + 1)) = δ_{j,n_{1}(k+1)−1} = δ_{j,n−1}, where δ_{a,b} denotes the Kronecker delta.

On the other hand, by expanding and shifting indices in (5.21b), we obtain the expression

∑_{h=−1}^{n_{1}−2} ∑_{s=0}^{h+1} ∑_{b=1}^{k}(−1)^{(h+1)(k+1)+b}x^{s(k+1)+b}y^{(h−s+1)(k+1)}

· t^{min{s+χ(h even),h−s+1}}P_{j+1}(0, (h + 1)(k + 1) + b)

+ ∑_{h=−1}^{n_{1}−2} ∑_{s=−1}^{h} ∑_{b=1}^{k}(−1)^{(h+1)(k+1)+b}x^{(s+1)(k+1)}y^{(h−s)(k+1)+b}

· t^{min{s+1,h−s+χ(h even)}}P_{j+1}(0, (h + 1)(k + 1) + b) (5.23)

for the triple sum (5.21b), while, by replacing b by k + 1 − b in (5.21c), we obtain the expression

− ∑_{h=0}^{n_{1}−1} ∑_{s=0}^{h} ∑_{b=1}^{k}(−1)^{(h+1)(k+1)−b}x^{(s+1)(k+1)}y^{(h−s)(k+1)+b}

· t^{min{s+1,h−s+χ(h even)}}P_{j+1}(0, (h + 1)(k + 1) + b)

− ∑_{h=0}^{n_{1}−1} ∑_{s=0}^{h} ∑_{b=1}^{k}(−1)^{(h+1)(k+1)−b}x^{s(k+1)+b}y^{(h−s+1)(k+1)}

· t^{min{s+χ(h even),h−s+1}}P_{j+1}(0, (h + 1)(k + 1) + b) (5.24) for the triple sum (5.21c). If we add (5.23) and (5.24), then there is again a large amount of cancellation, with only the terms for h = −1, for s = −1, and for s = h + 1 in (5.23), and the terms for h = n_{1} − 1 in (5.24) surviving. However, the terms for h = n_{1} − 1 in (5.24) involve P_{j+1}(0, n_{1}(k + 1) + b) which vanishes for b ≥ 1 since j < n = n_{1}(k + 1). Therefore, the sum of (5.23) and (5.24) equals

∑_{b=1}^{k}(−1)^{b} (x^{b} + y^{b}) P_{j+1}(0, b)

+ ∑_{h=0}^{n_{1}−2} ∑_{b=1}^{k}(−1)^{(h+1)(k+1)+b} (x^{(h+1)(k+1)+b} + y^{(h+1)(k+1)+b}) P_{j+1}(0, (h + 1)(k + 1) + b)

= ∑_{h=0}^{n_{1}−1} ∑_{b=1}^{k}(−1)^{h(k+1)+b} (x^{h(k+1)+b} + y^{h(k+1)+b}) P_{j+1}(0, h(k + 1) + b).  (5.25)

In total, by taking the sum of (5.22) and (5.25), we see that the (0, j)-entry in our new matrix, given in (5.21), is equal to

− P_{j+1}(0, 0) + ∑_{m=0}^{n_{1}(k+1)−1}(−1)^{m} (x^{m} + y^{m}) P_{j+1}(0, m)

− (−1)^{n_{1}(k+1)} ∑_{s=1}^{n_{1}−1} t^{min{s,n_{1}−s}}x^{s(k+1)}y^{(n_{1}−s)(k+1)}δ_{j,n−1}. (5.26)

We now claim that

−P_{j+1}(0, 0) + ∑_{m=0}^{j+1}(−1)^{m} (x^{m} + y^{m}) P_{j+1}(0, m) = 0.  (5.27)

(The reader should keep in mind that n = n_{1}(k + 1).) In order to see this, we appeal to (2.4). Thereby, the left-hand side of (5.27) becomes

⟨z^{0}⟩ ( − z^{j+1} (1 + \frac{x}{z})^{j+1} (1 + \frac{y}{z} )^{j+1}

+ ∑_{m=0}^{j+1}(−1)^{m} (x^{m} + y^{m}) z^{j+1−m} (1 + \frac{x}{z})^{j+1} (1 + \frac{y}{z} )^{j+1} )

= ⟨z^{0}⟩ z^{j+1} (1 + \frac{x}{z})^{j+1} (1 + \frac{y}{z} )^{j+1} ( − 1 + \frac{1 − (−\frac{x}{z})^{j+2}}{1 + \frac{x}{z}} + \frac{1 − (−\frac{y}{z} )^{j+2}}{1 + \frac{y}{z}} )

= ⟨z^{0}⟩ z^{j+1} (1 + \frac{x}{z})^{j} (1 + \frac{y}{z} )^{j} (1 − \frac{xy}{z^{2}} )

− ⟨z^{0}⟩ z^{−1} (1 + \frac{x}{z})^{j} (1 + \frac{y}{z} )^{j} ((−x)^{j+2} + (−y)^{j+2})

= ⟨z^{−1}⟩ \frac{1}{(j + 1)} \frac{d}{dz} (z^{j+1} (1 + \frac{x}{z})^{j+1} (1 + \frac{y}{z} )^{j+1} ) = 0,

establishing the claim.

We are now in the position to conclude the proof of (5.10) in the case where n = n_{1}(k+1). By using (5.27) in (5.26), we see that the (0, j)-entry in the new matrix is given by

− (−1)^{n_{1}(k+1)} (x^{n_{1}(k+1)} + y^{n_{1}(k+1)}) δ_{j,n−1}

− (−1)^{n_{1}(k+1)} ∑_{s=1}^{n_{1}−1} t^{min{s,n_{1}−s}}x^{s(k+1)}y^{(n_{1}−s)(k+1)}δ_{j,n−1}

= −(−1)^{n_{1}(k+1)} ∑_{s=0}^{n_{1}} t^{min{s,n_{1}−s}}x^{s(k+1)}y^{(n_{1}−s)(k+1)}δ_{j,n−1}.

In particular, this means that all the entries in row 0, except for the last, vanish. It is therefore now easy to compute the determinant of the matrix we have obtained: as we observed in the paragraph above (5.17), this matrix is an “almost” upper triangular matrix, meaning that it is a matrix (M̂_{i,j}) for which M̂_{i,j} = 0 if j < i − 1. Furthermore (cf. the remark after (5.19)), we have M̂_{i,i−1} = 1 for i ≥ 1. Now, in addition, all entries in row 0 vanish, except for the last, which is equal to

−(−1)^{n_{1}(k+1)} ∑_{s=0}^{n_{1}} t^{min{s,n_{1}−s}}x^{s(k+1)}y^{(n_{1}−s)(k+1)}.

Hence, the determinant of the matrix we have obtained equals the above expression times the product of the entries M̂_{i,i−1}, i ≥ 1 (which is equal to 1), times the sign (−1)^{n−1} = (−1)^{n_{1}(k+1)−1}, that is, it is equal to

∑_{s=0}^{n_{1}} t^{min{s,n_{1}−s}}x^{s(k+1)}y^{(n_{1}−s)(k+1)}.  (5.28)

We can now sum up. The row operations at the very beginning and the factorisation of powers of t and xy from the rows resulted in a factor (see (5.17) and (5.18))

(−1)^{n_{1}\binom{k+1}{2}}t^{⌊ \frac{n_{1}}{2} ⌋}(xy)^{(k+1)^{2}\binom{n_{1}}{2}}.

The determinant of the matrix we had obtained after these operations turned out to be equal to (5.28). The product of these two expressions is indeed equal to the right-hand side of (5.10) in the case where n = n_{1}(k + 1).

Finally, we treat the case where n = n_{1}(k + 1) + k. In fact, this case can be reduced to the previous one. Namely, after one has performed the manipulations described at the beginning, after which the new matrix entries are given by (5.14)–(5.16), one is faced with a block matrix

( \begin{matrix}A & B \\ 0 & C \end{matrix} ) ,

where A is exactly the (n_{1}(k + 1)) × (n_{1}(k + 1)) matrix that is obtained by applying these manipulations in the previous case (that is, in the case where n = n_{1}(k + 1)), and where C is a k × k “reflected upper triangular” matrix. (By “reflected upper triangular”, we mean a matrix where all entries above the anti-diagonal of the matrix are equal to 0.) Moreover, all entries on the anti-diagonal of the matrix C are equal to t^{χ(n_{1} odd)}(xy)^{n_{1}(k+1)}. Hence, our determinant is equal to the result of the previous case multiplied by

(−1)^{\binom{k}{2}}t^{k·χ(n_{1} odd)}(xy)^{n_{1}k(k+1)}.

This is exactly in agreement with the right-hand side of (5.10) in the case where n = n_{1}(k + 1) + k. □

6. Main theorems, II. In this section we present two further families of determinant evaluations, where the entries of the matrices of which the determinant is taken are built out of path generating functions. By (4.4), and (4.5), the special case t = 1 of Theorems 10 and 11 below implies Theorems 3 and 4, respectively.

The reader should compare these theorems with Theorems 8 and 9. Evidently, there are strong similarities, with the only essential difference being located in the first argument of the path generating function in the second term of the matrix entries. Why we have chosen to present the matrix entries in Theorems 10 and 11 as sums rather than as differences (as opposed to the presentation of Theorems 8 and 9), and why we have chosen a slightly different exponent of xy, will become clear in Section 8. Clearly, one could transform one presentation into the other by replacement of t by −txy.

Theorem 10. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (P_{j}(i, k) + t(xy)^{i}P_{j}(−i, k))

= \{ \begin{matrix}(−1)^{kn_{1}+\binom{k}{2}}(1 + t)t^{k(n_{1}−1)}(xy)^{k(n_{1}−1)(2kn_{1}−k+1)} & n = 2kn_{1} − k + 1, \\ (−1)^{kn_{1}}(1 + t)t^{kn_{1}−1}(xy)^{kn_{1}(2kn_{1}−k−1)} & n = 2kn_{1}, \\ 0 & n ≢ 0, k + 1 (mod 2k), \end{matrix} (6.1)

while for k = 0 we have

det_{0≤i,j≤n−1} (P_{j}(i, 0) + t(xy)^{i}P_{j}(−i, 0)) = (1 + t)^{n}(xy)^{\binom{n}{2}}.  (6.2)

Remarks. (1) If k = 1, the first two cases on the right-hand side of (6.1) coincide, so that we have

det_{0≤i,j≤n−1} (P_{j}(i, 1) + t(xy)^{i}P_{j}(−i, 1)) = \{ \begin{matrix}(−1)^{n_{1}}(1 + t)t^{n_{1}−1}(xy)^{2n_{1}(n_{1}−1)} & n = 2n_{1}, \\ 0 & n odd. \end{matrix}

(2) By Formula (2.2), the determinant evaluation in Theorem 10 also implies a formula for negative k. More precisely, using also (2.1), we have

P_{j}(i, −k) + t(xy)^{i}P_{j}( − i, −k) = P_{j}(0, −i − k) + t(xy)^{i}P_{j}(0, i − k)
= (xy)^{i+k}P_{j}(0, i + k) + t(xy)^{k}P_{j}(0, k − i)
= t(xy)^{k} (P_{j}(i, k) + t^{−1}(xy)^{i}P_{j}(−i, k)) .  (6.3)

Aside from some trivial factors, the expression in the last line is again in the form as the expression for the matrix element of the determinant on the left-hand side of (6.1). We omit the explicit statement of the resulting formula.

Proof. If k = 0, then the matrix of which we want to compute the determinant is upper triangular, and the entry on the main diagonal in the i-th row is

P_{i}(i, 0) + t(xy)^{i}P_{i}(−i, 0) = (1 + t)(xy)^{i},

i = 0, 1, …, n − 1. The assertion in (6.2) follows immediately.

The rest of the proof is analogous to the one of Theorem 8. We content ourselves in outlining the key steps, leaving details to the reader.

In the matrix

(P_{j}(i, k) + t(xy)^{i}P_{j}(−i, k))_{0≤i,j≤n−1} ,

of which we want to compute the determinant, we replace row (2kh + b) by

∑_{ℓ=0}^{h}(−1)^{ℓ−h}t^{ℓ−h}(xy)^{(h−ℓ)k} · (row (2ℓk + b))

+ ∑_{ℓ=1}^{h}(−1)^{ℓ−h}t^{ℓ−h−1}(xy)^{(h−ℓ)k+b} · (row (2ℓk − b)) (6.4)

if 0 ≤ b ≤ k − 1, and by

∑_{ℓ=0}^{h}(−1)^{ℓ−h}t^{ℓ−h}(xy)^{(h−ℓ)k} · (row (2ℓk + b))

+ ∑_{ℓ=1}^{h+1}(−1)^{ℓ−h}t^{ℓ−h−1}(xy)^{(h−ℓ)k+b} · (row (2ℓk − b)) (6.5)

if k + 1 ≤ b ≤ 2k − 1. Again, it is easy to see that this can be achieved by elementary row manipulations. (We remind the reader that the rows are labelled by 0, 1, 2, . . ..) We must pay attention to the fact that, since in the case where b = 0 and h ≥ 1 the coefficient of row 2hk in (6.4) is 1 + t^{−1}, these manipulations change the value of the determinant. To be precise, they create a factor of

(1 + t^{−1})^{⌊(n−1)/2k⌋} ,  (6.6)

by which we must divide the result in the end.

The (i, j)-entry of the new matrix, with i = 2hk + b, is given by

(xy)^{2hk}P_{j}(0, (2h + 1)k − b) + t(xy)^{2hk+b}P_{j}(0, (2h + 1)k + b)

if 0 ≤ b ≤ k, and by

−t(xy)^{(2h+1)k}P_{j}(0, (2h + 3)k − b) + t(xy)^{2hk+b}P_{j}(0, (2h + 1)k + b)

if k + 1 ≤ b ≤ 2k − 1.

In particular, this means that the (i, j)-entry, with i = 2hk + b, vanishes in the case where 0 ≤ b ≤ k whenever j < (2h + 1)k − b, and that it vanishes in the case where k + 1 ≤ b ≤ 2k − 1 whenever j < (2h + 3)k − b. Hence, if n = 2hk + b with 1 ≤ b ≤ k, then row 2hk consists entirely of zeroes since n − 1 < 2hk + k. Similarly, if n = 2hk + b with k+2 ≤ b ≤ 2k−1, then row 2hk+k+1 consists entirely of zeroes since n−1 < 2hk+2k−1. Consequently, the determinant equals zero in the case where n ≢ 0, k + 1 (mod 2k).

If n = 2n_{1}k, then one can transform the matrix which we have obtained by the above manipulations into an upper triangular matrix, using the permutation of the rows given by

i = 2hk + b ↦ \{ \begin{matrix}(2h + 1)k − b & 0 ≤ b ≤ k, \\ (2h + 3)k − b & k + 1 ≤ b ≤ 2k − 1, \end{matrix}  (6.7)

0 ≤ i ≤ n−1. Reading the entries along the main diagonal of this upper triangular matrix, we find

1 + t; 1, …, 1; −t(xy)^{k}, …, −t(xy)^{k},

(1 + t)(xy)^{2k}; (xy)^{2k} …, (xy)^{2k}; −t(xy)^{3k}, …, −t(xy)^{3k},

(1 + t)(xy)^{4k}; (xy)^{4k}, …, (xy)^{4k}; −t(xy)^{5k}, …, −t(xy)^{5k},

............................................................................................

(1 + t)(xy)^{(2n_{1}−2)k}; (xy)^{(2n_{1}−2)k}, …, (xy)^{(2n_{1}−2)k}; −t(xy)^{(2n_{1}−1)k}, …, −t(xy)^{(2n_{1}−1)k}, (6.8)

where, when arranged as above, there are exactly 2k entries in each line, the first always containing a factor 1 + t, followed by k equal entries, which are in their turn followed by k − 1 equal entries. The product of these entries is (1 + t)^{n_{1}}t^{(k−1)n_{1}}(xy)^{kn_{1}(2kn_{1}−k−1)}. In order to arrive at the final result, this expression has to be divided by (6.6), by the sign of the permutation (6.7), and by the signs arising in (6.8). If everything is put together, we obtain the right-hand side in (6.1) for n = 2kn_{1}.

The case of n = 2kn_{1} − k + 1 can be treated in the same manner. We leave the details to the reader. □

Theorem 11. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (P_{j+1}(i, k) + t(xy)^{i}P_{j+1}(−i, k))

= \{ \begin{matrix}(−1)^{k(n_{1}−1)−1}(1 + t)t^{kn_{1}−2}(xy)^{kn_{1}(2kn_{1}−k−3)+k}P_{n−k+2,k}(x, y, t) \\ n = 2kn_{1} − 1, \\ (−1)^{kn_{1}+\binom{k}{2}}(1 + t)t^{k(n_{1}−1)}(xy)^{k(n_{1}−1)(2kn_{1}−k+1)}P_{n,k}(x, y, t) \\ n = 2kn_{1} − k + 1, \\ (−1)^{kn_{1}+\binom{k+1}{2}}(1 + t)t^{k(n_{1}−1)}(xy)^{k(n_{1}−1)(2kn_{1}−k−1)}P_{n−k,k}(x, y, t) \\ n = 2kn_{1} − k, \\ (−1)^{kn_{1}}(1 + t)t^{kn_{1}−1}(xy)^{kn_{1}(2kn_{1}−k−1)}P_{n,k}(x, y, t) & n = 2kn_{1}, \\ 0 n ≢ 0, k, k + 1, 2k − 1 (mod 2k), \end{matrix}

(6.9)

where

P_{m,k}(x, y, t)

= \{ \begin{matrix}∑_{s=0}^{m/k}(−1)^{s}t^{min\{s, \frac{m}{k} −s\}}x^{sk}y^{m−sk} & if m ≡ 0 (mod k), \\ ∑_{s=0}^{⌊m/k⌋}(−1)^{s}t^{min\{s,⌈m/k⌉−s\}} (x^{sk}y^{m−sk} + x^{m−sk}y^{sk}) & if m ≢ 0 (mod k), \end{matrix}

while for k = 1 we have

det_{0≤i,j≤n−1} (P_{j+1}(i, 1) + t(xy)^{i}P_{j+1}(−i, 1))

= \{ \begin{matrix}(−1)^{n_{1}+1}(1 + t)t^{n_{1}−1}(xy)^{2(n_{1}−1)^{2}}P_{n−1,1}(x, y, t) & n = 2n_{1} − 1, \\ (−1)^{n_{1}}(1 + t)t^{n_{1}−1}(xy)^{2n_{1}(n_{1}−1)}P_{n,1}(x, y, t) & n = 2n_{1}, \end{matrix}

(6.10)

and for k = 0 we have

det_{0≤i,j≤n−1} (P_{j+1}(i, 0) + t(xy)^{i}P_{j+1}(−i, 0)) = (1 + t)^{n}(xy)^{\binom{n}{2}}(x^{n} + y^{n}).  (6.11)

Remark. Again, by Formula (2.2), the determinant evaluation in Theorem 11 also implies formulae for negative k. To see this, all one has to do is to replace j by j + 1 in the calculation (6.3). We omit the explicit statement of the resulting formula.

Proof. As was the case also earlier, we have to treat the case k = 0 separately. Using (2.1) and (2.2), we see that, in this case, we have

P_{j+1}(i, 0) + t(xy)^{i}P_{j+1}(−i, 0) = (1 + t)(xy)^{i}P_{j+1}(0, i).

Hence, the determinant that we want to compute equals

(1 + t)^{n}(xy)^{\binom{n}{2}} det_{0≤i,j≤n−1} (P_{j+1}(0, i)).  (6.12)

We note that, for i = 1, 2, …, n − 1, the first i − 1 entries in row i of the matrix (P_{j+1}(0, i))_{0≤i,j≤n−1} vanish, while the entry in column i − 1 equals P_{i}(0, i) = 1. We now replace row 0 by

−(row 0) + ∑_{i=0}^{n−1}(−1)^{i} (x^{i} + y^{i}) · (row i).

Since the coefficient of row 0 in the above linear combination of rows equals 1, this operation does not change the value of the determinant. Using (5.27), we see that, in the new 0-th row, all entries vanish except for the last one in column n−1, which equals −(−1)^{n}(x^{n}+y^{n}). It is now easy to compute the determinant now obtained: it is equal to

−(−1)^{n−1}(−1)^{n}(x^{n} + y^{n}) · 1^{n−1} = x^{n} + y^{n}.

Substituting this for the determinant in (6.12) leads to the right-hand side of (6.11), as required.

From now on let k ≥ 1. Also here, we have done a similar proof already when establishing Theorem 9. Therefore, again, we shall be brief here.

We start by applying the row operations described in (6.4) and (6.5). We obtain a new matrix, where the (i, j)-entry, with i = 2hk + b, of the new matrix is given by

(xy)^{2hk}P_{j+1}(0, (2h + 1)k − b) + t(xy)^{2hk+b}P_{j+1}(0, (2h + 1)k + b)

if 0 ≤ b ≤ k, and by

−t(xy)^{(2h+1)k}P_{j+1}(0, (2h + 3)k − b) + t(xy)^{2hk+b}P_{j+1}(0, (2h + 1)k + b)

if k + 1 ≤ b ≤ 2k − 1. As earlier, at this point we can already read off that the determinant vanishes if n ≢ 0, k, k + 1, 2k − 1 (mod 2k).

We concentrate now on the case where n = 2kn_{1}. We reorder the rows according to the permutation (6.7). Subsequently, we divide each entry in row i, i ≥ 1, by the first non-zero entry in its row. Clearly, since this changes the determinant, the corresponding factor has to be taken into account in the end.

The resulting matrix is again an “almost” upper triangular matrix, that is, a matrix (M_{i,j}) for which M_{i,j} = 0 if j < i − 1. Furthermore, the first non-zero entry in row i, the entry M_{i,i−1}, equals 1 for all i ≥ 1.

In this matrix, we replace the 0-th row by

∑_{h=0}^{2n_{1}−1} ∑_{b=0}^{k−1}(−1)^{hk+b} ∑_{s=0}^{h} d(h, b, s) x^{sk}y^{(h−s)k} · (row (hk + b)),  (6.13)

where the coefficients d(h, b, s) are given by

d(h, b, s) = \{ \begin{matrix}(−1)^{h−s}t^{min\{s+χ(h odd),h−s\}}x^{b} + (−1)^{s}t^{min\{s,h−s+χ(h odd)\}}y^{b}, \\ if b ≠ 0, \\ (−1)^{s}t^{min\{s,h−s\}}, & if b = 0 and h is even, \\ χ(s = 0 or s = h), & if b = 0 and h is odd. \end{matrix}

Again, since the coefficient of the 0-th row in the linear combination (6.13) is 1, this does not change the value of the determinant.

We claim that, in the new matrix, all entries in row 0 are zero, except for the last one. To compute the last one, one can proceed as in the analogous situation in the proof of Theorem 9. Since there are no new aspects which arise here, we omit the details, leaving them to the reader.

The remaining three cases can be treated similarly. □

7. Specialisations. In this section we list specialisations of our results obtained in the previous sections. The special values of x and y that we choose are those that we discussed at the end of Section 2. We state all of our results for non-negative values of k only. However, we wish to point out that, for most of them, our results in the previous sections also imply corresponding results for negative values of k, cf. the remarks after Theorems 3–4, 8–11. We omit their explicit statement however for the sake of brevity.

We begin with Theorem 1. If we set x = −y = \sqrt{−1} there, then, using (2.6) and Lemma 5, we obtain the following two results.

Corollary 12. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (\frac{2k + 1}{i + j + k + 1}\binom{2i + 2j}{i + j + k}) = \{ \begin{matrix}(−1)^{kn_{1}+\binom{k}{2}} & n = n_{1}(2k + 1) − k, \\ (−1)^{kn_{1}} & n = n_{1}(2k + 1), \\ 0 & n ≢ 0, k + 1 (mod 2k + 1). \end{matrix}

Corollary 13. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (\frac{2k + 1}{i + j + k + 2}\binom{2i + 2j + 2}{i + j + k + 1}) = \{ \begin{matrix}(−1)^{kn_{1}+\binom{k+1}{2}} & n = n_{1}(2k + 1) − k − 1, \\ (−1)^{kn_{1}} & n = n_{1}(2k + 1), \\ 0 & n ≢ 0, k (mod 2k + 1). \end{matrix}

On the other hand, under the same specialisation, Lemma 6 suggests that also the determinant

det_{0≤i,j≤n−1} (\frac{2k}{i + j + k + 1}\binom{2i + 2j + 1}{i + j + k})

is always 0, 1, or −1. However, since on the right-hand side of (3.2) we encounter the square of the above determinant, we do not know whether we get +1 or −1 for the cases where the determinant is non-zero. Fortunately, there is a different specialisation which disposes of this problem, see Corollary 15.

Next we specialise x = \frac{1}{2}(1 + \sqrt{−3}) and y = \frac{1}{2}(1 − \sqrt{−3}) in Theorem 1. By (2.8), we obtain the following result.

Corollary 14. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (∑_{ℓ≥0} (\binom{i + j}{ℓ, ℓ + k} − \binom{i + j}{ℓ, ℓ + k + 2})) = \{ \begin{matrix}(−1)^{n_{1}\binom{k+1}{2}} & n = n_{1}(k + 1), \\ 0 & n ≢ 0 (mod k + 1). \end{matrix}

Finally, the specialisation x = y = 1 in Theorem 1 yields the following determinant identity upon appealing to (2.10) and replacing k by k − 1.

Corollary 15. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (\frac{2k}{i + j + k + 1}\binom{2i + 2j + 1}{i + j + k}) = \{ \begin{matrix}(−1)^{n_{1}\binom{k}{2}} & n = n_{1}k, \\ 0 & n ≢ 0 (mod k). \end{matrix}

Now we turn our attention to Theorem 2. If we set x = −y = \sqrt{−1} there, then, using (2.6) and Lemma 5, in addition to obtaining Corollary 13 again, we obtain the following result.

Corollary 16. For all positive integers n and k ≥ 2, we have

det_{0≤i,j≤n−1} (\frac{2k + 1}{i + j + k + 3}\binom{2i + 2j + 4}{i + j + k + 2})

= \{ \begin{matrix}(−1)^{kn_{1}+\binom{k}{2}+1} & n = n_{1}(2k + 1) − k − 2, \\ (−1)^{kn_{1}+\binom{k+1}{2}}(n + k + 1) & n = n_{1}(2k + 1) − k − 1, \\ (−1)^{k(n_{1}+1)}(n + 1) & n = n_{1}(2k + 1) − 1, \\ (−1)^{kn_{1}} & n = n_{1}(2k + 1), \\ 0 & n ≢ 0, k − 1, k, 2k (mod 2k + 1), \end{matrix} (7.1)

while for k = 0 we have

det_{0≤i,j≤n−1} (\frac{1}{i + j + 3}\binom{2i + 2j + 4}{i + j + 2}) = n + 1.

Remark. The formula in (7.1) is also valid for k = 1. Explicitly, we have

det_{0≤i,j≤n−1} (\frac{3}{i + j + 4}\binom{2i + 2j + 4}{i + j + 3}) = \{ \begin{matrix}(−1)^{n_{1}+1}3n_{1} & n = 3n_{1} − 2, \\ (−1)^{n_{1}+1}3n_{1} & n = 3n_{1} − 1, \\ (−1)^{n_{1}} & n = 3n_{1}. \end{matrix}

Also here, Lemma 6 suggests a further determinant evaluation, which turns out to be obtainable by another specialisation, see Corollary 18.

Next we specialise x = \frac{1}{2}(1 + \sqrt{−3}) and y = \frac{1}{2}(1 − \sqrt{−3}) in Theorem 2. By (2.8), we obtain the following result.

Corollary 17. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (∑_{ℓ≥0} (\binom{i + j + 1}{ℓ, ℓ + k} − \binom{i + j + 1}{ℓ, ℓ + k + 2}))

= \{ \begin{matrix}−(−1)^{n_{1}\binom{k+2}{2}} & n = n_{1}(3k + 3) − 2k − 3 and k ≢ 2 (mod 3), \\ −(−1)^{n_{1}\binom{k+2}{2}} & n = n_{1}(3k + 3) − 2k − 2 and k ≢ 2 (mod 3), \\ (−1)^{(n_{1}−1)\binom{k+2}{2}} & n = n_{1}(3k + 3) − k − 2 and k ≢ 2 (mod 3), \\ (−1)^{n_{1}\binom{k+2}{2}} & n = n_{1}(3k + 3) and k ≢ 2 (mod 3), \\ (−1)^{n_{1}\binom{k+1}{2}+ \frac{1}{3} n_{1}(k+1)}(n_{1} + 1) & n = n_{1}(k + 1) and k ≡ 2 (mod 3), \\ (−1)^{n_{1}\binom{k+1}{2}+\binom{k}{2}+ \frac{1}{3} n_{1}(k+1)}(n_{1} + 1) & n = n_{1}(k + 1) + k and k ≡ 2 (mod 3), \\ 0 & otherwise, \end{matrix}

while for k = 0 we have

det_{0≤i,j≤n−1} (∑_{ℓ≥0} (\binom{i + j + 1}{ℓ, ℓ + k} − \binom{i + j + 1}{ℓ, ℓ + k + 2})) = \{ \begin{matrix}1 & n ≡ 0, 1 (mod 6), \\ −1 & n ≡ 3, 4 (mod 6), \\ 0 & otherwise. \end{matrix}

Finally, setting x = y = 1 in Theorem 2 yields the following determinant identity upon appealing to (2.10) and replacing k by k − 1.

Corollary 18. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (\frac{2k}{i + j + k + 2}\binom{2i + 2j + 3}{i + j + k + 1})

= \{ \begin{matrix}(−1)^{n_{1}\binom{k}{2}}(n_{1} + 1) & n = n_{1}k, \\ (−1)^{n_{1}\binom{k}{2}+\binom{k−1}{2}}(n_{1} + 1) & n = n_{1}k + k − 1, \\ 0 & n ≢ 0, k − 1 (mod k). \end{matrix}

Next we consider the corresponding specialisations of Theorem 3. If we set x = −y = \sqrt{−1} there, then, using (2.5) and Lemma 5, we obtain the following two results.

Corollary 19. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (\binom{2i + 2j}{i + j + k}) = \{ \begin{matrix}(−1)^{n_{1}k} & n = 2n_{1}k, \\ (−1)^{n_{1}k+\binom{k}{2}} & n = 2n_{1}k − k + 1, \\ 0 & n ≢ 0, k + 1 (mod 2k), \end{matrix}

while for k = 0 we have

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

det_{0≤i,j≤n−1} (\binom{2i + 2j + 2}{i + j + k + 1}) = \{ \begin{matrix}(−1)^{\binom{n_{1}}{2}k+n_{1}\binom{k}{2}} & n = n_{1}k, \\ 0 & n ≢ 0 (mod k), \end{matrix}

while for k = 0 we have

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

Still considering the specialisation x = −y = \sqrt{−1}, Lemma 6 hints at a further determinant evaluation, which is given in the theorem below.

Theorem 21. For all positive integers n and k, we have

det_{0≤i,j≤n−1} (\binom{2i + 2j + 1}{i + j + k}) = \{ \begin{matrix}1 & n = (2k − 1)n_{1}, \\ (−1)^{n_{1}\binom{k}{2}} & n = (2k − 1)n_{1} − k + 1, \\ 0 & n ≢ 0, k (mod 2k − 1), \end{matrix}  (7.3)

while for k = 0 we have

det_{0≤i,j≤n−1} (\binom{2i + 2j + 1}{i + j}) = 1.

Remark. If k = 1, the first two cases on the right-hand side of (7.3) coincide, so that we have

det_{0≤i,j≤n−1} (\binom{2i + 2j + 1}{i + j + 1}) = 1.

Sketch of proof of Theorem 21. Lemma 6 is not sufficient to prove the assertion because it only yields a formula for the square of the determinant in (7.3). So, we have to find a direct proof.

By using the path decomposition argument in the paragraph below (4.3), or by Chu– Vandermonde convolution, we have

\binom{2i + 2j + 1}{i + j + k} = ∑_{ℓ=−i}^{i} \binom{2i}{i + ℓ}\binom{2j + 1}{j + k − ℓ}.

Then, in the same style as in the paragraph above (4.4), one can do row manipulations to see that

det_{0≤i,j≤n−1} (\binom{2i + 2j + 1}{i + j + k}) = \frac{1}{2} det_{0≤i,j≤n−1} (\binom{2j + 1}{j + k − i} + \binom{2j + 1}{j + k + i}) .

In order to evaluate the latter determinant, we can proceed as in the proof of Theorem 10. □

If we specialise x = \frac{1}{2}(1 + \sqrt{−3}) and y = \frac{1}{2}(1 − \sqrt{−3}) in Theorem 3, then, by (2.7), we obtain the following result.

det_{0≤i,j≤n−1} (∑_{ℓ≥0} \binom{i + j}{ℓ, ℓ + k}) = \{ \begin{matrix}(−1)^{kn_{1}+\binom{k}{2}} & n = 2kn_{1} − k + 1, \\ (−1)^{kn_{1}} & n = 2kn_{1}, \\ 0 & n ≢ 0, k + 1 (mod 2k), \end{matrix}

while for k = 0 we have

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

The specialisation x = y = 1 in Theorem 3 yields the result in Corollary 19 a second time.

At last, we consider the corresponding specialisations of Theorem 4. If we set x = −y = \sqrt{−1} there, then, using (2.5) and Lemma 5, we obtain Corollary 20 again, but also the additional determinant evaluation below.

Corollary 23. For all positive integers n and k ≥ 1, we have

det_{0≤i,j≤n−1} (\binom{2i + 2j + 4}{i + j + k + 2})

= \{ \begin{matrix}(−1)^{n_{1}k} & n = 2n_{1}k, \\ (−1)^{n_{1}k+\binom{k+2}{2}} & n = 2n_{1}k − k − 1, \\ 2(−1)^{n_{1}k+\binom{k+1}{2}}(n + k) & n = 2n_{1}k − k, \\ 2(−1)^{n_{1}k+k}(n + 1) & n = 2n_{1}k − 1, \\ 0 & n ≢ 0, k − 1, k, 2k − 1 (mod 2k), \end{matrix} (7.4)

while for k = 0 we have

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

Remark. The formula in (7.4) is also valid for k = 1. Explicitly, we have

det_{0≤i,j≤n−1} (\binom{2i + 2j + 4}{i + j + 3}) = \{ \begin{matrix}(−1)^{n_{1}} & n = 2n_{1}, \\ (−1)^{n_{1}+1}4n_{1} & n = 2n_{1} − 1. \end{matrix}

Also here, Lemma 6 hints at a further determinant evaluation. We formulate it in the conjecture below.

Conjecture 24. For all positive integers n and k ≥ 2, we have

det_{0≤i,j≤n−1} (\binom{2i + 2j + 3}{i + j + k + 1}) = \{ \begin{matrix}2n_{1} + 1 & n = (2k − 1)n_{1}, \\ (−1)^{k+1}(4n_{1}) & n = (2k − 1)n_{1} − 1, \\ (−1)^{\binom{k}{2}}(4n_{1}) & n = (2k − 1)n_{1} − k + 1, \\ (−1)^{\binom{k−1}{2}}(2n_{1} − 1) & n = (2k − 1)n_{1} − k, \\ 0 & otherwise, \end{matrix} (7.5)

while for k = 0, 1 we have

det_{0≤i,j≤n−1} (\binom{2i + 2j + 3}{i + j + 1}) = 2n + 1.

Remark. We believe that this conjecture can be proved in a similar way as Theorem 21 above; that is, one would first transform the determinant via

det_{0≤i,j≤n−1} (\binom{2i + 2j + 3}{i + j + k + 1}) = \frac{1}{2} det_{0≤i,j≤n−1} (\binom{2j + 3}{j + k − i + 1} + \binom{2j + 3}{j + k + i + 1}) ,

and then proceed in the spirit of the proof of Theorem 11. However, we did not try to work this out. We should point out that, by Lemma 6, the only unproven part in (7.5) concerns the signs.

If we specialise x = \frac{1}{2}(1 + \sqrt{−3}) and y = \frac{1}{2}(1 − \sqrt{−3}) in Theorem 4, then, by (2.7), we obtain the following result.

Corollary 25. For all positive integers n and k ≥ 2, we have

det_{0≤i,j≤n−1} (∑_{ℓ≥0} \binom{i + j + 1}{ℓ, ℓ + k}) = \{ \begin{matrix}(−1)^{kn_{1}/2} & n = kn_{1} and k ≡ 0 (mod 6), \\ (−1)^{\binom{n_{1}+1}{2}} & n = kn_{1} and k ≡ 3 (mod 12), \\ (−1)^{\binom{n_{1}}{2}} & n = kn_{1} and k ≡ 9 (mod 12), \\ (−1)^{kn_{1}+\binom{k+1}{2}} & n = 6kn_{1} − 5k and 3 ∤ k, \\ 3(−1)^{k(n_{1}+1)+⌊(k+1)/6⌋} & n = 6kn_{1} − 5k + 1 and 3 ∤ k, \\ 3(−1)^{k(n_{1}+1)+⌊k/3⌋} & n = 6kn_{1} − 4k − 1 and 3 ∤ k, \\ 2(−1)^{kn_{1}+1} & n = 6kn_{1} − 4k and 3 ∤ k, \\ 2(−1)^{kn_{1}+\binom{k}{2}+1} & n = 6kn_{1} − 3k and 3 ∤ k, \\ 3(−1)^{k(n_{1}+1)+⌊(k+4)/6⌋} & n = 6kn_{1} − 3k + 1 and 3 ∤ k, \\ 3(−1)^{kn_{1}+⌊k/3⌋+1} & n = 6kn_{1} − 2k − 1 and 3 ∤ k, \\ (−1)^{k(n_{1}+1)} & n = 6kn_{1} − 2k and 3 ∤ k, \\ (−1)^{kn_{1}+\binom{k+1}{2}} & n = 6kn_{1} − k and 3 ∤ k, \\ (−1)^{kn_{1}} & n = 6kn_{1} and 3 ∤ k, \\ 0 & otherwise, \end{matrix}

while for k = 1 we have

det_{0≤i,j≤n−1} (∑_{ℓ≥0} \binom{i + j + 1}{ℓ, ℓ + 1}) = \{ \begin{matrix}1 & n ≡ 0, 1, 4, 5 (mod 12), \\ 2 & n ≡ 2, 3 (mod 12), \\ −1 & n ≡ 6, 7, 10, 11 (mod 12), \\ −2 & n ≡ 8, 9 (mod 12), \end{matrix}

and for k = 0 we have

det_{0≤i,j≤n−1} (∑_{ℓ≥0} \binom{i + j + 1}{ℓ, ℓ}) = \{ \begin{matrix}(−8)^{n_{1}−1} & n = 3n_{1} − 2, \\ 2(−8)^{n_{1}−1} & n = 3n_{1} − 1, \\ (−8)^{n_{1}} & n = 3n_{1}. \end{matrix}

Finally, the specialisation x = y = 1 in Theorem 4 yields the result in Corollary 20 a second time.

Obviously, we could have also performed analogous specialisations in Theorems 8–11, thus obtaining even more determinant evaluations. For the sake of brevity, we mention just one of these. It is the special case x = y = 1 of Theorem 8.

Corollary 26. For all positive integers n and non-negative integers k, we have

det_{0≤i,j≤n−1} (\binom{2j}{j + k − i} − t\binom{2j}{j + k + i + 2})

= \{ \begin{matrix}(−1)^{n_{1}\binom{k+1}{2}}t^{k⌊ \frac{n_{1}}{2} ⌋} & n = n_{1}(k + 1), \\ 0 & n ≢ 0 (mod k + 1). \end{matrix}

8. Concluding remarks and questions. We close our article by some comments on the results that we have obtained, and by posing some open questions.

8.1. Is there a connection to symplectic and orthogonal characters? Given a partition λ = (λ_{1}, λ_{2}, …, λ_{n}) (i.e., a non-increasing sequence of non-negative integers), the (irreducible) symplectic character sp_{λ}(x_{1}, x_{2}, …, x_{n}) can be defined by (see [8, Prop. 24.22])

sp_{λ}(x_{1}, x_{2}, …, x_{n})

= \frac{1}{2} det_{1≤i,j≤n} (h_{λ_{i}−i+j}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}) + h_{λ_{i}−i−j+2}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1})) , (8.1)

where, for m ≥ 1, h_{m}(y_{1}, y_{2}, …, y_{N}) := ∑_{1≤i_{1}≤···≤i_{m}≤N} y_{i_{1}} ⋯ y_{i_{m}} is the m-th complete homogeneous symmetric function in the variables y_{1}, y_{2}, …, y_{N}, h_{0}(y_{1}, y_{2}, …, y_{N}) := 1, and h_{m}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}) is short for h_{m}(x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}). It can as well be written alternatively in the form (see [8, Cor. 24.24])

sp_{λ}(x_{1}, x_{2}, …, x_{n})

= det_{1≤i,j≤λ_{1}} (e_{λ′_{i}−i+j}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}) − e_{λ′_{i}−i−j}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1})) , (8.2)

where, for m ≥ 1, e_{m}(y_{1}, y_{2}, …, y_{N}) := ∑_{1≤i_{1}<···<i_{m}≤N} y_{i_{1}} ⋯ y_{i_{m}} is the m-th elementary symmetric function in the variables y_{1}, y_{2}, …, y_{N}, e_{0}(y_{1}, y_{2}, …, y_{N}) := 1, λ′ denotes the partition conjugate to λ, and where we use an analogous convention for the short form e_{m}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}). On the other hand, the (irreducible) odd special orthogonal character so_{λ}(x_{1}, x_{2}, …, x_{n}) can be defined by (see [8, Prop. 24.46])

so_{λ}(x_{1}, x_{2}, …, x_{n})

= det_{1≤i,j≤n} (h_{λ_{i}−i+j}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1) − h_{λ_{i}−i−j}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1)) , (8.3)

where h_{m}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1) is short for h_{m}(x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{n}, x_{n}^{−1}, 1). It can as well be written alternatively in the form (see [8, Cor. 24.35])

so_{λ}(x_{1}, x_{2}, …, x_{n})

= \frac{1}{2} det_{1≤i,j≤λ_{1}} (e_{λ′_{i}−i+j}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1) + e_{λ′_{i}−i−j+2}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1)) , (8.4)

with an analogous convention how to read e_{m}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1).

If one now compares the right-hand sides of (8.2) and (8.3) with the determinants in Theorems 8 and 9, respectively the right-hand sides of (8.1) and (8.4) with the determinants in Theorems 10 and 11, and if one recalls that (8.1)–(8.4) have been interpreted in [7] in terms of generating functions for certain families of non-intersecting lattice paths, then one observes striking similarities. One is led to think that one should be able to specialise the partition λ and the variables x_{1}, x_{2}, …, x_{n} appropriately so that the determinants in Theorems 8–11 are obtained (at least for t = 1). However, we were not able to make this speculation concrete.

8.2. A combinatorial derivation of (4.4) and (4.5)? The determinantal relations (4.2) and (4.3) were derived by combinatorial means, making appeal to the Lindström– Gessel–Viennot theorem presented here in Theorem 7. We could also have derived these relations by some row manipulations, but we believe that the combinatorial argument is much more illuminating. On the other hand, the determinantal relations (4.4) and (4.5) were derived by row manipulations. This leads naturally to the question whether there are also combinatorial explanations for (4.4) and (4.5)? Indeed, the determinants on the left-hand side can be combinatorially interpreted as generating functions for families of non-intersecting lattice paths by using again Theorem 7. Moreover, there is also a combinatorial model available for the right-hand side determinants, which would interpret them as generating functions for families of non-intersecting paths where, in addition, reflections of paths do also not intersect other paths (cf. [7, Sec. 7] for more detailed explanations on this model). However, we were not able to use these combinatorial interpretations to develop a combinatorial understanding of (4.4) and (4.5).

8.3. Determinant evaluations of Eğecioğlu, Redmond and Ryavec. In [5, 6], Eğecioğlu, Redmond and Ryavec go in a direction somewhat “orthogonal” to ours, in that they consider the Hankel determinants

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

(among others). This should be compared to the determinants in Corollaries 19, 20 and 23. Eğecioğlu, Redmond and Ryavec develop a complex method based on differential equations for polynomial generalisations of such determinants, which enables them to prove closed form evaluations in the cases k = 0, 1, …, 4. However, if k > 4, there do not seem to be “nice” formulae for these determinants, as opposed to our families of determinants. On the other hand, Eğecioğlu, Redmond and Ryavec conjecture (see [6, Sec. 11]) that also their determinants follow a modular pattern, depending on n and k, in general. Although there is only marginal overlap between their results and ours, it is still possible that there is a unifying picture for both sets of results (and conjectures) lurking behind.

References

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

2. T. Amdeberhan and D. Zeilberger, Determinants through the looking glass, Adv. Appl. Math. 27 (2001), 225–230, Maple package DODGSON available at

http://www.math.rutgers.edu/~zeilberg/tokhniot/DODGSON.

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

4. L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

5. Ö. Eğecioğlu, T. Redmond and C. Ryavec, Almost product evaluation of Hankel determinants, Electron. J. Combin. 15 (1) (2008), Article #R6, 58 pp.

6. Ö. Eğecioğlu, T. Redmond and C. Ryavec, A multilinear operator for almost product evaluation of Hankel determinants, J. Combin. Theory Ser. A 117 (2010), 77–103.

7. M. Fulmek and C. Krattenthaler, Lattice path proofs for determinant formulas for symplectic and orthogonal characters, J. Combin. Theory Ser. A 77 (1997), 3–50.

8. W. Fulton and J. Harris, Representation Theory, Springer–Verlag, New York, 1991.

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

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

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

11. 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-Ver-lag, New York, 2004, pp. 337–356.

12. C. Krattenthaler, The enumeration of lattice paths with respect to their number of turns, Advances in Combinatorial Methods and Applications to Probability and Statistics (N. Balakrishnan, ed.), Birkhäuser, Boston, 1997, pp. 29–58.

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

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

15. C. Krattenthaler, On multiplicities of points on Schubert varieties in Graßmannians II, J. Algebraic Combin. 22 (2005), 273–288.

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

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

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

19. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96–131.

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

21. D. Zeilberger, The holonomic Ansatz II. Automatic discovery (!) and proof (!!) of holonomic determinant evaluations, Ann. Combin. 11 (2007), 241–247, Maple package DET available at

http://www.math.rutgers.edu/~zeilberg/tokhniot/DET.