Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries

Taras Goy Faculty of Mathematics and Computer Science Vasyl Stefanyk Carpathian National University Ivano-Frankivsk, 76018 Ukraine

                 taras.goy@pnu.edu.ua

Mark Shattuck Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

                   mshattuc@utk.edu

Abstract

We find formulas for the determinants of several Toeplitz-Hessenberg matrices whose nonzero entries are Fuss-Catalan numbers. By Trudi’s formula, one obtains equivalent multi-sum identities indexed over the set of partitions of a fixed integer involving the product of Fuss-Catalan numbers and multinomial coefficients. We make use of generating functions to establish our results and, as a consequence, several entries from the OEIS are afforded new combinatorial interpretations as determinants of certain Toeplitz-Hessenberg matrices. Finally, we provide counting arguments for several of our determinant identities drawing upon combinatorial interpretations of various specific cases of the Fuss-Catalan numbers in terms of Dyck paths, ternary trees, and non-crossing partitions.

1 Introduction

The Fuss-Catalan numbers A_{n}(p, r) were introduced in [23] and are given explicitly by

A_{n}(p, r) = \frac{r}{pn + r}\binom{pn + r}{n} = \frac{r}{n!} ∏_{i=1}^{n−1}(pn + r − i), n ≥ 0.

The A_{n}(p, r) are given recursively by

A_{n}(p, r) = A_{n}(p, r − 1) + A_{n−1}(p, p + r − 1), n ≥ 1,

and represent the coefficient of x^{n} in M^{r}, where M = M(x) satisfies xM^{p} = M − 1. Note that the A_{n}(p, r) reduce to the binomial coefficients of order r when p = 0 and to Pascal’s triangle, read along diagonals, when p = 1. When p = 2 and r = 1, the Fuss-Catalan numbers reduce to the classical Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n}, which occur throughout enumerative combinatorics, see [27]. The A_{n}(p, r) are referred to as the Raney numbers by some authors, with the Fuss-Catalan descriptor being reserved for the special case when p = 2 and r = 1. Here, we will assume that p and r denote fixed non-negative integers, not both zero.

The A_{n}(p, r) where p ≥ 1 answer the question of finding the number of possible sequences for completing a computer stack of instructions in exactly pn + r steps (and not fewer) if at each step either a single instruction is processed or p−1 new instructions arrive, where at the beginning, there are r instructions outstanding. See also [13, Chapter 7] for an equivalent formulation (and combinatorial proof of the solution) of the problem in terms of lattice paths. When p = k + 1 and r = 1, the A_{n}(p, r) enumerate the non-crossing partitions of size kn in which the number of elements in each block is divisible by k, see [7, Lemma 4.1]. See also, for example, the following references for other appearances of the Fuss-Catalan numbers in algebra [2, 14], probability [6, 19], and combinatorics [1, 3, 16, 21, 22, 24].

In [9], it was shown

D_{+}(C_{1}, C_{2}, …, C_{n}) = (−1)^{n−1}C_{n−1}, n ≥ 1,

and

D_{−}(C_{1}, C_{2}, …, C_{n}) = (2n − 1)C_{n−1}, n ≥ 1,

by both algebraic and combinatorial arguments, where D_{±}(a_{1}, …, a_{n}) denotes the determinant of a Toeplitz-Hessenberg matrix of the form (1) below in which a_{0} = ±1. Here, we extend these and other results from [9] by considering matrices with Fuss-Catalan number entries and special cases thereof (especially p = 2 or 3). This yields new connections between A_{n}(p, r) and several sequences occurring in [25]. By contrast, Toeplitz-Hessenberg matrices whose determinants work out to the Fuss-Catalan numbers have previously been considered in [8]. Finally, we note that comparable formulas have been found for the determinants of Toeplitz-Hessenberg matrices whose nonzero entries are derived from other well-known sequences such as, inter alia, the Motzkin [10], Leonardo [12], Schröder, and Fine [11] numbers.

The organization of this paper is as follows. In the second section, we establish a general formula for D_{+}(A_{1}(p, r), …, A_{n}(p, r)), and note some particular cases corresponding to entries in [25]. We also establish several further determinant formulas involving A_{n}(p, r) for specific p and r. As a consequence of our results, we obtain new combinatorial interpretations in terms of Toeplitz-Hessenberg matrices for several sequences in [25]. By Trudi’s formula, these determinant formulas may be expressed as multi-sum identities involving sums of products of Fuss-Catalan numbers and multinomial coefficients. In the third section, we provide combinatorial proofs of several of our formulas using the definition of the determinant as a signed sum over the set of permutations of [n] = {1, …, n}.

Our combinatorial arguments entail finding a direct enumeration of a discrete structure counted by the resulting positive determinant sum when a_{0} = −1 and a sign-changing involution on a related (signed) structure whose sum of signs is given by the determinant when a_{0} = 1. In our combinatorial proofs, we draw upon interpretations of various specific cases of A_{n}(p, r) in terms of ternary trees, Dyck paths, and non-crossing partitions. A notable bijection is used in our argument of the formula for D_{−}(A_{0}(3, 1), …, A_{n−1}(3, 1)), see (19) below, wherein a one-to-one correspondence is found between the set of Dyck paths of semi-length 2n with all descents even and no valleys of height one and a subset of the non-crossing partitions of [2n] with all even block sizes whose first block satisfies a certain restriction with regard to its run lengths. On the other hand, our proofs of the formulas for D_{+}(K_{−1}, …, K_{n−2}) and D_{+}(K_{0}, …, K_{n−1}), where K_{n} = C_{n+2} − C_{n+1}, require defining a somewhat intricate sign-changing involution in each case on sets of vectors of Dyck paths whose combined semi-length satisfies a certain restriction. It will be seen that the survivors of the involution in both instances are enumerated by partial sums of Catalan numbers starting from either one or zero, respectively (see entry \underline{A014137} in [25]).

2 Fuss-Catalan determinants

Consider an n × n matrix A_{n} for some n ≥ 1 of the form

A_{n} := A_{n}(a_{0}; a_{1}, …, a_{n}) = ( \begin{matrix}a_{1} & a_{0} & 0 & ⋯ & 0 & 0 \\ a_{2} & a_{1} & a_{0} & ⋯ & 0 & 0 \\ a_{3} & a_{2} & a_{1} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ a_{n−1} & a_{n−2} & a_{n−3} & ⋯ & a_{1} & a_{0} \\ a_{n} & a_{n−1} & a_{n−2} & ⋯ & a_{2} & a_{1} \end{matrix} ),  (1)

where a_{0} ≠ 0. Such a matrix A_{n} is described as being Toeplitz-Hessenberg (see, e.g., [20]).

The following expression for det(A_{n}) in terms of the a_{i} is known as Trudi’s formula [17, Theorem 1], the a_{0} = 1 case of which has been attributed to Brioschi [20].

Lemma 1. If n ≥ 1, then

det(A_{n}) = ∑_{α̃=n}(−a_{0})^{n−|α|}m_{n}(α)a_{1}^{α_{1}}a_{2}^{α_{2}} ⋯ a_{n}^{α_{n}},  (2)

where the sum is over all n-tuples α = (α_{1}, …, α_{n}) of non-negative integers such that α̃ = α_{1} + 2α_{2} + ⋯ + nα_{n} = n, with |α| = α_{1} + ⋯ + α_{n} and m_{n}(α) = \frac{|α|!}{α_{1}!···α_{n}!}.

Note that the sum in (2) may be regarded as being over the set of all partitions of the integer n.

Consider now the generating functions

f(x) = ∑_{n≥1} det(A_{n})x^{n} and g(x) = ∑_{i≥1} a_{i}x^{i},

where A_{n} is of the form in (1). Using (2), one can establish the following relation (see, e.g., [12]) between f(x) and g(x), which will be made frequent use of.

Lemma 2. We have

f(x) = \frac{−\frac{1}{a_{0}} g(−a_{0}x)}{1 + \frac{1}{a_{0}} g(−a_{0}x)}.  (3)

To simplify notation, we denote the specific cases of det(A_{n}(a_{0}; a_{1}, …, a_{n})) when a_{0} = ±1 by D_{±}(a_{1}, …, a_{n}). We have the following general determinant formula involving Fuss-Catalan numbers, where the binomial coefficient \binom{α}{k} is taken to be \frac{α(α−1)···(α−k+1)}{k!} for any number α and non-negative integer k.

Theorem 3. Let p, r ≥ 0 be fixed integers. Then we have

D_{+}(A_{1}(p, r), A_{2}(p, r), …, A_{n}(p, r)) = (−1)^{n−1} \frac{r}{n}\binom{pn − r − 1}{n − 1},  n ≥ 1.  (4)

Proof. Let u(x) = ∑_{n≥1} A_{n}(p, r)x^{n} and v(x) = ∑_{n≥1}(−1)^{n−1} \frac{r}{n} \binom{pn−r−1}{n−1}x^{n}. By Lemma 2, to establish (4), it suffices to show

\frac{−u(−x)}{1 + u(−x)} = v(x), i.e., u(x) + v(−x) = −u(x)v(−x),

upon replacing x with −x. Consider equating coefficients of x^{n} for n ≥ 1 on both sides of the last equation, taking into account a convolution on the right-hand side. Then (4) is seen to be equivalent to the following binomial identity for all n ≥ 1:

\frac{r}{n}\binom{pn + r − 1}{n − 1} − \frac{r}{n}\binom{pn − r − 1}{n − 1} = ∑_{i=1}^{n−1} \frac{r^{2}}{i(n − i)}\binom{pi + r − 1}{i − 1}\binom{pn − pi − r − 1}{n − i − 1}. (5)

To show (5), we first recall the general convolution identity for all integers n, t ≥ 0 and real numbers r and s from [13, p. 202, Eq. (5.63)]:

∑_{k=0}^{n} \frac{rs}{(tk + r)(tn − tk + s)}\binom{tk + r}{k}\binom{tn − tk + s}{n − k} = \frac{r + s}{tn + r + s}\binom{tn + r + s}{n},

the s = −r case of which corresponds to

∑_{k=0}^{n} \frac{r^{2}}{(tk + r)(tn − tk − r)}\binom{tk + r}{k}\binom{tn − tk − r}{n − k} = 0.  (6)

Now consider separating the k = 0 and k = n terms in (6) and then applying the fact \binom{α}{k} = \frac{α}{k} \binom{α−1}{k−1} for any real number α and positive integer k. This yields

∑_{k=1}^{n−1} \frac{r^{2}}{k(n − k)}\binom{tk + r − 1}{k − 1}\binom{tn − tk − r − 1}{n − k − 1} = \frac{r}{tn + r}\binom{tn + r}{n} − \frac{r}{tn − r}\binom{tn − r}{n}

= \frac{r}{n}\binom{tn + r − 1}{n − 1} − \frac{r}{n}\binom{tn − r − 1}{n − 1},

which is equivalent to (5) and completes the proof of (4).

The following special cases of Theorem 3 correspond to entries in [25].

Corollary 4. We have

(−1)^{n−1}D_{+}(A_{1}(2, 3), A_{2}(2, 3), …, A_{n}(2, 3)) = C_{n−1} − C_{n−2} = \underline{A000245}(n − 2), n ≥ 2, (7)

(−1)^{n−1}D_{+}(A_{1}(2, 4), A_{2}(2, 4), …, A_{n}(2, 4)) = C_{n−1} − 2C_{n−2} = −\underline{A115143}(n), n ≥ 3, (8)
(−1)^{n−1}D_{+}(A_{1}(3, 1), A_{2}(3, 1), …, A_{n}(3, 1)) = \frac{1}{n}\binom{3n − 2}{n − 1} = \underline{A006013}(n − 1), n ≥ 1, (9)
(−1)^{n−1}D_{+}(A_{1}(3, 2), A_{2}(3, 2), …, A_{n}(3, 2)) = \frac{2}{n}\binom{3n − 3}{n − 1} = \underline{A007226}(n − 1), n ≥ 1.(10)

Remark 5. Using the fact \binom{−n}{k} = (−1)^{k}\binom{n+k−1}{k}, we have that the p = 0 case of (4) is equivalent to

D_{+} (\binom{r}{1}, \binom{r}{2}, …, \binom{r}{n}) = \binom{n + r − 1}{n},  n, r ≥ 1.  (11)

Let K_{n} := A_{n}(2, 3) = C_{n+2} − C_{n+1} for n ≥ −1 and let

C := C(x) = \frac{1 − \sqrt{1 − 4x}}{2x}

denote the Catalan number generating function. We have the following further determinant formulas involving C_{n} and K_{n}.

Theorem 6. If n ≥ 1, then

D_{−}(C_{1}, C_{3}, …, C_{2n−1}) = \underline{A066357}(n),  (12)
D_{−}(C_{2}, C_{3}, …, C_{n+1}) = p_{n},  (13)
D_{+}(K_{−1}, K_{0}, …, K_{n−2}) = (−1)^{n−1} ∑_{i=1}^{n−1} C_{i},  (14)

D_{+}(K_{0}, K_{1}, …, K_{n−1}) = (−1)^{n−1} ∑_{i=0}^{n−1} C_{i} = (−1)^{n−1}\underline{A014137}(n − 1),  (15)
D_{−}(K_{0}, K_{1}, …, K_{n−1}) = \underline{A026674}(n),  (16)

where p_{n} is given by \frac{1}{2−C^{2}} = 1 + ∑_{n≥1} p_{n}x^{n}.

Proof. To show (12), first note

∑_{n≥1} C_{2n−1}x^{2n−1} = \frac{C(x) − C(−x)}{2} = \frac{2 − \sqrt{1 − 4x} − \sqrt{1 + 4x}}{4x},

and hence

∑_{n≥1} C_{2n−1}x^{n} = \frac{2 − \sqrt{1 − 4x^{1/2}} − \sqrt{1 + 4x^{1/2}}}{4} .

By the a_{0} = −1 case of (3), we then have

∑_{n≥1} D_{−}(C_{1}, …, C_{2n−1})x^{n} = \frac{2 − \sqrt{1 − 4x^{1/2}} − \sqrt{1 + 4x^{1/2}}}{2 + \sqrt{1 − 4x^{1/2}} + \sqrt{1 + 4x^{1/2}}} .

Recall

∑_{n≥1} \underline{A066357}(n)x^{n} = xC^{2}(x^{1/2})C^{2}(−x^{1/2}) = \frac{1 − 2x^{1/2} − \sqrt{1 − 4x^{1/2}}}{1 + 2x^{1/2} + \sqrt{1 + 4x^{1/2}}} ,

where the second equality follows from the definition of C(y) and the fact yC^{2}(y) = C(y)−1. Thus, formula (12) holds if and only if the generating functions for n ≥ 1 corresponding to the two sides are equal, i.e.,

(2 − \sqrt{1 − 4x^{1/2}} − \sqrt{1 + 4x^{1/2}})(1 + 2x^{1/2} + \sqrt{1 + 4x^{1/2}})
= (2 + \sqrt{1 − 4x^{1/2}} + \sqrt{1 + 4x^{1/2}})(1 − 2x^{1/2} − \sqrt{1 − 4x^{1/2}}),

which may subsequently be verified. For (13), note

∑_{n≥1} C_{n+1}x^{n} = ∑_{n≥2} C_{n}x^{n−1} = \frac{1}{x}(C − 1 − x),

and hence

∑_{n≥1} D_{−}(C_{2}, …, C_{n+1})x^{n} = \frac{C − 1 − x}{2x + 1 − C} = \frac{x}{2x + 1 − C} − 1 = \frac{1}{2 − C^{2}} − 1,

as desired.

To show (14), first note

∑_{n≥1} K_{n−2}x^{n} = ∑_{n≥1}(C_{n} − C_{n−1})x^{n} = (1 − x)C − 1,

and thus, by the a_{0} = 1 case of (3), we have

∑_{n≥1} D_{+}(K_{−1}, …, K_{n−2})x^{n} = \frac{1 − (1 + x)D}{1 − (1 − (1 + x)D)} = \frac{1}{(1 + x)D} − 1,

where D = C(−x). On the other hand,

∑_{n≥1} ((−1)^{n−1} ∑_{i=1}^{n−1} C_{i}) x^{n} = ∑_{i≥1} C_{i} ∑_{n≥i+1}(−1)^{n−1}x^{n} = \frac{x}{1 + x}(D − 1).

Using the fact xD^{2} = 1 − D, one can show the equality of generating functions \frac{1}{(1+x)D} − 1 = \frac{x}{1+x}(D − 1), which implies (14). A similar proof applies to (15). Finally, for (16), note

∑_{n≥1} K_{n−1}x^{n} = ∑_{n≥0}(C_{n+1} − C_{n})x^{n} = \frac{(1 − x)C − 1}{x} = xC^{3},

where the last equality follows from two applications of xC^{2} = C − 1, and hence

∑_{n≥1} D_{−}(K_{0}, …, K_{n−1})x^{n} = \frac{xC^{3}}{1 − xC^{3}} = ∑_{n≥1} \underline{A026674}(n)x^{n},

as desired.

Remark 7. Note that \underline{A066357}(n) enumerates, among other things, the set of lattice paths from (0, 0) to (2n, 2n) using (1, 0) and (0, 1) steps that lie on or above the line y = x and avoid points (m, m) where m is odd. Formula (12) above is seen to provide a new combinatorial interpretation for \underline{A066357} in terms of weighted compositions of n (see preliminary discussion in third section). A comparable remark applies to the other sequences from [25] that arise here as determinants of matrices with Fuss-Catalan entries.

One may obtain an explicit formula for the sequence p_{n} as follows, which apparently does not occur in [25]. Upon writing

∑_{n≥1} p_{n}x^{n} = \frac{1}{2 − C^{2}} − 1 = \frac{C^{2} − 1}{1 − (C^{2} − 1)} = ∑_{i≥1}(C^{2} − 1)^{i},

we have

p_{n} = [x^{n}] ∑_{i≥1}(C^{2} − 1)^{i} = ∑_{i=1}^{n} ∑_{k=1}^{i}(−1)^{i−k}\binom{i}{k}[x^{n}]C^{2k}

= ∑_{i=1}^{n} ∑_{k=1}^{i}(−1)^{i−k}\binom{i}{k}\frac{2k(2n + 2k − 1)!}{n!(n + 2k)!},

where in the third equality we have made use of the well-known fact [x^{n}]C^{j} = \frac{j(2n+j−1)!}{n!(n+j)!} for n, j ≥ 1; see, e.g., [29, p. 54, Eq. (2.5.16)]. The last expression may be rewritten to give

p_{n} = ∑_{k=1}^{n} ∑_{i=0}^{n−k}(−1)^{i} \frac{k}{n + k} \binom{2n + 2k}{n}\binom{i + k}{k},  n ≥ 1.  (17)

Let

H_{n} := A_{n}(3, 1) = \frac{1}{3n + 1}\binom{3n + 1}{n} = \underline{A001764}(n)

and

J_{n} := A_{n}(3, 2) = \frac{2}{3n + 2}\binom{3n + 2}{n} = \underline{A006013}(n)

for n ≥ 0. In addition to those given above in Corollary 4, we have the following determinant formulas involving H_{n} and J_{n}.

Theorem 8. Let n ≥ 1, unless stated otherwise. Then we have

D_{+}(H_{0}, H_{1}, …, H_{n−1}) = (−1)^{n−1}\underline{A023053}(n − 1),  (18)
D_{−}(H_{0}, H_{1}, …, H_{n−1}) = \underline{A098746}(n),  (19)
D_{−}(H_{1}, H_{2}, …, H_{n}) = \underline{A047099}(n),  (20)
D_{+}(H_{2}, H_{3}, …, H_{n+1}) = \frac{2(−1)^{n−1}}{n} \binom{3n − 3}{n − 1} = (−1)^{n−1}\underline{A007226}(n − 1), n ≥ 2, (21)
D_{+}(J_{0}, J_{1}, …, J_{n−1}) = (−1)^{n−1}\underline{A121545}(n),  (22)
D_{−}(J_{0}, J_{1}, …, J_{n−1}) = H_{n}.  (23)

Proof. We provide proofs of (21) and (23), the others being similar. For (21), first note

∑_{n≥1} H_{n+1}x^{n} = \frac{1}{x}(H − 1 − x),

where the power series ∑_{n≥0} H_{n}x^{n} is denoted by H = H(x). Recall that H satisfies H = 1 + xH^{3}. By Lemma 2, we get

∑_{n≥1} D_{+}(H_{2}, …, H_{n+1})x^{n} = \frac{\frac{1}{x}(H(−x) − 1 + x)}{1 − \frac{1}{x}(H(−x) − 1 + x)} = \frac{H(−x) − 1 + x}{1 − H(−x)},

whence

∑_{n≥2} D_{+}(H_{2}, …, H_{n+1})x^{n} = \frac{x}{1 − H(−x)} − 1 − 3x.

On the other hand, from the known generating function formula for \underline{A007226}(n), we have

∑_{n≥2}(−1)^{n−1}\underline{A007226}(n − 1)x^{n} = x (∑_{n≥0} \underline{A007226}(n)(−x)^{n} − 2)

= x (\frac{1 − H^{−2}(−x)}{−x} − 2) = H^{−2}(−x) − 1 − 2x.

So to complete the proof of (21), we must show \frac{x}{1−H(−x)} − x = H^{−2}(−x), i.e., H^{−2}(x) + \frac{x}{1−H(x)} = x, upon replacing x with −x. The last equality is equivalent to 1 − H + xH^{2} = xH^{2}(1 − H), which holds since xH^{3} = H − 1. For (23), first note ∑_{n≥1} J_{n−1}x^{n} = xH^{2}, by the known generating function formula for J_{n}. By (3), we then get

D_{−}(J_{0}, …, J_{n−1})x^{n} = \frac{xH^{2}}{1 − xH^{2}} .

Since ∑_{n≥1} H_{n}x^{n} = H − 1, equality (23) is equivalent xH^{2} = (H − 1)(1 − xH^{2}), which follows from the relation for H.

By formula (2) and Theorems 3, 6, and 8, we obtain the following multi-sum identities involving the Fuss-Catalan numbers.

Corollary 9. Let n ≥ 1, unless stated otherwise. Then we have

∑_{α̃=n}(−1)^{|α|−1}m_{n}(α)A_{1}(p, r)^{α_{1}}A_{2}(p, r)^{α_{2}} ⋯ A_{n}(p, r)^{α_{n}} = \frac{r}{n}\binom{pn − r − 1}{n − 1},
∑_{α̃=n} m_{n}(α)C_{1}^{α_{1}}C_{3}^{α_{2}} ⋯ C_{2n−1}^{α_{n}} = \underline{A066357}(n),
∑_{α̃=n} m_{n}(α)C_{2}^{α_{1}}C_{3}^{α_{2}} ⋯ C_{n+1}^{α_{n}} = p_{n},

∑_{α̃=n}(−1)^{|α|−1}m_{n}(α)K_{−1}^{α_{1}}K_{0}^{α_{2}} ⋯ K_{n−2}^{α_{n}} = ∑_{i=1}^{n−1} C_{i},

∑_{α̃=n}(−1)^{|α|−1}m_{n}(α)K_{0}^{α_{1}}K_{1}^{α_{2}} ⋯ K_{n−1}^{α_{n}} = ∑_{i=0}^{n−1} C_{i},
∑_{α̃=n} m_{n}(α)K_{0}^{α_{1}}K_{1}^{α_{2}} ⋯ K_{n−1}^{α_{n}} = \underline{A026674}(n),

∑_{α̃=n}(−1)^{|α|−1}m_{n}(α)H_{0}^{α_{1}}H_{1}^{α_{2}} ⋯ H_{n−1}^{α_{n}} = \underline{A023053}(n − 1),
∑_{α̃=n} m_{n}(α)H_{0}^{α_{1}}H_{1}^{α_{2}} ⋯ H_{n−1}^{α_{n}} = \underline{A098746}(n),
∑_{α̃=n} m_{n}(α)H_{1}^{α_{1}}H_{2}^{α_{2}} ⋯ H_{n}^{α_{n}} = \underline{A047099}(n),
∑_{α̃=n}(−1)^{|α|−1}m_{n}(α)H_{2}^{α_{1}}H_{3}^{α_{2}} ⋯ H_{n+1}^{α_{n}} = \underline{A007226}(n − 1), n ≥ 2,
∑_{α̃=n}(−1)^{|α|−1}m_{n}(α)J_{0}^{α_{1}}J_{1}^{α_{2}} ⋯ J_{n−1}^{α_{n}} = \underline{A121545}(n),
∑_{α̃=n} m_{n}(α)J_{0}^{α_{1}}J_{1}^{α_{2}} ⋯ J_{n−1}^{α_{n}} = H_{n},

where p_{n} is given by (17) and we make use of the notation from Lemma 1.

3 Combinatorial proofs

In this section, we provide combinatorial arguments for several of the determinant formulas from the prior section. First, recall the definition of the determinant of an n × n matrix A as a (signed) sum over the set S_{n} of permutations of [n] given by

det(A) = ∑_{σ∈S_{n}} sgn(σ)a_{1,σ(1)} ⋯ a_{n,σ(n)},  (24)

where A = (a_{i,j})_{1≤i,j≤n} and sgn(σ) denotes the sign of σ ∈ S_{n}. Assume that permutations are arranged as disjoint cycles, with the smallest element first in each cycle. In the case when A is Toeplitz-Hessenberg, we have that only permutations σ each of whose cycles comprises a set of consecutive integers in their natural order can make a nonzero contribution towards the sum in (24). Otherwise, one of the factors a_{i,σ(i)} in the product of terms corresponding to σ in (24) is ensured of being zero.

Recall that a composition of n ≥ 1 is a sequence of positive integers, called parts, whose sum is n. Let C_{n,k} denote the set of compositions of n whose members have exactly k parts and let C_{n} = ∪_{k=1}^{n}C_{n,k}. Then permutations of [n] capable of making a nonzero contribution towards det(A) when A is Toeplitz-Hessenberg are clearly synonymous with the members of C_{n}, upon identifying the various cycle lengths as parts.

Suppose that each part of size i for i ≥ 1 within a member of C_{n} is to receive a weight of a_{i}, where (a_{i})_{i≥0} denotes the sequence associated with the Toeplitz-Hessenberg matrix A defined by (1). Then one may regard the sum in (24) in this case as being over C_{n}, where the (signed) weight of a member π = (π_{1}, …, π_{k}) ∈ C_{n,k} is given by (−a_{0})^{n−k} ∏_{i=1}^{k} a_{π_{i}}. When a_{0} = −1, then all of the terms in the expansion of det(A) are non-negative, assuming (a_{i})_{i≥1} is non-negative, and one gets

det(A) = ∑_{π∈C_{n}} a_{π_{1}}a_{π_{2}} ⋯,  a_{0} = −1,  (25)

where π_{i} denotes the i-th part of π = (π_{1}, π_{2}, …) ∈ C_{n}. On the other hand, if a_{0} = 1, then one gets the signed sum

det(A) = ∑_{π∈C_{n}}(−1)^{n−μ(π)}a_{π_{1}}a_{π_{2}} ⋯,  a_{0} = 1,  (26)

where μ(π) denotes the number of parts of the composition π.

So to obtain combinatorial arguments for the determinant formulas from the prior section wherein a_{0} = ±1, we interpret det(A) as a positive or signed sum over C_{n} in which parts are weighted as in (25) or (26). The problem of finding combinatorial expressions (and explanations thereof) for positive composition sums such as those on the right-hand side of (25) is one that has been encountered previously on occasion; see, e.g., [26, p. 46, Exercises 14.f, 14.g, and 14.h]. For the signed sums considered here of the form (26), we will make use of sign-changing involutions to establish the result. See, e.g., the text [4, Chapter 6] as well as [5] for proofs of some basic combinatorial identities that utilize involutions.

For the first several results that we prove in this section, we consider cases of (25) or (26) where a_{i} corresponds to the cardinality of some set of lattice paths. See [9, Section 4] for comparable combinatorial arguments in which the sequence represented by a_{i} for i ≥ 1 is derived from the classical Catalan numbers. Before proceeding, let us recall some standard terminology. By a Dyck path, we mean a sequence of u = (1, 1) and d = (1, −1) steps starting at the origin and terminating on the x-axis that never goes below the x-axis. The semi-length of a Dyck path ρ, denoted by |ρ|, is defined as the number of u steps in ρ (i.e., half the total number of steps of ρ). Let D_{n} for n ≥ 1 denote the set of all Dyck paths of semi-length n, with D_{0} the singleton set consisting of the empty lattice path. It is wellknown that |D_{n}| = C_{n} for all n ≥ 0. By a unit α within a Dyck path ρ, we mean a string of consecutive steps of ρ of the form α = uα′d, where the initial u starts and terminal d ends on the x-axis and α′ does not touch the x-axis at any point. That is, α′ itself is a Dyck path (possibly empty) when viewed as starting from the origin.

We now provide combinatorial proofs of the identities (12), (13), (16), (11), (14), (15), (7), (9), (23), and (19) in that order. For the first three identities, we perform a direct enumeration and define an appropriate bijection in establishing the determinant in question as a_{0} = −1.

3.1 Proofs of (12), (13), and (16)

To show (12), first note that D_{−}(C_{1}, …, C_{2n−1}) enumerates compositions of n in which parts of size i are weighted by C_{2i−1} for each i ≥ 1. To capture this idea combinatorially, let π = (π_{1}, π_{2}, …) ∈ C_{n} and λ = (λ_{1}, λ_{2}, …), with each λ_{i} ∈ D_{2π_{i}−1}. Note that the number of parts of π, and hence components of λ, may vary from 1 to n. Then D_{−}(C_{1}, …, C_{2n−1}) gives the cardinality of the set S of all possible ordered pairs (π, λ), as π ranges over C_{n} and λ can be any one of the vectors of Dyck paths corresponding to π. Given α = (π, λ) ∈ S, define g(α) as the concatenation of the lattice paths uλ_{i}d for i ≥ 1, i.e., g(α) = ∏_{i≥1} uλ_{i}d. From this, it is seen that D_{−}(C_{1}, …, C_{2n−1}) gives the cardinality of the subset of D_{2n} consisting of those members in which only returns to the x-axis of the form (2i, 0) where i is even are possible. Recall that one of the combinatorial interpretations of \underline{A066357}(n) is that it enumerates lattice paths from (0, 0) to (2n, 2n) using (1, 0) and (0, 1) steps that lie on or above the line y = x and avoid points (m, m) where m is odd. Upon rotating by 45^{∘} clockwise and dilating by a factor of \sqrt{2}, such lattice paths are seen to be synonymous with the aforementioned subset of D_{2n} enumerated by D_{−}(C_{1}, …, C_{2n−1}), which implies (12).

We now show (13). Given n ≥ 1 and 1 ≤ k ≤ n, let A_{n,k} denote the set of vectors λ = (λ_{1}, …, λ_{k}) of Dyck paths such that ∑_{i=1}^{k} |λ_{i}| = n + k and |λ_{i}| ≥ 2 for all i. Then we have D_{−}(C_{2}, …, C_{n+1}) = |A_{n}| for n ≥ 1, where A_{n} = ∪_{k=1}^{n}A_{n,k}. We seek to show |A_{n}| = p_{n}, where p_{n} is as defined above. Since

∑_{n≥1} p_{n}x^{n} = \frac{1}{2 − C^{2}} − 1 = \frac{C^{2} − 1}{1 − (C^{2} − 1)} = ∑_{k≥1}(C^{2} − 1)^{k},

we have that p_{n} gives the cardinality of the set A′_{n} consisting of all vectors of the form ρ = (ρ_{1}, …, ρ_{k}) where k ∈ [n] in which ∑_{i=1}^{k} |ρ_{i}| = n and each ρ_{i} is a nonempty Dyck path wherein a point of ρ_{i} along the x-axis is marked (possibly the first or last point). That is, each ρ_{i} can be expressed as ρ_{i} = α_{i}β_{i}, where α_{i} and β_{i} are Dyck paths such that the final point of α_{i} is marked (with this point being the origin if α_{i} is empty). Consider decomposing each component λ_{i} for i ≥ 1 within λ = (λ_{1}, λ_{2}, …) ∈ A_{n} as λ_{i} = γ_{i}uδ_{i}d, where γ_{i} and δ_{i} denote possibly empty Dyck paths. Define f(λ) by (γ_{1}δ_{1}, γ_{2}δ_{2}, …) wherein the final point of γ_{i} is marked in each component lattice path. Then f(λ) ∈ A′_{n} for each λ as |λ_{i}| ≥ 2 for all i and f is seen to be a bijection between A_{n} and A′_{n}. This implies |A_{n}| = |A′_{n}| = p_{n}, as desired, and completes the proof of (13).

Finally, to show (16), first observe that K_{n−1} = C_{n+1} − C_{n} enumerates members of D_{n+1} starting with uu, by subtraction. Thus, we have that D_{−}(K_{0}, …, K_{n−1}) counts the set B_{n} consisting of all vectors ν = (ν_{1}, ν_{2}, …) of Dyck paths such that ∑_{i≥1} |ν_{i}| = n+k, where each ν_{i} starts uu and k denotes the number of components of the specific vector in question. Recall that \underline{A026674}(n) is the coefficient of x^{n} in the expansion of \frac{xC^{3}}{1−xC^{3}} = xC^{3} + x^{2}C^{6} + ⋯, and a combinatorial interpretation for this sequence in terms of lattice paths may be realized as follows. Given n ≥ 1, let B′_{n} denote the set of vectors π = (π_{1}, π_{2}, …) wherein ∑_{i≥1} |π_{i}| = n and each π_{i} is a nonempty Dyck path one of whose units is marked. Upon considering the sections prior to and following the marked unit, we see that each component path π_{i} within π is accounted for by xC^{3}. Hence, the coefficient of x^{k}C^{3k} enumerates the subset of vectors in B′_{n} which contain exactly k components for each k ≥ 1. Considering all possible k thus implies |B′_{n}| = \underline{A026674}(n) for n ≥ 1.

To complete the proof of (16), it then suffices to define a bijection between B_{n} and B′_{n}. To do so, first note that since each component ν_{i} of ν ∈ B_{n} starts with uu, we have ν_{i} = uα_{i}β_{i}dγ_{i}, where α_{i} is a unit and β_{i} and γ_{i} are possibly empty Dyck paths. Define ν′_{i} = β_{i}α_{i}γ_{i}, where the unit α_{i} is to be marked, and let ν′ = (ν′_{1}, ν′_{2}, …). Note that ν′ ∈ B′_{n} for all ν since a single u and d have been removed from each component ν_{i} of ν. The mapping ν ↦ ν′ then provides a bijection between B_{n} and B′_{n}, which implies (16).

For the next two determinant identities when a_{0} = 1, we make use of sign-changing involutions in establishing the results. Given a (signed) set S, we denote the sum of the signs of the elements of S by σ(S).

3.2 Proofs of (11) and (14)

To show (11), where r ≥ 1 is fixed, first note that a member of C_{n} containing a part greater than r does not contribute to the determinant in (11), so we may restrict attention to members of C_{n} with all parts in [r]. Given 1 ≤ k ≤ n, let C_{n,k}^{(r)} denote the subset of C_{n,k} consisting of those members whose parts all lie in [r]. Note that C_{n,k}^{(r)} = ∅ if k < t, so we may assume k ≥ t, where t = ⌈n/r⌉. Let I_{j} := [(j − 1)r + 1, jr] for j ≥ 1. Define T_{n,k}^{(r)} to be the set consisting of all subsets α of [rk] of size n such that α ∩ I_{j} ≠ ∅ for all 1 ≤ j ≤ k. For each π = (π_{1}, …, π_{k}) ∈ C_{n,k}^{(r)}, let π^{∗} denote the subset of T_{n,k}^{(r)} consisting of those α such that |α ∩ I_{j}| = π_{j} for each j ∈ [k]. Note |π^{∗}| = ∏_{j=1}^{k} \binom{r}{π_{j}} for each π, with T_{n,k}^{(r)} = ∪_{π}π^{∗} and

the π^{∗} mutually disjoint, where the union is over all π ∈ C_{n,k}^{(r)}. Define the sign of a member of T_{n,k}^{(r)} by (−1)^{n−k}. Let T_{n}^{(r)} = ∪_{k=t}^{n}T_{n,k}^{(r)}, and thus we have

D_{+} (\binom{r}{1}, \binom{r}{2}, …, \binom{r}{n}) = σ(T_{n}^{(r)}), n, r ≥ 1.

Given α ∈ T_{n}^{(r)}, let α_{j} := |α ∩ I_{j}| and m_{j} = min(α ∩ I_{j}) for j ≥ 1. Let T̃_{n}^{(r)} denote the subset of T_{n}^{(r)} consisting of those α for which α_{j} = 1 and m_{j+1} − r ≤ m_{j} for all j. Note T̃_{n}^{(r)} ⊆ T_{n,n}^{(r)} and hence each member of T̃_{n}^{(r)} is of positive sign. Further, we have |T̃_{n}^{(r)}| = \binom{n+r−1}{n}, as members of T̃_{n}^{(r)} are seen to be synonymous with weak compositions of n with r parts. To complete the proof of (11), it suffices to define a sign-changing involution on T_{n}^{(r)} − T̃_{n}^{(r)} as follows. Suppose α ∈ T_{n}^{(r)} − T̃_{n}^{(r)} and let j_{0} denote the smallest j ≥ 1 such that either (i) α_{j} ≥ 2 or (ii) α_{j} = 1, with m_{j+1} − r > m_{j}. Let α′ be the member of T_{n}^{(r)} obtained from α by either adding r to each element of α greater than m_{j_{0}} if (i) holds, or subtracting r from each such element of α if (ii). Then one may verify that the mapping α ↦ α′ provides the desired sign-changing involution, which completes the proof of (11).

To show (14), first note that compositions containing a part of size 1 do not contribute to the determinant since K_{−1} = 0. We then associate to each part of size i ≥ 2 within π ∈ C_{n} a member of D_{i} that starts u^{2}, where it is assumed that π contains no 1’s. We will describe a u^{2} string in which the first u originates on the x-axis as basal. Concatenating the various Dyck paths that arise as one considers all of the parts of π from left to right yields a marked member of D_{n} starting with u^{2} such that some subset of the basal u^{2} is marked, with the initial u^{2} always being marked. Let E_{n} denote the set of marked members of D_{n} starting with u^{2} and marked as described. Define the sign of ρ ∈ E_{n} as (−1)^{n−k}, where k denotes the number of marked basal u^{2} occurring in ρ. Then we have D_{+}(K_{−1}, …, K_{n−2}) = σ(E_{n}) for n ≥ 1.

Define a sign-reversing involution on E_{n} by identifying the leftmost non-initial basal u^{2}, if it exists, and changing its status as to whether or not it is marked. The set of survivors of this involution consists of those ρ ∈ E_{n} of the form ρ = uρ′d(ud)^{n−i−1} for some 1 ≤ i ≤ n−1, where ρ′ is a Dyck path. Such ρ all have sign (−1)^{n−1} and are enumerated by ∑_{i=1}^{n−1} C_{i}, upon considering the semi-length of ρ′. Thus, we have that σ(E_{n}) is given by the right side of (14) as well, which completes the proof.

The combinatorial proofs of the subsequent two identities require more intricate signchanging involutions.

3.3 Proof of (15)

Given n ≥ 1 and 1 ≤ k ≤ n, let F_{n,k} denote the set of sequences of ordered pairs (i_{1}, λ_{1}), …, (i_{k}, λ_{k}) such that (i_{1}, …, i_{k}) ∈ C_{n,k} and λ_{j} ∈ D_{i_{j}+1} for all j ∈ [k], with each λ_{j} starting u^{2}. Define the sign of a member of F_{n,k} by (−1)^{n−k} and let F_{n} = ∪_{k=1}^{n}F_{n,k}. Then we have D_{+}(K_{0}, …, K_{n−1}) = σ(F_{n}) for n ≥ 1. We define a preliminary sign-changing involution on F_{n} as follows. Let (x, λ) denote the final ordered pair within π ∈ F_{n}. Suppose first that λ contains two or more units, that is, we may write λ = λ′λ′′, where λ′ ≠ ∅ and λ′′ is the final unit of λ. In this case, we replace (x, λ) with the two components (y, λ′), (z, uλ′′d), leaving the rest of π undisturbed, where |λ′| = y + 1, |λ′′| = z and x = y + z. Note λ′ ≠ ∅ implies it must start u^{2} and hence y ≥ 1, as required. We perform the reversal of the procedure just described if λ consists of a single unit of the form λ = u^{2}νd^{2} for some Dyck path ν. We will describe such a unit λ as being simple, with all other units ≠ ud being non-simple.

This involution may be extended by considering, if it exists, the rightmost component (x, λ) within π such that λ contains two or more units or consists of a single simple unit and performing one of the two procedures described in the preceding paragraph on this component. Note that in cases where λ is a simple unit, we require that (x, λ) not be the first ordered pair of π. Then the set F′_{n} of survivors of this extended involution on F_{n} consists of those sequences of pairs (i_{1}, λ_{1}), (i_{2}, λ_{2}), … in F_{n} such that λ_{j} for each j ≥ 2 is a nonsimple unit, with λ_{1} a unit of either kind. Upon deleting the initial u and terminal d steps of λ_{j} for each j ≥ 1, one may regard members of F′_{n} as sequences of the form (i_{1}, ρ_{1}), (i_{2}, ρ_{2}), … such that (i_{1}, i_{2}, …) ∈ C_{n} and ρ_{j} ∈ D_{i_{j}} for all j, with each ρ_{j} containing two or more units except for possibly ρ_{1}, which may contain a single unit. Note that, by removing the initial u and terminal d as described, there is no longer the restriction that Dyck paths in the second component start with u^{2}.

We now define an involution on F′_{n} as follows. Suppose ρ = (i_{1}, ρ_{1}), …, (i_{k}, ρ_{k}) is a member of F′_{n} for some 1 ≤ k ≤ n. We consider several cases on ρ_{1}. If ρ_{1} is a unit and k > 1, then replace (i_{1}, ρ_{1}), (i_{2}, ρ_{2}) with (i_{1} + i_{2}, ρ_{1}ρ_{2}). Conversely, if ρ_{1} contains at least three units, then we split the first ordered pair of ρ so as to create two pairs, the first of which will have a unit for its second coordinate. On the other hand, if ρ_{1} is a unit with k = 1, then there are C_{n−1} possibilities for ρ, each having sign (−1)^{n−1}.

So suppose ρ_{1} within (i_{1}, ρ_{1}) contains exactly two units, and write ρ_{1} = αβ, with α and β denoting the two units. If α = ud and k > 1, then replace (i_{1}, udβ), (i_{2}, ρ_{2}) with (i_{1} +i_{2}, uρ_{2}dβ) and, conversely, split the first ordered pair of ρ as indicated if α is non-simple with k ≥ 1. On the other hand, if α = ud and k = 1, then no such operation can be performed and the sum of the signs of these survivors is given by (−1)^{n−1}C_{n−2}, as β is a unit with |β| = n − 1 in this case. So assume α is a simple unit. If β = ud and k > 1, then replace (i_{1}, αud), (i_{2}, ρ_{2}) with (i_{1} + i_{2}, αuρ_{2}d) and, conversely, split the first ordered pair of ρ as indicated if β is non-simple with k ≥ 1. If β = ud and k = 1, then, assuming n ≥ 3, there is a contribution towards σ(F′_{n}) of (−1)^{n−1}C_{n−3} in this case, as ρ_{1} = αud with α simple.

So assume n ≥ 4 and ρ_{1} = αβ, where α and β are both simple. Then we have α = uα′d and β = uβ′d, where α′ and β′ are units. We then repeat the argument given in the preceding paragraph with α′β′ in place of αβ. Note it is understood that one is to add a u just before and a d directly following each of the two units of the second coordinate in the first ordered pair within all of the relevant members of F′_{n−2} after the transformations described above are made using α′β′ in place of αβ. This yields survivors having cardinality C_{n−4} + C_{n−5}, with each of sign (−1)^{n−1}, where C_{−1} = 0. We then repeat the preceding argument on the resulting set of survivors until no further steps can be applied.

Thus, combining all of the survivors from the various steps of the sign-changing involution defined above yields members of F′_{n} with k = 1 of the form (n, ν), where ν is one of the following: (i) ν a unit, (ii) ν = αβ, where α = u^{i}d^{i} and β = u^{i−1}β′d^{i−1} for some i ≥ 1, with β′ a unit, or (iii) ν = αβ, where α = u^{i}α′d^{i} and β = u^{i}d^{i} for some i ≥ 1, with α′ a unit. This implies that the cardinality of the set of survivors is given by

C_{n−1} + ∑_{i=1}^{⌊n/2⌋}(C_{n−2i} + C_{n−2i−1}),

which may be rewritten as ∑_{i=0}^{n−1} C_{i}. As each survivor has sign (−1)^{n−1}, we have that σ(F_{n}) = σ(F′_{n}) is also given by the right side of (15), which completes the proof.

3.4 Proof of (7)

Given n ≥ 2 and 1 ≤ k ≤ n, let G_{n,k} denote the set of sequences of ordered pairs (i_{1}, λ_{1}), …, (i_{k}, λ_{k}) such that (i_{1}, …, i_{k}) ∈ C_{n,k} and λ_{j} ∈ D_{i_{j}+2} for all j ∈ [k], with each λ_{j} starting u^{2}. Define the sign of a member of G_{n,k} by (−1)^{n−k} and let G_{n} = ∪_{k=1}^{n}G_{n,k} so that D_{+}(K_{1}, …, K_{n}) = σ(G_{n}). We define a preliminary sign-changing involution on G_{n} as follows. Let (x, λ) denote the final ordered pair within π ∈ G_{n,k} for some k ∈ [n]. First suppose λ contains two or more units. Let λ = αβγ, where α and γ are units and β is possibly empty.

Let y = |α| + |β| and we consider cases on y. If y ≥ 3, then replace (x, λ) with the two ordered pairs (y − 2, αβ), (z, u^{2}d^{2}γ), leaving the rest of π undisturbed, where z = |γ| and hence x = y + z − 2. If y = 2, then α = u^{2}d^{2} and β = ∅, in which case we perform the reversal of the operation just described and merge the final two pairs of π accordingly, which can be done provided k > 1.

We extend this involution by considering the largest j, if it exists, such that λ_{j} contains two or more units and applying one of the two operations described in the prior paragraph using the j-th ordered pair (and its predecessor, in case of the latter operation). The set G′_{n} of survivors of this extended involution on G_{n} consists of those sequences of pairs (i_{1}, λ_{1}), (i_{2}, λ_{2}), … such that λ_{j} is a unit for all j ≥ 2, with λ_{1} either a unit or of the form λ_{1} = u^{2}d^{2}ν for a unit ν.

Let π = (i_{1}, λ_{1}), …, (i_{k}, λ_{k}) for some k ∈ [n] denote a member of G′_{n}. First suppose λ_{1} is a unit. If λ_{k} = u^{2}δd^{2}, where δ is a Dyck path with |δ| ≥ 2, then replace (i_{k}, λ_{k}) with (i_{k} − 1, uδd), (1, u^{3}d^{3}), and vice versa, if δ = ud. Note n ≥ 2 implies k > 1 in cases when (i_{k}, λ_{k}) = (1, u^{3}d^{3}), whence there is a predecessor and the merging of the final two pairs of π can indeed be implemented. On the other hand, if λ_{k} is expressible as λ_{k} = uαβd, where α is a unit and β is a Dyck path with |β| ≥ 2, then replace (i_{k}, λ_{k}) with (x, uβd), (y, uαud^{2}), where x = |β|−1 and y = |α|. Note that i_{k} = x+y, as required, since |λ_{k}| = |α|+|β|+1 = x+y+2. If β = ud in λ_{k}, then we perform the reverse operation on π, provided k > 1. Note that members of G′_{n} with k = 1 of the form (i_{1}, λ_{1}) = (n, uαud^{2}), where α is a unit, remain unpaired. There are C_{n−1} possibilities for such members of G′_{n} as |α| = n in this case, and each has sign (−1)^{n−1}.

Now suppose λ_{1} = u^{2}d^{2}ν for a unit ν. Each such sequence π in G′_{n} where k ≥ 3 is paired with another of opposite sign, by the preceding. Thus, the unpaired π ∈ G′_{n} at this point wherein λ_{1} = u^{2}d^{2}ν are those for which k = 1 or k = 2 with λ_{2} = u^{3}d^{3} or λ_{2} = uδud^{2} for a unit δ. Consider the following further pairings:

(i) (n, u^{2}d^{2}uαd) ↔ (n − 1, u^{2}d^{2}α), (1, u^{3}d^{3}),
(ii) (n, u^{2}d^{2}uαβd) ↔ (a, u^{2}d^{2}α), (b, u^{2}βdud^{2}),

where α is a unit, β is a nonempty Dyck path, a = |α| and b = |β| + 1. Note that n ≥ 2 implies the section α is indeed nonempty in (i). It is seen that sequences π with k = 2 of the form (n − 1, u^{2}d^{2}α), (1, u^{2}dud^{2}) are not paired by (i) or (ii). Then α a unit with |α| = n − 1 implies there are C_{n−2} possibilities for such π, each having sign (−1)^{n−2}. Combining with the survivors above of the form (i_{1}, λ_{1}) = (n, uαud^{2}) implies

σ(G_{n}) = σ(G′_{n}) = (−1)^{n−1}(C_{n−1} − C_{n−2}),

which completes the proof of (7).

Before proving the next pair of identities, we recall some further terminology. A (rooted) ternary tree T is a set of connected vertices (called nodes) in which each node either has exactly three children or is childless, where one node (namely, the root) is the ancestor of all other nodes. Nodes of T for which there are no children are referred to as leaves. The three nodes emanating from a node v that is not a leaf are called the left, middle, and right children of v. The set of descendants of v is the subtree of T for which v is the root. Finally, the level of v is the minimum number of edges one must traverse to get back to the root r of T. Thus, the three children of r have level 1, their children have level 2, and so on, with r being the only node of level 0. Finally, the number of nodes of T that have children is denoted by |T |, or equivalently it is the total number of edges in T divided by three.

Let R_{n} denote the set of all ternary trees T with |T | = n. Recall H_{n} = \underline{A001764}(n) = |R_{n}| for n ≥ 0, with J_{n} = \underline{A006013}(n) enumerating the set of all ordered pairs (ρ, λ) of ternary trees for which |ρ| + |λ| = n.

3.5 Proofs of (9) and (23)

We first show (9). Given n ≥ 1 and 1 ≤ k ≤ n, let H_{n,k} denote the set of vectors (λ_{1}, …, λ_{k}) of ternary trees such that ∑_{j=1}^{k} |λ_{j}| = n and |λ_{j}| ≥ 1 for each j. Define the sign of a member of H_{n,k} by (−1)^{n−k} and let H_{n} = ∪_{k=1}^{n}H_{n,k}. Then it is seen D_{+}(H_{1}, …, H_{n}) = σ(H_{n}) for n ≥ 1. To define a sign-changing involution on H_{n}, we consider cases on the first component λ_{1} of λ = (λ_{1}, λ_{2}, …) ∈ H_{n} as follows. Let r denote the root of λ_{1} and r_{i} for 1 ≤ i ≤ 3 the left, middle, and right child of r, respectively. Let ρ denote the subtree of λ_{1} obtained by considering the complete set of descendants of r_{2}, with r_{2} understood to be the root of ρ, and let a = |ρ|. If a > 0, then we form the two ternary trees α and β, where α is obtained from λ_{1} by deleting all of the descendants of r_{2} (which would make r_{2} a leaf in α) and β is taken to be a copy of the subtree ρ. One may verify |α| + |β| = |λ_{1}|, with this operation reversing the sign of λ as the number of components changes by one. On the other hand, if a = 0, i.e., if r_{2} is a leaf of λ_{1}, then we perform the reverse operation and merge the components λ_{1} and λ_{2} of λ so that the root of λ_{2} coincides with the middle child r_{2} of r in λ_{1} (and hence the non-root nodes of λ_{2} become the set of descendants of r_{2}). Note that this latter operation can be done provided λ ∈ H_{n,k} for some k > 1.

Combining the preceding two operations then yields a sign-changing involution on H_{n} that fails to be defined on members of H_{n,1} for which the middle child of the root is a leaf. Then each survivor has sign (−1)^{n−1}, and to see that they number J_{n−1}, consider the subtrees σ and ν of λ_{1} corresponding to the set of descendants of the children r_{1} and r_{3} of r, noting |σ| + |ν| = n − 1 since r_{2} is a leaf. Thus, we also have that σ(H_{n}) is given by (−1)^{n−1}J_{n−1} for n ≥ 1, which completes the proof of (9).

To show (23), first let J_{n,k} for 1 ≤ k ≤ n denote the set of vectors (π_{1}, …, π_{k}) such that π_{i} for each i is a ternary tree with |π_{i}| ≥ 1 wherein the middle child of the root is a leaf and ∑_{i=1}^{k} |π_{i}| = n. Note that if |π_{i}| = b, then there are J_{b−1} possibilities for the component π_{i} since the combined size of the subtrees comprising the descendants of the left and right children of the root is b − 1 (the middle child being a leaf). Thus, we have D_{−}(J_{0}, …, J_{n−1}) = |J_{n}| for n ≥ 1, where J_{n} = ∪_{k=1}^{n}J_{n,k}, since the combined size of all the component trees π_{i} is n.

\begin{matrix}π_{1} = \\ π_{2} = \\ π_{3} = \\ π_{4} = \\ f(π) = \end{matrix}

Figure 1: π = (π_{1}, π_{2}, π_{3}, π_{4}) ∈ J_{6} and f(π) ∈ R_{6}.

To complete the proof of (23), we need to show |J_{n}| = H_{n} for n ≥ 1, and for this, we seek a bijection between J_{n} and R_{n}. To do so, suppose π = (π_{1}, π_{2}, …) ∈ J_{n}. Let r_{i} denote the root and v_{i} the middle child of the root of π_{i} for each i ≥ 1. Let f(π) be the ternary tree obtained from π by fusing π_{i} to π_{i+1} such that r_{i+1} coincides with v_{i} for all i. See Figure 1 above for an example of f when n = 6. Then ∑_{i≥1} |π_{i}| = n implies f(π) ∈ R_{n} for all π. Note that π ∈ J_{n,k} implies the level of the descendant δ reached by starting with the root of f(π) and picking the middle child each time until one encounters a leaf is given by k for each k ∈ [n]. Thus, to reverse f, one may start with the root r of λ ∈ R_{n} and note the sequence of descendants r = p_{0}, p_{1}, …, p_{k} = δ wherein p_{j} is the middle child of p_{j−1} for each j ∈ [k] and δ is childless. Then use the subtrees of λ obtained by considering the descendants of the two siblings of p_{j} for each j to construct the various components of f^{−1}(λ). Hence, the mapping f between J_{n} and R_{n} is seen to be reversible, and thus provides the desired bijection between the two sets.

Before proving our last identity, let us recall some terminology related to finite set partitions. By a partition of a set, we mean a collection of nonempty pairwise disjoint subsets, called blocks, whose union is the set. Let P_{n} denote the set of all partitions of [n] for n ≥ 1, with P_{0} consisting of the single empty partition with no blocks. A partition Π = B_{1}/B_{2}/ ⋯ ∈ P_{n} is said to be in standard form if its blocks B_{i} are arranged such that min(B_{i}) < min(B_{i+1}) for all i. An equivalent sequential representation of Π, expressed in standard form, is obtained by writing π = π_{1} ⋯ π_{n} wherein i ∈ B_{π_{i}} for each i ∈ [n] (see, e.g., [28]). The sequence π is referred to as the canonical sequential form of the partition Π. It is straightforward to show π_{i+1} ≤ max(π_{1} ⋯ π_{i}) + 1 for 1 ≤ i ≤ n − 1 with π_{1} = 1, which is referred to as the restricted growth condition (see, e.g., [18]).

Recall that a partition Π is said to be non-crossing (see [15]) if its canonical form contains no subsequences of the form a-b-a-b, where a < b (i.e., if it avoids the pattern 1-2-1-2 in the classical sense). Let N C_{n} denote the set of non-crossing partitions of [n]; it is well-known that |N C_{n}| = C_{n} for all n ≥ 0. We make the following preliminary observations concerning the canonical form of a member of N C_{n}. Suppose that the sequential form π of a member of N C_{n} is written as π = 1π^{(1)} ⋯ 1π^{(r)}, where each π^{(i)} contains no 1’s if non-empty. Let 1 ≤ i_{1} < ⋯ < i_{s} ≤ r denote the set of indices i such that π^{(i)} ≠ ∅. Then the distinct letters of π^{(i_{1})} comprise the interval [2, x], where x = max(π^{(i_{1})}), with π^{(i_{1})} itself being a non-crossing partition on this alphabet. Further, we have that π non-crossing implies min(π^{(i_{j})}) = max(π^{(i_{j−1})}) + 1 for 2 ≤ j ≤ s, with each π^{(i_{j})} non-crossing on its respective alphabet of letters, which comprises an interval for each j. Recall that the sequence H_{n} enumerates, among other things, the set U_{n} of non-crossing partitions of [2n] where each block is of even size, i.e., each letter in its canonical sequential form occurs an even number of times.

We next describe a lattice path interpretation for the sequence H_{n}. By a descent within a Dyck path λ, we mean a maximal sequence of consecutive d steps. A descent is classified as even or odd depending upon the parity of the number of d steps contained therein. Let V_{n} denote the subset of D_{2n} in whose members all descents are even. Then it is well-known that |V_{n}| = H_{n} for n ≥ 1, and we describe in the following lemma a bijection between U_{n} and V_{n}.

Lemma 10. There is a bijection g_{n} between U_{n} and V_{n} for each n ≥ 0.

Proof. By a slight abuse of notation, we will denote the bijection g_{n} : U_{n} ↦ V_{n} simply by g for all n. We define g recursively on n, the n = 0 case sending the empty partition to the empty lattice path. If n ≥ 1, then we represent π ∈ U_{n} sequentially as π = 1π^{(1)} ⋯ 1π^{(2r)} for some r ≥ 1, where π^{(i)} for each i contains no 1’s and may be empty. From the observations made previously concerning non-crossing partitions, each of the letters of π other than 1 has all of its occurrences contained within some nonempty π^{(i)}, and hence each of the blocks corresponding to the section π^{(i)} is of even size. We may then define g(π) by setting

g(π) = ug(π^{(1)})ug(π^{(2)})d^{2} ⋯ ug(π^{(2r−1)})ug(π^{(2r)})d^{2},

where each section π^{(i)} is to be viewed as a restricted growth function with smallest letter 1 concerning the application of g to π^{(i)}. Note that the number of 1’s in π is equal to twice the number of returns to the x-axis in g(π) for all π. Upon considering the positions and number of returns within an arbitrary member of V_{n}, it is then possible to construct its inverse image under g. Thus, the mapping g yields a bijection between U_{n} and V_{n}.

To illustrate the bijection g, note that when n = 1, we have g(11) = u^{2}d^{2}, and for n = 2, we have g(1111) = u^{2}d^{2}u^{2}d^{2}, g(1122) = u^{4}d^{4}, and g(1221) = u^{3}d^{2}ud^{2}. One can then deduce g for larger n using the prior established values; for example, if n = 6 and π = 123321441155 ∈ U_{6}, then g(π) = u^{4}d^{2}ud^{2}u^{3}d^{4}u^{4}d^{4} ∈ V_{6}.

We now provide a combinatorial explanation of (19), where we draw upon the prior bijection.

3.6 Proof of (19)

Let L_{n,k} for 1 ≤ k ≤ n denote the set of vectors (ρ_{1}, …, ρ_{k}) of non-crossing partitions with even block sizes such that |ρ_{1}| + ⋯ + |ρ_{k}| = 2n − 2k, where the ρ_{i} are allowed to be empty, and let L_{n} = ∪_{k=1}^{n}L_{n,k}. Then we have D_{−}(H_{0}, …, H_{n−1}) = |L_{n}| for all n ≥ 1. We now seek to express the vectors in L_{n} as members of a certain subset of U_{n} as follows. By a run within a block B in a member of P_{n}, we mean a maximal sequence of consecutive integers each element of which lies in B. Let U′_{n} denote the subset of U_{n} consisting of those members such that the first block D (i.e., the block in which 1 lies) contains the element 2n and satisfies the following restrictions with regard to its runs:

(i) either D contains all of [2n] or it contains two or more runs,
(ii) if it contains two or more runs, the run of D that contains 1 must have odd length, as

does the run of D containing 2n,

(iii) all other runs in D have even length.

We define a bijection between L_{n} and U′_{n} as follows. Suppose ρ ∈ L_{n} and say ρ = (ρ_{1}, …, ρ_{m}) for some m ∈ [n]. Let 1 ≤ i_{1} < i_{2} < ⋯ be the complete set of indices i such that ρ_{i} ≠ ∅. Let x_{j} = max(ρ_{i_{j}}) for j ≥ 1. We represent the partition ρ_{i_{1}} sequentially as a restricted growth function using the letters in the alphabet {2, 3, …, x_{1} + 1}. Then for each ℓ ≥ 2, we represent ρ_{i_{ℓ}} sequentially using the letters in the interval [S_{ℓ−1} + 2, S_{ℓ} + 1], where S_{ℓ} = ∑_{j=1}^{ℓ} x_{j} for each ℓ ≥ 1. For each r ∈ [m], let w_{r} denote the word obtained as described from ρ_{i_{ℓ}} if r = i_{ℓ} for some ℓ ≥ 1 and let w_{r} be the empty word if r ≠ i_{ℓ} for any ℓ (i.e., if the r-th component of ρ is the empty partition). Define w_{ρ} to be the word of length 2n obtained as the concatenation ∏_{r=1}^{m}(1w_{r}1); i.e., we both prepend and append a 1 to each word w_{r} (including cases when it is empty) and write the resulting words for all r ∈ [m] from left to right. It is seen that w_{ρ} ∈ U′_{n}, represented sequentially, and that the combined number of blocks in all of the nonempty components of ρ is given by max(w_{ρ}) − 1 for each ρ ∈ L_{n}. One may then verify that the mapping ρ ↦ w_{ρ} is indeed a bijection between L_{n} and U′_{n}, as desired.

By a valley within λ, we mean an occurrence of a d step being directly followed by a u. The height of a valley refers to the y-coordinate of the valley vertex, i.e., the final height achieved by the d step. Let V′_{n} denote the subset of V_{n} in which no valleys of height one occur in its members. Recall that one of the combinatorial interpretations for \underline{A098746}(n) is that it gives the cardinality of V′_{n} for all n ≥ 1. Thus, to complete the proof of (19), it suffices to define a bijection between U′_{n} and V′_{n}, as it was demonstrated above that |U′_{n}| = |L_{n}|.

To do so, we may extend the mapping g from Lemma 10 to a bijection between U′_{n} and V′_{n} as follows. Let δ ∈ U′_{n} for some n ≥ 1. Then δ may be expressed sequentially in the form δ = (1δ^{(1)}1)(1δ^{(2)}1) ⋯ (1δ^{(s)}1) for some s ≥ 1, where δ^{(i)} for each i ∈ [s] contains no 1’s if nonempty. Note that δ ∈ U′_{n} implies δ^{(i)} ∈ U_{m_{i}}, where \frac{|δ^{(i)}|}{2} = m_{i} for some m_{i} ≥ 0. We may then apply g to each of the sections δ^{(i)} and let f(δ) = u^{2}g(δ^{(1)})d^{2} ⋯ u^{2}g(δ^{(s)})d^{2}. Note that g(δ^{(i)}) having all of its descents even implies the same for f(δ), with f(δ) containing no valleys of height one (due to all of its units being of the form u^{2}ρd^{2} for some Dyck path ρ), whence f(δ) ∈ V′_{n} for all δ. Then it is seen that f provides the desired bijection between U′_{n} and V′_{n}, which completes the proof of (19).

References

[1] P. Alexandersson, F. G. Kebede, S. A. Fufa, and D. Qiu, Pattern-avoidance and Fuss-Catalan numbers, J. Integer Sequences 26 (2023), Article 23.4.2.

[2] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc. 202 (2009).

[3] J.-C. Aval, Multivariate Fuss-Catalan numbers, Discrete Math. 308 (2008), 4660–4669.

[4] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[5] A. T. Benjamin and J. J. Quinn, An alternate approach to alternating sums: A method to DIE for, College Math. J. 39 (2008), 191–201.

[6] S. J. Dilworth and S. R. Mane, Success run waiting times and Fuss-Catalan numbers, J. Probab. Stat. 2015 (2015), Art. 482462.

[7] P. H. Edelman, Chain enumeration and non-crossing partitions, Discrete Math. 31 (1980), 171–180.

[8] J. Feng, The Hessenberg matrices and Catalan and its generalized numbers, arxiv preprint arXiv:1810.09170v1 [math.CO], 2018. Available at http://arxiv.org/abs/

1810.09170v1.

[9] T. Goy and M. Shattuck, Determinant formulas of some Toeplitz-Hessenberg matrices with Catalan entries, Proc. Indian Acad. Sci. Math. Sci. 129 (2019), Art. 46.

[10] T. Goy and M. Shattuck, Determinants of some Hessenberg-Toeplitz matrices with Motzkin number entries, J. Integer Sequences 26 (2023), Article 23.3.4.

[11] T. Goy and M. Shattuck, Hessenberg-Toeplitz matrix determinants with Schröder and Fine number entries, Carpathian Math. Publ. 15 (2023), 420–436.

[12] T. Goy and M. Shattuck, Determinants of Toeplitz-Hessenberg matrices with generalized Leonardo number entries, Ann. Math. Sil. 38 (2024), 284–313.

[13] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edition, Addison-Wesley, 1994.

[14] T.-X. He and L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Linear Algebra Appl. 532 (2017), 25–42.

[15] M. Klazar, On abab-free and abba-free set partitions, European J. Combin. 17 (1996), 53–68.

[16] T. Mansour and J. L. Ramirez, Enumerations on polyominoes determined by Fuss-Catalan words, Australas. J. Combin. 81 (2021), 447–457.

[17] M. Merca, A note on the determinant of a Toeplitz-Hessenberg matrix, Spec. Matrices 1 (2013), 10–16.

[18] S. Milne, A q-analog of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. Math. Soc. 245 (1978), 89–118.

[19] W. Młotkowski, Fuss-Catalan numbers in noncommutative probability, Doc. Math. 15 (2010), 939–955.

[20] T. Muir, The Theory of Determinants in the Historical Order of Development, Vol. 3, Dover, 1960.

[21] J. H. Przytycki and A. S. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Combin. Theory Ser. A 92 (2000), 68–76.

[22] F. Qi and B.-N. Guo, Some properties and generalizations of the Catalan, Fuss, and Fuss-Catalan numbers, in M. Ruzhansky, H. Dutta, and R. P. Agarwal, eds., Mathematical Analysis and Applications: Selected Topics, Wiley, 2018, pp. 101–133.

[23] G. R. Raney, Functional composition patterns and power series reversion, Trans. Amer. Math. Soc. 94 (1960), 441–451.

[24] A. Schuetz and G. Whieldon, Polygonal dissections and reversions of series, Involve 9 (2016), 223–236.

[25] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Available at

    https://oeis.org, 2026.

[26] R. P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, 1997.

[27] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

[28] D. Stanton and D. White, Constructive Combinatorics, Springer, 1986.

[29] H. S. Wilf, generatingfunctionology, Academic Press, 1994.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 11C20, 11B39. Keywords: Fuss-Catalan number, Raney number, Toeplitz-Hessenberg matrix, Trudi’s formula, generating function.

(Concerned with sequences \underline{A000245}, \underline{A001764}, \underline{A006013}, \underline{A007226}, \underline{A014137}, \underline{A023053}, \underline{A026674}, \underline{A047099}, \underline{A066357}, \underline{A098746}, \underline{A115143}, and \underline{A121545}.)

Received January 16 2025; revised version received January 3 2026. Published in Journal of Integer Sequences January 24 2026.

Return to Journal of Integer Sequences home page.