Some determinants of path generating functions, II

C. Krattenthaler^{†∗} and D. Yaqubi^{‡∗∗}

†Fakultät für Mathematik, Universität Wien, Oskar-Norgenstern-Platz 1, A-1090 Vienna, Austria.

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

‡Department of Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran

Abstract. We evaluate Hankel determinants of matrices in which the entries are generating functions for paths consisting of up-steps, down-steps and level steps with a fixed starting point but variable end point. By specialisation, these determinant evaluations have numerous corollaries. In particular, one consequence is that the Hankel determinant of Motzkin prefix numbers equals 1, regardless of the size of the Hankel matrix.

1. Introduction. Determinants (and Hankel determinants in particular) of path counting numbers (respectively, more generally, of path generating functions) are ubiquitous in the literature. Their “popularity” stems in part from the fact that, frequently, such determinants can be evaluated into attractive, compact closed formulae. This article contributes further to this body of results.

The determinants that we consider here involve matrices formed from numbers and generating functions of three-step paths. More precisely, our paths consist of up-steps (1, 1), level steps (1, 0), and down-steps (1, −1). The number of such paths from (0, 0) to (n, 0) that never run below the x-axis is known as the Motzkin number M_{n} (cf. [7, Exercise 6.38]; Figure 1.a shows an example of a path contributing to M_{11}). On the other hand, the number of paths from (0, 0) to (2n, 0) that consist only of up-steps (1, 1) and down-steps (1, −1) and do not run below the x-axis is known as the Catalan number C_{n} = \frac{1}{n+1} \binom{2n}{n}

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

Key words and phrases. Hankel determinants, Catalan numbers, ballot numbers, Motzkin numbers, Motzkin prefix numbers, Motzkin paths.

∗Research partially supported by the Austrian Science Foundation FWF, grant S50-N15, in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.

∗∗Current address: Faculty of Agriculture and Animal Science, University of Torbat-e Jam, Iran.

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

a. A Motzkin path b. A Catalan path

Figure 1

(cf. [7, Exercise 6.19]; Figure 1.b shows an example of a path contributing to C_{8}). It is well-known that

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}(M_{i+j}) = 1,  (1.3)

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.4)

see e.g. [8, 1]).

In [2], these Hankel determinant evaluations were generalised to Hankel determinant evaluations of path generating functions as follows (among others). We define P_{n}(k, l) as the generating function ∑_{P} w(P), where P runs over all three-step paths from (0, k) to (n, l), 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}^{+}(k, l) 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. Clearly, if we specialise x = −y = \sqrt{−1}, then P_{2n}^{+}(0, 0) reduces to C_{n} (and P_{2n+1}^{+}(0, 0) = 0 for all n), while, if we specialise x = \frac{1}{2}(1+\sqrt{−3}), y = \frac{1}{2}(1−\sqrt{−3}), then P_{n}^{+}(0, 0) reduces to M_{n}. The somewhat unusual parametrisation that we have chosen here turns out to be useful in the context of the Hankel determinant evaluations of [2] and of the present article, in that the evaluations can be much more elegantly presented than it would be possible under more straightforward parametrisations.

The theorems from [2] that generalise (1.1)–(1.4) to the weighted setting are the following two.

Theorem 1 ([2, 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.5)

Theorem 2 ([2, 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.6)

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.5) and (1.6) 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} .

The work on the present article began with computer experiments of the second author on Hankel determinants of Motzkin prefix numbers. By definition, the n-th Motzkin prefix number is the number of three-step paths consisting of n steps, starting at the origin, and not running below the x-axis (with any end point). We denote this number by MP_{n}. The aforementioned computer experiments seemed to indicate that

det_{0≤i,j≤n−1}(MP_{i+j}) = 1  (1.7)

for all n. Subsequent consultation of the On-Line Encyclopedia of Integer Sequences [6, sequence A005773] revealed that this same observation had already been made earlier by Philippe Deléham in 2007. On the other hand, in view of the earlier work [2], the first author was obviously led to look at the weighted generalisation of the Hankel determinant in (1.7), namely

det_{0≤i,j≤n−1} (∑_{l≥0} P_{i+j}^{+}(0, l)) ,

or even more generally at

det_{0≤i,j≤n−1} (∑_{l≥0} P_{i+j}^{+}(k, l)) .

The entries here are generating functions for three-step paths of a given length that start at height k and never run below the x-axis.

From here, it did not take very long to discover the closed form evaluations of the Hankel determinants of path generating functions in (1.8) and (1.9) below. Of course, these were at this point only conjectures.

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

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

(1.8)

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

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

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

(1.9)

Remarks. (1) Also here, if k = 0, the formulae in Theorems 3 and 4 have to be read according to the convention that only the first line on the right-hand sides of (1.8) and (1.9) applies; that is,

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

and

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

Similarly, if k = 1 only the first two lines in Theorem 4 apply; that is,

det_{0≤i,j≤n−1} (∑_{l≥0} P_{i+j+1}^{+}(1, l))

= \{ \begin{matrix}(−1)^{n_{1}}(xy)^{4\binom{n_{1}+1}{2}−n} (\frac{y^{2(n_{1}+1)}−x^{2(n_{1}+1)}}{y^{2}−x^{2}} − \frac{y^{2n_{1}} −x^{2n_{1}}}{y^{2}−x^{2}} ) , & if n = 2n_{1}, \\ (−1)^{n_{1}}(xy)^{4\binom{n_{1}+1}{2}} \frac{(1+x)(1+y)(y^{2(n_{1}+1)}−x^{2(n_{1}+1)})}{y^{2}−x^{2}} & if n = 2n_{1} + 1. \end{matrix}

(2) Clearly, the specialisation x = \frac{1}{2}(1+\sqrt{−3}), y = \frac{1}{2}(1−\sqrt{−3}), and k = 0 of Theorem 3 establishes (1.7). Many more interesting specialisations are possible, see Section 6.

In the present article, we provide proofs for these determinant evaluations. As it turns out, there is a “connection matrix” (see Section 3) which, upon multiplication on the left, transforms the Hankel matrices on the left-hand sides of (1.8) and (1.9) into the matrices on the left-hand sides of (1.5) and (1.6), respectively, up to some “correction” in the last row, see Lemmas 11 and 12 in Sections 4 and 5. This fact then allows us to complete the evaluation of the determinants in Theorems 3 and 4 by adapting arguments from the proofs of Theorems 1 and 2 in [2] to the new situation here, see the proofs of Theorems 3 and 4 in Sections 4 and 5. Auxiliary results for these proofs are collected in Section 3, which themselves depend on elementary properties of our path generating functions that are recalled in Section 2. We conclude our article with a list of interesting specialisations of our two main theorems in Section 6.

2. Elementary facts about three-step paths. In the proofs of our theorems, we need three elementary properties that our path generating functions satisfy. We list them here as (2.1)–(2.3). In the remainder of this section, we discuss four types of specialisations of the path generating functions, which will then be considered in Section 6 in the context of Theorems 3 and 4.

By retracing paths from the back to the beginning, one sees that

P_{n}^{+}(k, l) = (xy)^{k−l}P_{n}^{+}(l, k),  (2.1)

and the same symmetry relation holds for P_{n}(k, l), but we shall not have any need for the latter.

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

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

In fact, elementary combinatorial reasoning shows that there is an explicit formula for the path generating function P_{n}(k, l), namely

P_{n}(k, l) = ∑_{s≥0} \frac{n!}{s! (s + l − k)! (n − l + k − 2s)!}(x + y)^{n−l+k−2s}(xy)^{s}.  (2.3)

In combination with (2.2), this also yields an explicit formula for P_{n}^{+}(k, l). To be precise, we have

P_{n}^{+}(k, l) = ∑_{s≥0} \binom{n}{l − k + 2s} (\binom{l − k + 2s}{s} − \binom{l − k + 2s}{s − k − 1}) (x+y)^{n−l+k−2s}(xy)^{s}. (2.4)

In Section 6, we shall discuss specialisations of Theorems 3 and 4. The relevant specialisations of our path generating functions from [2, Eqs. (2.5)–(2.10)] are the following: with ω denoting a primitive sixth root of unity, we have

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

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

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

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

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

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

is a trinomial coefficient. We add one more such specialisation,

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

This is easy to derive from [2, Eq. (2.4)]. (The specialisations (2.11) and (2.12) were not given in [2] since they do not lead to anything new in the context of [2]. In our context they do.) By summation over l on both sides of (2.6), (2.8), (2.10), and (2.12), we obtain

∑_{l≥0} P_{n}^{+}(k, l)|_{x=−y=\sqrt{−1}} = ∑_{l=0}^{k} \binom{n}{⌊\frac{1}{2}(n + 1 − k)⌋ + l},  (2.13)

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

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

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

The last identity can in fact be simplified, in view of the elementary summation formula

∑_{s=0}^{M}(−1)^{s}\binom{N}{s} = (−1)^{M} \binom{N − 1}{M}.

Namely, we have

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

Care must be applied of how to interpret the expression on the right-hand side for n = 0: in (2.16), the value for n = 0 must be taken as 1, regardless of the choice of k.

3. The connection matrix A(n). In this section, we define the connection matrix A(n) announced in the introduction, see (3.1). Multiplication of our matrices of Motzkin prefix generating functions on the left by A(n) allows us to connect them — via Lemmas 11 and 12 — to the matrices of Motzkin generating functions in [2], presented here in Theorems 1 and 2 in the previous section. The connection is not completely direct, it is only up to correction matrices (the matrices C_{0}(n, k) and C_{1}(n, k) in the lemmas). Nevertheless, since A(n) has determinant 1 (see Lemma 6), multiplication on the left by A(n) does not change the determinant, and some further work makes it possible to deduce Theorems 3 and 4 on the basis of results from Theorems 1 and 2.

We define the matrix A(n) := (A_{n,i,j})_{0≤i,j≤n−1} by

A_{n,i,j} = \{ \begin{matrix}\frac{(1+x)(1+y)}{xy}, & if i = j < n − 1, \\ −\frac{1}{xy} , & if i = j − 1 < n − 1, \\ \frac{(−1)^{n+j}}{xy} & ∑ & {n \atop l=j} & (\binom{l}{j}\binom{n+j−1−l}{j}x^{l−j}y^{n−1−l} \\ +\binom{l}{j}\binom{n+j−l}{j}x^{l−j}y^{n−l}) , & if i = n − 1 and j < n − 1, \\ \frac{xy−(n−1)(x+y)}{xy}, & if i = j = n − 1, \\ 0, & otherwise. \end{matrix}

(3.1)

Here, binomial coefficients have to be interpreted as 0 as soon as a lower parameter becomes negative or an upper parameter is less than the lower parameter. For example, the matrix A(4) has the form

( \begin{matrix}\frac{(1+x)(1+y)}{xy} & −\frac{1}{xy} & 0 & 0 \\ 0 & \frac{(1+x)(1+y)}{xy} & −\frac{1}{xy} & 0 \\ 0 & 0 & \frac{(1+x)(1+y)}{xy} & −\frac{1}{xy} \\ A_{4,3,0} & A_{4,3,1} & A_{4,3,2} & \frac{xy−3(x+y)}{xy} \end{matrix} ) ,

where the entries A_{4,3,0}, A_{4,3,1}, A_{4,3,2} are the polynomials in x and y divided by xy given by the next-to-last line in (3.1).

In the proof of Lemma 9, we shall need alternative formulae for the matrix entries in the last row of A(n), which are presented in the lemma below.

Lemma 5. For all non-negative integers n and j with 0 ≤ j ≤ n − 2, we have

A_{n,n−1,j} = \frac{(−1)^{n+j}}{xy} ∑_{r≥0}(−1)^{r} (\binom{n − r − 1}{r}\binom{n − 2r − 1}{j}(xy)^{r}(x + y)^{n−1−j−2r}

+\binom{n − r}{r}\binom{n − 2r}{j}(xy)^{r}(x + y)^{n−j−2r}) . (3.2)

Proof. Since the two terms in the summand on the right-hand side of (3.2) arise from each other by a shift of n by 1, it suffices to concentrate on one of them:

∑_{r≥0}(−1)^{r}\binom{n − r}{r}\binom{n − 2r}{j}(xy)^{r}(x + y)^{n−j−2r}

= ∑_{r≥0}(−1)^{r}\binom{n − r}{r}\binom{n − 2r}{j}(xy)^{r} ∑_{ℓ≥0} \binom{n − j − 2r}{ℓ}x^{ℓ}y^{n−j−2r−ℓ}

= ∑_{l≥0} x^{l}y^{n−j−l} ∑_{r≥0}(−1)^{r}\binom{n − r}{r}\binom{n − 2r}{j}\binom{n − j − 2r}{l − r}

= ∑_{l≥0} x^{l}y^{n−j−l}\binom{n}{j}\binom{n − j}{l}_{2}F_{1}[ \begin{matrix}j + l − n, −l \\ −n \end{matrix}; 1] .

Here, we used the standard hypergeometric notation

rF_{s}[ \begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix}; z] = ∑_{l=0}^{∞} \frac{(a_{1})_{l} ⋯ (a_{r})_{l}}{l! (b_{1})_{l} ⋯ (b_{s})_{l}} z^{l} ,

where the Pochhammer symbol (α)_{m} is defined by (α)_{m} = α(α + 1)(α + 2) ⋯ (α + m − 1) for m > 0, and (α)_{0} = 1. The above _{2}F_{1}-series can be evaluated by means of the Chu– Vandermonde summation formula (see [5, (1.7.7); Appendix (III.4)]),

2F_{1}[ \begin{matrix}a, −N \\ c \end{matrix} ; 1] = \frac{(c − a)_{N}}{(c)_{N}} ,  (3.3)

where N is a nonnegative integer. Thus, we obtain

∑_{l≥0} x^{l}y^{n−j−l}\binom{n}{j}\binom{n − j}{l}\frac{(−j − l)_{l}}{(−n)_{l}} = ∑_{l≥0} x^{l}y^{n−j−l}\binom{n − l}{j}\binom{l + j}{j}

= ∑_{l=j}^{n} x^{l−j}y^{n−l}\binom{n − l + j}{j}\binom{l}{j}.

This matches exactly with the original definition of A_{n,n−1,j}. □

Next we show that the determinant of the connection matrix A(n) is equal to 1. The proof requires an identity that is established separately in Lemma 7.

Lemma 6. For all positive integers n, we have det A(n) = 1.

Proof. We replace the last column of A(n) by

∑_{j=0}^{n−1} \frac{1}{(1 + x)^{n−1−j}(1 + y)^{n−1−j}} · (column j).

Clearly, this does not change the value of the determinant of A(n). Moreover, in the resulting matrix, all entries in the last column will become 0, except for the entry in the last row, which equals

∑_{j=0}^{n−2} \frac{1}{(1 + x)^{n−1−j}(1 + y)^{n−1−j}} A_{n,n−1,j} + \frac{xy − (n − 1)(x + y)}{xy}.

By Lemma 7, this expression equals

(\frac{xy}{(1 + x)(1 + y)})^{n−1} .  (3.4)

We may now expand the determinant with respect to the last column. Since in this column only the entry in the last row is non-zero, the result is that entry — that is, the expression in (3.4) — multiplied by the remaining minor det_{0≤i,j≤n−2}(A_{n,i,j}). This latter determinant is the determinant of a lower triangular matrix. Obviously, it equals the product of the diagonal entries. Altogether we obtain 1 as is straightforward to see. This establishes the lemma. □

Lemma 7. For all non-negative integers m, we have

∑_{j=0}^{n−2} \frac{1}{(1 + x)^{n−1−j}(1 + y)^{n−1−j}} A_{n,n−1,j} + \frac{xy − (n − 1)(x + y)}{xy} = (\frac{xy}{(1 + x)(1 + y)})^{n−1} .

(3.5)

Proof. We start with the precise form of the left-hand side of (3.5),

\frac{1}{xy} ∑_{j=0}^{n−2} \frac{(−1)^{n+j}}{(1 + x)^{n−1−j}(1 + y)^{n−1−j}} ∑_{l=j}^{n} (\binom{l}{j}\binom{n + j − 1 − l}{j}x^{l−j}y^{n−1−l}

+\binom{l}{j}\binom{n + j − l}{j}x^{l−j}y^{n−l}) + \frac{xy − (n − 1)(x + y)}{xy}.

It is straightforward to see that, by extending the sum over j to the range 0 ≤ j ≤ n, the last term in the above expression gets “swallowed”. In other terms, the expression can be rewritten as

\frac{1}{xy} ∑_{j=0}^{n} \frac{(−1)^{n+j}}{(1 + x)^{n−1−j}(1 + y)^{n−1−j}} ∑_{l=j}^{n} (\binom{l}{j}\binom{n + j − 1 − l}{j}x^{l−j}y^{n−1−l}

+\binom{l}{j}\binom{n + j − l}{j}x^{l−j}y^{n−l})

= \frac{(−1)^{n}}{xy(1 + x)^{n−1}(1 + y)^{n−1}}

× (∑_{j=0}^{n−1}(−1)^{j} ∑_{l=j}^{n−1} \binom{l}{j}\binom{n + j − 1 − l}{j}x^{l−j}y^{n−1−l}(1 + x)^{j}(1 + y)^{j}

+ ∑_{j=0}^{n}(−1)^{j} ∑_{l=j}^{n} \binom{l}{j}\binom{n + j − l}{j}x^{l−j}y^{n−l}(1 + x)^{j}(1 + y)^{j}) . (3.6)

Here, to lower the upper bounds on the summation indices of the sums over j and l in the first double sum is allowed due to the vanishing properties of the binomial coefficients \binom{l}{j} and \binom{n+j−1−l}{j}. The purpose of this “exercise” is to make it visible that the first double sum arises from the second by replacing n by n − 1.

Hence it suffices to concentrate on the second double sum. The coefficient of x^{A}y^{B}, 0 ≤ A, B ≤ n, in this sum is given by

∑_{j=0}^{n}(−1)^{j} ∑_{l=j}^{n} \binom{l}{j}\binom{n + j − l}{j}\binom{j}{A − l + j}\binom{j}{B − n + l}

= ∑_{j=0}^{n}(−1)^{j} ∑_{l=0}^{n−j} \binom{l + j}{j}\binom{n − l}{j}\binom{j}{A − l}\binom{j}{B − n + l + j}

= ∑_{l=0}^{n} ∑_{j=A−l}^{n}(−1)^{j}\binom{l + j}{j}\binom{n − l}{j}\binom{j}{A − l}\binom{j}{B − n + l + j}.

We write the inner sum over j in hypergeometric notation. Thereby we obtain

∑_{l=0}^{n}(−1)^{A−l}\binom{A}{l}\binom{n − l}{A − l}\binom{j}{A − l}\binom{j}{A + B − n}_{2}F_{1}[ \begin{matrix}A + 1, A − n \\ A + B − n + 1 \end{matrix} ; 1] .

The _{2}F_{1}-series can again be evaluated by means of the Chu–Vandermonde summation formula (3.3). We substitute the result and now write the remaining sum over l in hypergeometric notation. Thus, we arrive at

(−1)^{n}\binom{n − B}{n − A}\binom{n}{B}_{2}F_{1}[ \begin{matrix}B − n, −A \\ −n \end{matrix}; 1] .

By applying (3.3) once again and some simplification, we finally get

(−1)^{A+B+n} \frac{(−B)_{A} (−A)_{B}}{A! B!} = \{ \begin{matrix}(−1)^{n}, & if A = B, \\ 0, & otherwise, \end{matrix}  (3.7)

for the second double sum in (3.6). As we discussed earlier, the first double arises from the second by replacing n by n − 1. Thus, these two double sums either both vanish or cancel each other, except for A = B = n; in that latter case we are asking for the coefficient of x^{A}y^{B} = x^{n}y^{n}, which is necessarily zero in the first double sum (because only monomials of lower degree can appear) while it is the (−1)^{n} from (3.7) for the second double sum that survives. If this is substituted in (3.6), the assertion (3.5) follows immediately, which completes the proof of the lemma. □

The next two lemmas provide the identities that are crucial for establishing the link between the matrices in Theorems 3 and 4 and the matrices in [2], made explicit in Lemmas 11 and 12. The first is a relatively simple combinatorial identity.

Lemma 8. For all non-negative integers m, we have

(1 + x)(1 + y) ∑_{l=0}^{m} P_{m}^{+}(k, l) − ∑_{l=0}^{m+1} P_{m+1}^{+}(k, l) = xyP_{m}^{+}(k, 0).  (3.8)

Proof. We have

(1 + x)(1 + y) = 1 + (x + y) + xy.

This is exactly the sum of the weights of an up-step, of a horizontal step, and of a downstep. Thus, the first term in (3.8) is the generating function for paths consisting of m + 1 (horizontal, up- and down-)steps that start at (0, k) and do not run below the x-axis for the first m steps. On the other hand, the second term is the negative of the generating function for the same paths, except that one requires the stronger condition that they do not run below the x-axis for all of their m + 1 steps. Hence, the difference on the left-hand side of (3.8) equals the generating function for all those paths which reach (m, 0) without having passed below the x-axis, but then continue with a down-step. Since a down-step has weight xy, this is exactly the expression on the right-hand side of (3.8). □

The second identity is not combinatorial (at least, the authors do not have a combinatorial interpretation for it). Instead, its proof requires a certain summation formula for hypergeometric series which is stated separately in Lemma 10.

Lemma 9. For non-negative integers m and positive integers n with 0 ≤ m ≤ n, we have

∑_{j=0}^{n−1} A_{n,n−1,j} ∑_{l=0}^{m+j} P_{m+j}^{+}(k, l) = P_{m+n−1}^{+}(k, 0) + (xy)^{n−1} ∑_{l≥0} P_{m}(0, n − k + l),  (3.9)

where the coefficients A_{n,n−1,j} are given in (3.1).

Proof. Using the expression for A_{n,n−1,j} for 0 ≤ j ≤ n − 2 from Lemma 5 and the expression for P_{m+j}^{+}(k, l) in (2.4), we have

∑_{j=0}^{n−1}A_{n,n−1,j} ∑_{l=0}^{m+j+k} P_{m+j}^{+}(k, l)

= ∑_{j=0}^{n−2} ∑_{r,s≥0} ∑_{l=0}^{m+j+k} \frac{(−1)^{n+j+r}}{xy} \binom{m + j}{l − k + 2s} (\binom{l − k + 2s}{s} − \binom{l − k + 2s}{s − k − 1})

· (\binom{n − r − 1}{r}\binom{n − 2r − 1}{j}(xy)^{r+s}(x + y)^{n−1+m−l+k−2r−2s}

+\binom{n − r}{r}\binom{n − 2r}{j}(xy)^{r+s}(x + y)^{n+m−l+k−2r−2s})

+ \frac{xy − (n − 1)(x + y)}{xy} ∑_{l=0}^{m+n+k−1} P_{m+n−1}^{+}(k, l).

We would like to extend the sum over j to range over 0 ≤ j ≤ n. Because of the binomial coefficients \binom{n−2r−1}{j} and \binom{n−2r}{j}, this extension is indeed without any harm except if r = 0. Taking the corresponding corrections into account, we see that the above expression is equal to

∑_{j=0}^{n} ∑_{r,s≥0} ∑_{l=0}^{m+j+k} \frac{(−1)^{n+j+r}}{xy} \binom{m + j}{l − k + 2s} (\binom{l − k + 2s}{s} − \binom{l − k + 2s}{s − k − 1})

· (\binom{n − r − 1}{r}\binom{n − 2r − 1}{j}(xy)^{r+s}(x + y)^{n−1+m−l+k−2r−2s}

+\binom{n − r}{r}\binom{n − 2r}{j}(xy)^{r+s}(x + y)^{n+m−l+k−2r−2s})

+ ∑_{s≥0} ∑_{l=0}^{m+n+k−1} \frac{1}{xy} \binom{m + n − 1}{l − k + 2s} (\binom{l − k + 2s}{s} − \binom{l − k + 2s}{s − k − 1})

· ((xy)^{s}(x + y)^{n−1+m−l+k−2s} + n(xy)^{s}(x + y)^{n+m−l+k−2s})

− ∑_{s≥0} ∑_{l=0}^{m+n+k} \frac{1}{xy} \binom{m + n}{l − k + 2s} (\binom{l − k + 2s}{s} − \binom{l − k + 2s}{s − k − 1})

· (xy)^{s}(x + y)^{n+m−l+k−2s}

+ \frac{xy − (n − 1)(x + y)}{xy} ∑_{l=0}^{m+n+k−1} P_{m+n−1}^{+}(k, l).

We have

∑_{j=0}^{n}(−1)^{j}\binom{m + j}{l − k + 2s}\binom{n − 2r}{j} = \binom{m}{l − k + 2s}_{2}F_{1}[ \begin{matrix}m + 1, 2r − n \\ m − l + k − 2s + 1 \end{matrix} ; 1]

= \binom{m}{l − k + 2s}\frac{(−l + k − 2s)_{n−2r}}{(m − l + k − 2s + 1)_{n−2r}}

= (−1)^{n}\binom{m}{l − n − k + 2s + 2r},

again by the Chu–Vandermonde summation formula (3.3). If this is substituted (twice — once with n replaced by n − 1) in the quadruple sum of our earlier obtained expression, then we get

∑_{r,s≥0} ∑_{l=0}^{m+k} \frac{(−1)^{r}}{xy} (\binom{l − k + 2s}{s} − \binom{l − k + 2s}{s − k − 1})

· (−\binom{n − r − 1}{r}\binom{m}{l − n − k + 2s + 2r + 1}(xy)^{r+s}(x + y)^{n−1+m−l+k−2r−2s}

+\binom{n − r}{r}\binom{m}{l − n − k + 2s + 2r}(xy)^{r+s}(x + y)^{n+m−l+k−2r−2s})

+ \frac{(1 + n(x + y))}{xy} ∑_{l=0}^{m+n+k−1} P_{m+n−1}^{+}(k, l) − \frac{1}{xy} ∑_{l=0}^{m+n+k} P_{m+n}^{+}(k, l)

+ \frac{xy − (n − 1)(x + y)}{xy} ∑_{l=0}^{m+n+k−1} P_{m+n−1}^{+}(k, l).  (3.10)

We observe that

(1 + n(x + y)) + (xy − (n − 1)(x + y)) = (1 + x)(1 + y).

Hence, by Lemma 8, the last two lines of (3.10) simplify to P_{m+n−1}^{+}(k, 0), which is the first term on the right-hand side of (3.9).

The remaining task is therefore to simplify the triple sum in (3.10). In order to do so, we split it into two parts,

S_{1} = ∑_{r,s≥0} ∑_{l=0}^{m+k} \frac{(−1)^{r}}{xy} \binom{l − k + 2s}{s}

· (−\binom{n − r − 1}{r}\binom{m}{l − n − k + 2s + 2r + 1}(xy)^{r+s}(x + y)^{n−1+m−l+k−2r−2s}

+\binom{n − r}{r}\binom{m}{l − n − k + 2s + 2r}(xy)^{r+s}(x + y)^{n+m−l+k−2r−2s})

= ∑_{r,s≥0} ∑_{l=0}^{m+k} \frac{(−1)^{r}}{xy} \binom{m}{l − n − k + 2s + 2r}(xy)^{r+s}(x + y)^{n+m−l+k−2r−2s}

· (\binom{l − k + 2s}{s}\binom{n − r}{r} − \binom{l − k + 2s − 1}{s}\binom{n − r − 1}{r}) ,

and

S_{2} = − ∑_{r,s≥0} ∑_{l=0}^{m+k} \frac{(−1)^{r}}{xy} \binom{l − k + 2s}{s − k − 1}

· (−\binom{n − r − 1}{r}\binom{m}{l − n − k + 2s + 2r + 1}(xy)^{r+s}(x + y)^{n−1+m−l+k−2r−2s}

+\binom{n − r}{r}\binom{m}{l − n − k + 2s + 2r}(xy)^{r+s}(x + y)^{n+m−l+k−2r−2s})

= − ∑_{r,s≥0} ∑_{l=0}^{m+k} \frac{(−1)^{r}}{xy} \binom{m}{l − n − k + 2s + 2r}(xy)^{r+s}(x + y)^{n+m−l+k−2r−2s}

· (\binom{l − k + 2s}{s − k − 1}\binom{n − r}{r} − \binom{l − k + 2s − 1}{s − k − 1}\binom{n − r − 1}{r}) .

We start with the computation of S_{1}. We let t = r + s and write the sum over r in hypergeometric notation. This leads to

S_{1} = ∑_{t≥0} ∑_{l=0}^{m+k} \frac{1}{xy} \binom{m}{l − n − k + 2t}(xy)^{t}(x + y)^{n+m−l+k−2t}

· \binom{l − k + 2t − 1}{t − 1}_{5}F_{4}[ \begin{matrix}1 + \frac{nt}{l−k−n}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −t, −l + k − t \\ \frac{nt}{l−k−n}, 1 − n, \frac{1}{2} − \frac{l}{2} + \frac{k}{2} − t, 1 − \frac{l}{2} + \frac{k}{2} − t \end{matrix}; 1] .

Next, we apply the contiguous relation

5F_{4}[ \begin{matrix}a, b, c, A_{1}, A_{2} \\ B_{1}, B_{2}, B_{3}, B_{4} \end{matrix} ; z] = \frac{b (c − a − 1)}{(b − a) (c − 1)}_{5}F_{4}[ \begin{matrix}a, b + 1, c − 1, A_{1}, A_{2} \\ B_{1}, B_{2}, B_{3}, B_{4} \end{matrix} ; z]

+ \frac{a (c − b − 1)}{(a − b) (c − 1)}_{5}F_{4}[ \begin{matrix}a + 1, b, c − 1, A_{1}, A_{2} \\ B_{1}, B_{2}, B_{3}, B_{4} \end{matrix} ; z]

with a = −t, b = −l+k−t, c = 1+ \frac{nt}{l−k−n}, A_{1} = −\frac{n}{2}, A_{2} = \frac{1}{2} − \frac{n}{2}, B_{1} = \frac{nt}{l−k−n}, B_{2} = 1−n, B_{3} = \frac{1}{2} − \frac{l}{2} + \frac{k}{2} −t, and B_{4} = 1− \frac{l}{2} + \frac{k}{2} −t. Since, with our choice, we have c−1 = B_{1}, the effect is that, on the right-hand side, the _{5}F_{4}-series reduce to _{4}F_{3}-series. Thus, we obtain

S_{1} = ∑_{t≥0} ∑_{l=0}^{m+k} \frac{1}{xy} \binom{m}{l − n − k + 2t}\binom{l − k + 2t − 1}{t − 1}(xy)^{t}(x + y)^{n+m−l+k−2t}

· (\frac{l − k + t}{n}_{4}F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −t, 1 − l + k − t \\ 1 − n, \frac{1}{2} − \frac{l}{2} + \frac{k}{2} − t, 1 − \frac{l}{2} + \frac{k}{2} − t \end{matrix}; 1]

−\frac{l − k + t − n}{n}_{4}F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, 1 − t, −l + k − t \\ 1 − n, \frac{1}{2} − \frac{l}{2} + \frac{k}{2} − t, 1 − \frac{l}{2} + \frac{k}{2} − t \end{matrix}; 1]) .

Both _{4}F_{3}-series can be evaluated by means of Lemma 10. After some simplification, the result is

S_{1} = \frac{1}{xy} ∑_{t≥0} ∑_{l=0}^{m+k} \binom{m}{l − n − k + 2t}\binom{l − k + 2t − n}{t − n}(xy)^{t}(x + y)^{n+m−l+k−2t}

= ∑_{t≥0} ∑_{l=0}^{m+k} \frac{m!}{t! (l − k + t + n)! (m − n − l + k − 2t)!}(xy)^{t+n−1}(x + y)^{m−n−l+k−2t}

= (xy)^{n−1} ∑_{l≥0} P_{m}(0, n − k + l).

Here, we replaced t by t + n to go from the first to the second line, and subsequently we used (2.3) to arrive at the last line. Clearly, this is the second term on the right-hand side of (3.9).

A similar computation yields

S_{2} = \frac{1}{xy} ∑_{t≥0} ∑_{l=0}^{m+k} \binom{m}{l − n − k + 2t}\binom{l − k + 2t − n}{t − n − k − 1}(xy)^{t}(x + y)^{n+m−l+k−2t}.

Due to the binomial coefficient \binom{l−k+2t−n}{t−n−k−1}, the summation index t must be at least n+k+1 in order to generate non-vanishing summands. However, in that case we have

l − n − k + 2t ≥ l + n + k + 2 ≥ l + m + k + 2 > m,

which makes the binomial coefficient \binom{m}{l−n−k+2t} vanish. In other words, we have S_{2} = 0. This completes the proof of the lemma. □

The following is Lemma A3 from [4].

Lemma 10. Let n be a positive integer. Then

4F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ 1 − n, \frac{B}{2} , \frac{1}{2} + \frac{B}{2} \end{matrix} ; 1] = \frac{(A + B)_{n}}{(B)_{n}} + \frac{(−A)_{n}}{(B)_{n}} .

4. Proof of Theorem 3. We first use the results from the previous section to connect the matrix of Motzkin prefix generating functions on the left-hand side of (1.8) to a matrix of Motzkin generating functions that appeared in [2].

Lemma 11. Define matrices M_{0}(n, k) and MP_{0}(n, k) by

M_{0}(n, k) := (P_{i+j}^{+}(k, 0))_{0≤i,j≤n−1}

and

MP_{0}(n, k) := (∑_{l≥0} P_{i+j}^{+}(k, l))_{0≤i,j≤n−1} .

Then

A(n) · MP_{0}(n, k) = M_{0}(n, k) + C_{0}(n, k),

where A(n) is given by (3.1) and the “correction matrix” C_{0}(n, k) := (C_{n,k,i,j}^{(0)})_{0≤i,j≤n−1} is defined via

C_{n,k,i,j}^{(0)} = \{ \begin{matrix}0, & if i ≤ n − 2, \\ (xy)^{n−1} ∑_{l≥0} P_{j}(0, n − k + l), & if i = n − 1. \end{matrix}

Proof. This is a direct consequence of Lemmas 8 and 9. □

We are now in the position to prove Theorem 3.

Proof of Theorem 3. We start with

MP_{0}(n, k) = (∑_{l≥0} P_{i+j}^{+}(k, l)) .

We multiply on the left by A(n). According to Lemma 11, we get

M_{0}(n, k) + C_{0}(n, k)

= (\{ \begin{matrix}P_{i+j}^{+}(k, 0), & for i ≤ n − 2 \\ P_{n+j−1}^{+}(k, 0) + (xy)^{n−1} ∑_{l≥0} P_{j}(0, n − k + l), & for i = n − 1 \end{matrix} ) .

Since det A(n) = 1 by Lemma 6, the determinant of M_{0}(n, k) + C_{0}(n, k) is the same as the determinant of MP_{0}(n, k). If we apply relation (2.1) with l = 0, then we see that we have transformed our problem into the problem of evaluation of the determinant of

(xy)^{k}M′_{0}(n, k) + C_{0}(n, k),

where

M′_{0}(n, k) := (P_{i+j}^{+}(0, k))_{0≤i,j≤n−1} .

The determinant of M′_{0}(n, k) is evaluated in Theorem 1. As it turns out, for a while we may now follow the arguments of the proof of this evaluation in [2]. For the convenience of the reader, we summarise the main steps here.

The first step in [2] makes use of the combinatorics of non-intersecting lattice paths, see Section 4 there. One may however do equally well without combinatorics, as we now explain. By cutting paths after i steps, it is easy to see that the equation

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

holds. Thus, we see that (xy)^{k}M′_{0}(n, k) + C_{0}(n, k) is equal to the product of the matrices

(P_{i}^{+}(0, ℓ))_{0≤i,ℓ≤n−1}  (4.2)

and

(xy)^{k} (P_{j}^{+}(ℓ, k))_{0≤ℓ,j≤n−1} + C_{0}(n, k).  (4.3)

Indeed, since P_{i}^{+}(0, ℓ) = 0 for i < ℓ and P_{i}^{+}(0, i) = 1, the matrix in (4.2) is lower triangular with 1’s on the main diagonal, and thus we have

(P_{i}^{+}(0, ℓ))_{0≤i,ℓ≤n−1} · C_{0}(n, k) = C_{0}(n, k).

Moreover, for the same reason the determinant of the matrix in (4.2) is 1. Hence, the determinant of (4.3) still equals det MP_{0}(n, k).

The second step in [2] (see the first paragraph of Section 5 there) consists in the use of (2.2) in order to rewrite P_{j}^{+}(ℓ, k). In our case, we are led to the problem of evaluating the determinant of

(xy)^{k} (P_{j}(i, k) − (xy)^{ℓ+1}P_{j}(−i − 2, k))_{0≤i,j≤n−1} + C_{0}(n, k).  (4.4)

In the third step in [2] (see Eqs. (5.6) and (5.7) there with t = 1), certain row operations are applied. To be precise, row (h(2k + 2) + b) of the matrix obtained so far gets replaced by

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

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

if 0 ≤ b ≤ k − 1, and by

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

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

if k + 1 ≤ b ≤ 2k. We apply these same operations to the matrix in (4.4). The important feature of these operations is that, to obtain a row of the new matrix, only this row and earlier rows are involved. Therefore, by the computations performed in [2, proof of Theorem 8 with t = 1] that finally lead to (5.8) there and the subsequent two displays, these operations transform the matrix in (4.4) into the matrix

(xy)^{k}N_{0}(n, k) + C_{0}(n, k),  (4.7)

where N_{0}(n, k) = (N_{n,k,i,j}^{(0)})_{0≤i,j≤n−1} with

N_{n,k,h(2k+2)+b,j}^{(0)} = \{ \begin{matrix}−(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), & if 0 ≤ b ≤ k, \\ −(xy)^{(2h+1)(k+1)+b−k}P_{j}(0, (h + 1)(2k + 2) + b − k) \\ +(xy)^{(2h+1)(k+1)}P_{j}(0, (h + 1)(2k + 2) − b + k), \\ if k + 1 ≤ b ≤ 2k + 1. \end{matrix}

Close inspection of the new matrix in (4.7) reveals that its determinant can now rather straightforwardly be deduced.

Case 1: n ≢ 0, 1 (mod k + 1). Let

n = H(2k + 2) + B  (4.8)

with 0 ≤ B ≤ 2k + 1 but B ≠ 0, 1, k + 1, k + 2. Then it is not difficult to see (see the paragraphs after (5.8) in [2]) that, if 1 ≤ B ≤ k, row H(2k +2) of N_{0}(n, k) consists entirely of zeroes, while, if k + 2 ≤ B ≤ 2k + 1, row H(2k + 2) + k + 1 consists entirely of zeroes. In particular, this implies that in our case there is a row of zeroes in the matrix in (4.7), and hence its determinant vanishes. This establishes the third case on the right-hand side of (1.8).

Case 2: n ≡ 1 (mod k+1). With the notation of (4.8), we have B = 1 or B = k+2. By reusing the arguments in Case 1, we see that, here, it is the last row of N_{0}(n, k) (namely row n−1 = H(2k +2)+B −1) which consists entirely of zeroes. Since, in (4.7), the matrix C_{0}(n, k) — which is a matrix with potentially non-zero entries in the last row — is added to (xy)^{k}N_{0}(n, k), we cannot conclude that the determinant of (4.7) vanishes, but rather further analysis is required.

From now on, let n = (k + 1)n_{1} + 1. In order to get a clearer picture, it is convenient to reverse the order of rows s(k + 1), s(k + 1) + 1, …, s(k + 1) + k, for s = 0, 1, …, n_{1} − 1. It should be noticed that this leaves the last row, namely row n − 1 = (k + 1)n_{1}, in place. In this manner, we arrive at the matrix

(xy)^{k}N̄_{0}(n, k) + C_{0}(n, k),  (4.9)

where the matrix N̄_{0}(n, k) = (N̄_{n,k,i,j}^{(0)})_{0≤i,j≤n−1} is given by

N̄_{n,k,h(k+1)+b,j}^{(0)} = \{ \begin{matrix}−(xy)^{(h+1)(k+1)−b}P_{j}(0, (h + 2)(k + 1) − b) \\ +(xy)^{h(k+1)}P_{j}(0, h(k + 1) + b), \\ if 0 ≤ b ≤ k and h(k + 1) + b < n − 1, \\ 0, & if h(k + 1) = n − 1. \end{matrix}

Since P_{a}(0, b) = 0 for a < b, we see that the new matrix (4.9) is upper triangular except for the last row.

The reader should observe that, because of the permutation of the rows, the determinant of the matrix in (4.9) is not necessarily equal to the determinant of MP_{0}(n, k), but that they rather differ by a sign of (−1)^{n_{1}\binom{k+1}{2}}.

Let us concentrate on the last k +2 rows. There, all entries in columns 0, 1, …, n−k −3 are zero. In other words, the matrix N̄_{0}(n, k) + C_{0}(n, k) has a block form

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

where the (k + 2) × (k + 2) submatrix B looks as follows:

B = ( \{ \begin{matrix}(xy)^{n−2}P_{j}(0, i), & for n − k − 2 ≤ i ≤ n − 2 \\ (xy)^{n−1} ∑_{l≥0} P_{j}(0, n − k + l), & for i = n − 1 \end{matrix} ) .

Here, the index j ranges over j = n − k − 2, n − k − 1, …, n − 1. By subtracting xy times row i for i = n − k, n − k + 1, …, n − 2 from the last row, we may transform the matrix in (4.10) into

( \begin{matrix}A & ∗ \\ 0 & B′ \end{matrix} ) ,  (4.11)

where B′ is defined by

( \{ \begin{matrix}(xy)^{n−2}P_{j}(0, i), & for n − k − 2 ≤ i ≤ n − 2 \\ 0, & for i = n − 1 and j ≤ n − 2 \\ (xy)^{n−1}, & for i = j = n − 1 \end{matrix} ) ,

with j again ranging over j = n − k − 2, n − k − 1, …, n − 1. These row operations do not change the value of the determinant, and consequently the determinant of the matrix in (4.9) equals the one in (4.11).

The determinant of (4.11) is easy to compute since it is in fact an upper triangular matrix (including the last row!). Reading along the diagonal of this matrix, we find

(xy)^{k}, (xy)^{k}, …, (xy)^{k},
(xy)^{2k+1}, (xy)^{2k+1} …, (xy)^{2k+1},
(xy)^{3k+2}, (xy)^{3k+2}, …, (xy)^{3k+2},
...................................................
(xy)^{n−2}, (xy)^{n−2}, …, (xy)^{n−2},
(xy)^{n−1},

where, when arranged as above, there are exactly k + 1 entries in each line (except for the last line, of course). The product of these entries is

(xy)^{n_{1}k(k+1)+(k+1)^{2}\binom{n_{1}}{2}+n−1} = (xy)^{(k+1)^{2}\binom{n_{1}+1}{2}},

which, together with the earlier found sign (−1)^{n_{1}\binom{k+1}{2}}, establishes the second case in (1.8).

Case 3: n ≡ 0 (mod k + 1). Let n = (k + 1)n_{1}. Here, we also depart from (4.7). Inspection of the definition of the correction matrix C_{0}(n, k) in Lemma 11 shows that the entries in columns 0, 1, …, n − k − 1 in its last row all vanish. Therefore, if we reverse the order of rows s(k + 1), s(k + 1) + 1, …, s(k + 1) + k, for s = 0, 1, …, n_{1} − 1, then we obtain an upper triangular matrix whose entries along the diagonal are

(xy)^{k}, (xy)^{k}, …, (xy)^{k},
(xy)^{2k+1}, (xy)^{2k+1} …, (xy)^{2k+1},
(xy)^{3k+2}, (xy)^{3k+2}, …, (xy)^{3k+2},
...................................................
(xy)^{n−1}, (xy)^{n−1}, …, (xy)^{n−1}.

The product of these entries is

(xy)^{n_{1}k(k+1)+(k+1)^{2}\binom{n_{1}}{2}} = (xy)^{(k+1)^{2}\binom{n_{1}+1}{2}−n},

which, together with the sign (−1)^{n_{1}\binom{k+1}{2}} that results from the row permutation that we performed, establishes the first case in (1.8).

This completes the proof of the theorem. □

5. Proof of Theorem 4. We first use the results from Section 3 to connect the matrix of Motzkin prefix generating functions on the left-hand side of (1.9) to another matrix of Motzkin generating functions that appeared in [2].

Lemma 12. Define matrices M_{1}(n, k) and MP_{1}(n, k) by

M_{1}(n, k) := (P_{i+j+1}^{+}(k, 0))_{0≤i,j≤n−1}

and

MP_{1}(n, k) := (∑_{l≥0} P_{i+j+1}^{+}(k, l))_{0≤i,j≤n−1} .

Then

A(n) · MP_{1}(n, k) = M_{1}(n, k) + C_{1}(n, k),

where A(n) is given by (3.1) and the “correction matrix” C_{1}(n, k) := (C_{n,k,i,j}^{(1)})_{0≤i,j≤n−1} is defined via

C_{n,k,i,j}^{(1)} = \{ \begin{matrix}0, & if i ≤ n − 2, \\ (xy)^{n−1} ∑_{l≥0} P_{j+1}(0, n − k + l), & if i = n − 1. \end{matrix}

Proof. This is a direct consequence of Lemmas 8 and 9. □

We are now in the position to prove Theorem 4.

Proof of Theorem 4. We start with

MP_{1}(n, k) = (∑_{l≥0} P_{i+j+1}^{+}(k, l)) .

We multiply on the left by A(n). According to Lemma 12, we get

M_{1}(n, k) + C_{1}(n, k)

= (\{ \begin{matrix}P_{i+j+1}^{+}(k, 0), & for i ≤ n − 2 \\ P_{n+j}^{+}(k, 0) + (xy)^{n−1} ∑_{l≥0} P_{j+1}(0, n − k + l), & for i = n − 1 \end{matrix} ) .

Since det A(n) = 1 by Lemma 6, the determinant of M_{1}(n, k) + C_{1}(n, k) is the same as the determinant of MP_{1}(n, k). If we apply relation (2.1) with l = 0, then we see that we have transformed our problem into the problem of evaluation of the determinant of

(xy)^{k}M′_{1}(n, k) + C_{1}(n, k),

where

M′_{1}(n, k) := (P_{i+j+1}^{+}(0, k))_{0≤i,j≤n−1} .

The determinant of M′_{1}(n, k) is evaluated in Theorem 2. We now follow the arguments of the proof of this evaluation in [2] for a while.

Similarly to the proof of Theorem 3 in the previous section, the first step consists in the use of the decomposition (4.1) in order to convert our problem into the problem of the evaluation of the determinant of the matrix

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

In the second step, we rewrite P_{j+1}^{+}(i, k) by using (2.2). In this manner, we arrive at the problem of evaluating the determinant of

(xy)^{k} (P_{j+1}(i, k) − (xy)^{i+1}P_{j+1}(−i − 2, k))_{0≤i,j≤n−1} + C_{1}(n, k).  (5.1)

For the third step, we apply again the row operations given by (4.5) and (4.6). By the computations performed in [2, proof of Theorem 9 with t = 1] that finally lead to (5.14)–(5.16) there, these operations transform the matrix in (5.1) into the matrix

(xy)^{k}N_{1}(n, k) + C_{1}(n, k),  (5.2)

N_{n,k,h(2k+2)+b,j}^{(1)} = \{ \begin{matrix}−(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) & if 0 ≤ b ≤ k, \\ −(xy)^{(2h+1)(k+1)+b−k}P_{j+1}(0, (h + 1)(2k + 2) + b − k) \\ +(xy)^{(2h+1)(k+1)}P_{j+1}(0, (h + 1)(2k + 2) − b + k) \\ if k + 1 ≤ b ≤ 2k + 1. \end{matrix}

Closer inspection of the new matrix in (5.2) will lead to the claimed result in (1.9). This is less straightforward than in the proof of Theorem 3 though.

Case 1: n ≢ 0, 1, k (mod k + 1). Let

n = H(2k + 2) + B  (5.3)

with 0 ≤ B ≤ 2k + 1 but B ≠ 0, 1, k, k + 1, k + 2, 2k + 1. Then it is not difficult to see (see the paragraphs after (5.16) in [2]) that, if 1 ≤ B ≤ k−1, row H(2k+2) of N_{1}(n, k) consists entirely of zeroes, while, if k+2 ≤ B ≤ 2k, row H(2k+2)+k+1 consists entirely of zeroes. In particular, this implies that in our case there is a row of zeroes in the matrix in (5.2), and hence its determinant vanishes. This establishes the fourth case on the right-hand side of (1.9).

Case 2: n ≡ 0 (mod k + 1). With the notation of (5.3), we have B = 0 or B = k + 1. Similarly to Case 2 in the proof of Theorem 3 in the previous section, we subtract xy times row i for i = n − k − 1, n − k, …, n − 2 from the last row of the matrix in (5.2). Thus, we obtain the matrix

(xy)^{k}N_{1}(n, k) + C̄_{1}(n, k),  (5.4)

where C̄_{1}(n, k) is equal to the zero matrix except for the (n − 1, n − 1)-entry (the bottomright entry), which equals (xy)^{n−1}. Obviously, the determinant did not change. By using linearity in the last column, we may write the determinant of the matrix in (5.4) as

(xy)^{nk} det N_{1}(n, k) + (xy)^{(n−1)k+n−1} det (N_{1}(n, k))_{n−1}^{n−1},  (5.5)

where (N_{1}(n, k))_{n−1}^{n−1} denotes the matrix arising from N_{1}(n, k) by omitting the last row and the last column.

Since the matrix N_{1}(n, k) arose from M_{1}(n, k) by row operations that did not change the determinant, the determinant of N_{1}(n, k) equals the expression for det M_{1}(n, k) given in Theorem 2, namely

(−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}} ,

with n = n_{1}(k + 1). Similarly, the determinant of (N_{1}(n, k))_{n−1}^{n−1} equals the expression for det M_{1}(n − 1, k) given in Theorem 2, namely

(−1)^{n_{1}\binom{k+1}{2}+k}(xy)^{(k+1)^{2}\binom{n_{1}−1}{2}+(n_{1}−1)k(k+1)} \frac{y^{(k+1)n_{1}} − x^{(k+1)n_{1}}}{y^{k+1} − x^{k+1}} .

If these two expressions are substituted in (5.5), then the expression given in the first case on the right-hand side of (1.9) is obtained after minor modification.

Case 3: n ≡ 1 (mod k + 1). With the notation of (5.3), we have B = 1 or B = k + 2. Without loss of generality, we may assume k ≥ 1 (cf. Remark (1) after Theorem 4).

By reusing the arguments in Case 1, we see that, here, it is the last row of N_{1}(n, k) (namely row n − 1 = H(2k + 2) + B − 1) which consists entirely of zeroes. Since, in (5.2), the matrix C_{1}(n, k) — which is a matrix with potentially non-zero entries in the last row — is added to (xy)^{k}N_{1}(n, k), we cannot conclude that the determinant of (5.2) vanishes, but rather further work is required.

From now on, let n = (k + 1)n_{1} + 1. As in Case 2 of the proof of Theorem 3 in the previous section, we reverse the order of rows s(k + 1), s(k + 1) + 1, …, s(k + 1) + k, for s = 0, 1, …, n_{1} − 1, leaving the last row, row n − 1 = (k + 1)n_{1}, in place. Furthermore, we factor (xy)^{h(k+1)} from all the entries in rows h(k + 1), h(k + 1) + 1, …, h(k + 1) + k, h = 0, 1, …, n_{1} − 1. This yields an overall factor of

(xy)^{(k+1)^{2}\binom{n_{1}}{2}}  (5.6)

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.7)

in order to take into account the permutation of the rows that we performed. In this manner, we arrive at the matrix

N̄_{1}(n, k) + C_{1}(n, k),  (5.8)

where the matrix N̄_{1}(n, k) = (N̄_{n,k,i,j}^{(1)})_{0≤i,j≤n−1} is given by

N̄_{n,k,h(k+1)+b,j}^{(1)} = \{ \begin{matrix}P_{j+1}(0, h(k + 1) + b) − (xy)^{k−b+1}P_{j+1}(0, (h + 2)(k + 1) − b) \\ if 0 ≤ b ≤ k and h(k + 1) + b < n − 1, \\ 0, & if h(k + 1) = n − 1. \end{matrix}

(5.9)

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

In the matrix in (5.8), 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.10)

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

c(h, b, s) = \{ \begin{matrix}x^{b} + y^{b}, & if b ≠ 0, \\ 1, & if b = 0. \end{matrix}

Since the coefficient of the 0-th row in the linear combination (5.10) is 1, this does not change the value of the determinant. It should be noted that the last row, row n − 1 = n_{1}(k + 1), is not involved in the linear combination (5.10).

Now we have to redo the computation in [2] with t = 1, starting with (5.21) and leading to the result in the display in the centre of p. 161 there, however with the relaxed condition that j + 1 ≤ n = n_{1}(k + 1) + 1. (In [2] we have j + 1 ≤ n_{1}(k + 1) at that point.) Taking also into account our assumption that k ≥ 1, the final result is that the (0, j)-entry in the new matrix is given by

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

It is important to observe that, again because P_{a}(0, b) = 0 for a < b, this expression vanishes for j < n_{1}(k + 1) − 1, so that only the right-most two entries in row 0 are non-zero.

In addition to the above modifications of the 0-th row, in analogy to similar operations in Case 2 in the proof of Theorem 3 and in Case 2 of the current proof, we also replace the last row, row n − 1 = n_{1}(k + 1), by

(row n − 1) − (xy)^{n−1} ∑_{i=n−k}^{n−2} (row i).  (5.11)

When doing this operation it is important to observe that all entries in column j with j ≤ n − k − 1 are actually zero, that the entries N̄_{n,k,i,j}^{(1)} given by (5.9) for i ≤ n − 2 and j ≥ n − k are given by P_{j+1}(0, i), except for the (n − 2, n − 1)-entry, which is equal to P_{n}(0, n − 2) − (xy)P_{n}(0, n). Again, this operation does not change the determinant.

Altogether, the new matrix obtained is M̃_{1}(n, k) = (M̃_{n,k,i,j}^{(1)})_{0≤i,j≤n−1}, where

M̃_{n,k,h(k+1)+b,j}^{(1)} = \{ \begin{matrix}(−1)^{n_{1}(k+1)+1} ∑_{s=0}^{n_{1}} x^{s(k+1)}y^{(n_{1}−s)(k+1)} \\ ×(P_{j+1}(0, n_{1}(k + 1)) − (x + y)P_{j+1}(0, n_{1}(k + 1) + 1)), \\ if h = b = 0, \\ P_{j+1}(0, h(k + 1) + b) − (xy)^{k−b+1}P_{j+1}(0, (h + 2)(k + 1) − b), \\ if 0 ≤ b ≤ k and 0 < h(k + 1) + b < n − 1, \\ (xy)^{n−1}(P_{j+1}(0, n_{1}(k + 1)) + (1 + xy)P_{j+1}(0, n_{1}(k + 1) + 1)), \\ if h(k + 1) = n − 1. \end{matrix}

The determinant of this matrix is the same as that of the matrix in (5.8).

It is helpful to display the schematic form of this matrix:

M̃_{1}(n, k) = ( \begin{matrix}0 & … & 0 & a & b \\ & M & & ⋮ & ⋮ \\ 0 & … & 0 & c & d \end{matrix} ) ,  (5.12)

where

a = (−1)^{n_{1}(k+1)+1} \frac{x^{(k+1)(n_{1}+1)} − y^{(k+1)(n_{1}+1)}}{x^{k+1} − y^{k+1}} ,
b = (−1)^{n_{1}(k+1)+1} \frac{x^{(k+1)(n_{1}+1)} − y^{(k+1)(n_{1}+1)}}{x^{k+1} − y^{k+1}} ((n_{1}(k + 1) + 1)(x + y) − (x + y)),
c = (xy)^{n−1},
d = (xy)^{n−1}(n_{1}(k + 1) + 1)(x + y) + (1 + xy),  (5.13)

and M = (M_{i,j})_{1≤i≤n_{1}(k+1)−1, 0≤j≤n_{1}(k+1)−2} with

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

for 0 ≤ b ≤ k.

In order to evaluate the determinant of M̃_{1}(n, k), we do a Laplace expansion simultaneously with respect to the top and the bottom row. Thereby, we obtain

det M̃_{1}(n, k) = (−1)^{n} det ( \begin{matrix}a & b \\ c & d \end{matrix} ) · det M.  (5.14)

Straightforward calculation shows that

det ( \begin{matrix}a & b \\ c & d \end{matrix} ) = (−1)^{n}(xy)^{n−1} \frac{x^{(k+1)(n_{1}+1)} − y^{(k+1)(n_{1}+1)}}{x^{k+1} − y^{k+1}} (1 + x)(1 + y),

while M is an upper triangular matrix so that its determinant is equal to the product of its diagonal entries, all of which are 1. If everything is put together with the earlier obtained factors (5.6) and (5.7), then we arrive at the expression given in the second case on the right-hand side of (1.9).

Case 4: n ≡ k (mod k + 1). With the notation of (5.3), we have B = k or B = 2k + 1. Again, without loss of generality, we may assume k ≥ 1 (cf. Remark (1) after Theorem 4).

Let n = n_{1}(k + 1) + k. We do the same row operations as in Case 3, except the one in (5.11). This produces a matrix of the form

( \begin{matrix}0 & … & 0 & a & b & … \\ & M & & & ∗ \\ & 0 & & & & D \\ 0 & … & 0 & c & d & … \end{matrix} ) ,  (5.15)

where a, b, c, d, M are as in (5.12) and (5.13) (with the meaning of n in the definitions of c and d being the current one), and D is a (k − 1) × (k − 1) “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.) The entries a and c are located in column n_{1}(k + 1) − 1, so that the submatrix M is located strictly to the left of this column while the submatrix D is located strictly to the right of column n_{1}(k + 1) (the indexing of rows and columns starting at 0 as usual). To the left of D — in the rows covered by D — there are only zeroes.

By performing a Laplace expansion simultaneously with respect to the top and the bottom row, one sees that the determinant of the above matrix equals

(−1)^{n} det ( \begin{matrix}a & b \\ c & d \end{matrix} ) · det M · det D.  (5.16)

Comparison with (5.14) shows that the determinant of the matrix in (5.15) differs from det M̃(n, k) (with M̃(n, k) given in (5.12)) by a factor of

(−1)^{k−1}(xy)^{k−1} det D.

Here, the factor of (−1)^{k−1} comes from the factor (−1)^{n} in (5.16), taking into account that our current n is by k − 1 larger than the n in Case 3, and the factor (xy)^{k−1} comes from the factor (xy)^{n−1} in the definitions of c and d, again taking into account that the n here differs from the one in Case 3.

Since the entries of D were not affected by the row operations from Case 3, they still equal the corresponding entries in (xy)^{k}N_{1}(n, k) (cf. (5.2)). Consequently — as we already stated earlier — D is “reflected upper triangular”, with entries (xy)^{n} along the main antidiagonal. It follows that det D equals (−1)^{\binom{k−1}{2}}(xy)^{n(k−1)}. Hence, the determinant of the matrix in (5.15) differs from det M̃(n, k) by a factor of

(−1)^{k−1+\binom{k−1}{2}}(xy)^{(n+1)(k−1)} = (−1)^{\binom{k}{2}}(xy)^{(n_{1}+1)(k^{2}−1)}.

This is indeed exactly the factor by which the third expression on the right-hand side of (1.9) differs from the second expression.

This completes the proof of the theorem. □

6. Specialisations. In this section we list specialisations of Theorems 3 and 4. The special values of x and y that we choose are those that we discussed at the end of Section 2. In all the results that we list in this section, the convention of Remark (1) after the statements of Theorems 3 and 4 applies (in a slightly modified form): for k = 0, 1, it is the first applicable case in the case distinctions on the right-hand sides that produces the correct result.

We begin by setting x = −y = \sqrt{−1} in Theorem 3. Using (2.13), we obtain the following result.

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

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

(6.1)

A noteworthy special case is the one for k = 0,

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

In other words, this gives the “Hankel transform” of the sequence (\binom{n}{⌊n/2⌋})_{n≥0} of central

and “almost central” binomial coefficient. According to [6, Sequence A001405], this Hankel determinant evaluation had been observed by Philippe Deléham in 2007.

On the other hand, for k = 1 we get

det_{0≤i,j≤n−1} (\binom{i + j + 1}{⌊\frac{1}{2}(i + j + 2)⌋}) = det_{0≤i,j≤n−1} (\binom{i + j + 1}{⌊\frac{1}{2}(i + j + 1)⌋}) = (−1)^{⌊n/2⌋}, (6.3)

thus obtaining the “Hankel transform” of the shifted sequence (\binom{n}{⌊n/2⌋})_{n≥1} of central and

“almost central” binomial coefficients. We add that the choices of k = 2 and k = 3 provide Hankel determinant evaluations for the sequences A026010 and A026023 in [6].

Next we set x = −y = \sqrt{−1} in Theorem 4, upon using (2.13) again. This leads to the following determinant identity.

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

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

= \{ \begin{matrix}2n_{1} + 1, & if n = (k + 1)n_{1} and k ≡ 1 (mod 4), \\ 1, & if n = (k + 1)n_{1} and k ≡ 3 (mod 4), \\ (−1)^{n_{1}/2}, & if n = (k + 1)n_{1}, and k and n_{1} are even, \\ (−1)^{(k+n_{1}−1)/2}, & if n = (k + 1)n_{1}, k is even, and n_{1} is odd, \\ 2n_{1} + 2, & if n = (k + 1)n_{1} + 1, and k is odd, \\ 2(−1)^{n_{1}/2}, & if n = (k + 1)n_{1} + 1, and k and n_{1} are even, \\ (−1)^{(k−1)/2}(2n_{1} + 2), & if n = (k + 1)n_{1} + k, and k is odd, \\ 2(−1)^{(k+n_{1})/2}, & if n = (k + 1)n_{1} + k, and k and n_{1} are even, \\ 0, & otherwise. \end{matrix}

(6.4)

For k = 0, we obtain (6.3) again, while for k = 1 we get

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

which is the “Hankel transform” of the doubly shifted sequence (\binom{n}{⌊n/2⌋})_{n≥2} of central and

“almost central” binomial coefficients. Clearly, for k = 2 and k = 3, Corollary 14 provides Hankel determinant evaluations for the sequences A026010 and A026023, respectively, with the first element of each sequence omitted.

We continue setting x = y^{−1} = ω in Theorem 3. We recall that this specialisation in P_{n}^{+}(k, l) corresponds to weighting each path by 1 — which amounts to ordinary counting of paths — so that P_{n}^{+}(k, l)_{x=y^{−1}=ω} is simply equal to the number of all three-step paths from (0, k) to (n, l) that never run below the x-axis. Consequently,

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

equals the number of three-step paths starting at (0, k), proceeding for n steps, and never running below the x-axis. For k = 0, these are the Motzkin prefix numbers MP_{n} mentioned in the introduction. For generic k, these numbers can be considered as generalised Motzkin prefix numbers, for which (2.14) provides an explicit formula. We denote the number in (6.6) by MP_{n}(k).

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

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

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

Clearly, the case k = 0 provides the proof of (1.7). Further noteworthy special cases are the one for k = 1,

det_{0≤i,j≤n−1} ( MP_{i+j}(1)) = (−1)^{⌊n/2⌋},  (6.8)

providing the “Hankel transform” of Sequence A025566 in [6], and the one for k = 2,

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

providing the “Hankel transform” of Sequence A005774 in [6].

Specialisation of x = y^{−1} = ω in Theorem 4 yields further Hankel determinant evaluations for (generalised) Motzkin prefix numbers.

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

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

(6.10)

The special cases k = 0, 1, 2 are explicitly

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

det_{0≤i,j≤n−1} ( MP_{i+j+1}(1)) = \{ \begin{matrix}(−1)^{⌊n/6⌋}, & if n ≡ 0, 4 (mod 3), \\ 3(−1)^{⌊n/6⌋}, & if n ≡ 1, 3 (mod 3), \\ 2(−1)^{⌊n/6⌋}, & if n ≡ 2 (mod 3), \\ 0, & if n ≡ 5 (mod 3), \end{matrix}  (6.12)

det_{0≤i,j≤n−1} ( MP_{i+j+1}(2)) = \{ \begin{matrix}1, & if n ≡ 0 (mod 3), \\ 3⌈n/3⌉, & if n ≡ 1 (mod 3), \\ −3⌈n/3⌉, & if n ≡ 2 (mod 3), \end{matrix}  (6.13)

providing further Hankel determinant evaluations for the sequences A005773, A025566, and A005774 in [6].

Next we turn our attention to the specialisation x = y = 1. Use of (2.15) in Theorem 3 yields the following result.

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

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

For k = 0, Equation (6.14) says that the “Hankel transform” of the sequence (\binom{2n+1}{n+1})_{n≥0} (which is [6, Sequence A001700]) is the all-1 sequence. This is a well-known

result, and it is also covered by [2, Theorem 21].

For k = 1, Equation (6.14) provides the “Hankel transform” of the sequence (\binom{2n+2}{n})_{n≥0} (which is [6, Sequence A001791] up to a shift). Again, this is a known result, see e.g. [2, Cor. 20 with k = 1].

On the other hand, specialising x = y = 1 in Theorem 4, we arrive at the following Hankel determinant evaluation.

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

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

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

(6.15)

Similarly to before, for k = 1 this recovers [2, Cor. 23 with k = 1], while for k = 0 it proves Conjecture 24 in [2] for k = 0 and k = 1.

Finally, we set x = y = −1 in Theorem 3. Using (2.16), we obtain a determinant evaluation which can be considered to be in a row with [2, Cors. 12, 15, 13, 18, 16].

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

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

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

Here, the (0, 0)-entry of the matrix on the left-hand side is zero by definition.

Proof. Since

\frac{2k + 2}{i + j + k + 1}\binom{2i + 2j − 1}{i + j + k} = \frac{k + 1}{i + j}\binom{2i + 2j}{i + j + k + 1},

the matrix on the left-hand side of (6.16), of which the determinant is taken, is the n × n Hankel matrix corresponding to the sequence in (2.16), up to the sign in (2.16), and up to the convention of how to interpret the term for n = 0 in (2.16). Applying the specialisation x = y = −1 in Theorem 3 and using (2.16), we are led to the determinant evaluation

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

(6.17)

where the (0, 0)-entry in the matrix on the left-hand side has to be taken as 1. Let M = (M_{i,j})_{0≤i,j≤n−1} be that matrix. We write the 0-th row of the matrix as

(0, M_{0,1}, M_{0,2}, …, M_{0,n−1}) + (1, 0, …, 0).

Subsequently, we use the linearity of the determinant in this row to decompose the determinant into the sum

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

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

where the (0, 0)-entry in the first matrix is zero by definition. The first determinant in (6.18) is thus the determinant in (6.16), up to a sign of (−1)^{nk}. Because of (6.17), we know the total value of (6.18), while the second determinant in (6.18) has been evaluated in [2, Corollary 18].^{1} Thus, this sets up an equation for the determinant in (6.16), which we just have to solve. □

Specialising x = y = 1 in Theorem 4 and using (2.15) again, we recover Corollary 15 in [2].

Acknowledgements. The authors thank an anonymous referee for an extremely careful reading of the original manuscript.

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. J. Cigler and C. Krattenthaler, Some determinants of path generating functions, Adv. Appl. Math. 46 (2011), 144–174.

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

4. C. Krattenthaler, Determinant identities and a generalization of the number of totally symmetric self-complementary plane partitions, Electron. J. Combin. 4(1) (1997), Article #R27, 62 pp.

1Unfortunately, the determinant evaluation in Corollary 18 of [2] is seriously mistyped: on the righthand side, every occurrence of k must be replaced by k−1. Alternatively, we might replace every occurrence of k on the left-hand side by k + 1 (and, in the sentence above Corollary 18 in [2] disregard “and replacing k by k − 1”.) The latter leads in fact to the form of this evaluation that we need here.

5. L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

6. N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

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

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

Fakultät für Mathematik, Universität Wien, Oskar-Norgenstern-Platz 1, A-1090 Vienna,

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

Department of Mathematics, Ferdowsi University Of Mashhad, Mashhad, Iran