Determinants of Some Hessenberg–Toeplitz Matrices with Motzkin Number Entries

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

                 taras.goy@pnu.edu.ua

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

               mark.shattuck2@gmail.com

Abstract

In this paper, we find formulas for the determinants of some Hessenberg–Toeplitz matrices whose nonzero entries are derived from the Motzkin number sequence and its translates. We provide both algebraic and combinatorial proofs of our results, making use of generating functions for the former and various counting methods, such as direct enumeration, sign-changing involutions, and bijections, for the latter. In the process, it is shown that three important classes of lattice paths—namely, the Motzkin paths, the Riordan paths, and the so-called Motzkin left factors—have their cardinalities given as determinants of certain Hessenberg–Toeplitz matrices with Motzkin number entries. Further formulas are found for determinant identities involving two sequences from the On-Line Encyclopedia of Integer Sequences, which are subsequently explained bijectively.

1 Introduction

The Motzkin numbers, denoted by M_{n}, have been widely studied in enumerative and algebraic combinatorics. They are defined recursively by

M_{n} = M_{n−1} + ∑_{i=0}^{n−2} M_{i}M_{n−2−i}, n ≥ 2,

or equivalently by

M_{n} = \frac{2n + 1}{n + 2}M_{n−1} + \frac{3n − 3}{n + 2}M_{n−2}, n ≥ 2,

with initial values M_{0} = M_{1} = 1. The first several terms of the Motzkin sequence (M_{n})_{n≥0} are given by

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, ….

See sequence \underline{A001006} from the On-Line Encyclopedia of Integer Sequences (OEIS) [25] for further information on this sequence. Here we are interested in some new combinatorial aspects of Motzkin numbers related to their occurrence in certain Hessenberg–Toeplitz matrices.

Let R_{n} denote the n-th Riordan number \underline{A005043} and L_{n} the n-th term of sequence \underline{A005773} for n ≥ 0. The first ten terms of (R_{n})_{n≥0} and (L_{n})_{n≥0} are given respectively by

1, 0, 1, 1, 3, 6, 15, 36, 91, 232, … and 1, 1, 2, 5, 13, 35, 96, 267, 750, 2123, ….

The R_{n} and L_{n} are closely aligned with the Motzkin numbers in that they satisfy the simple relations M_{n} = R_{n} + R_{n+1} and M_{n} = 3L_{n+1} − L_{n+2} for n ≥ 0, which can be shown using generating functions or bijectively. The M_{n}, R_{n}, and L_{n} sequences enumerate important classes of first quadrant lattice paths in which there are three kinds of steps—up, down, and horizontal. See [5] for further combinatorial properties of the Motzkin and Riordan numbers. In establishing our results, we will make use of their (ordinary) generating function formulas

M(x) := ∑_{n≥0} M_{n}x^{n} = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}} ,

R(x) := ∑_{n≥0} R_{n}x^{n} = \frac{1 + x − \sqrt{1 − 2x − 3x^{2}}}{2x(1 + x)} ,

and

L(x) := ∑_{n≥0} L_{n}x^{n} = \frac{3x − 1 − \sqrt{1 − 2x − 3x^{2}}}{6x − 2} .

A variety of different parameters have been considered on Motzkin paths in the literature; see, e.g., [3, 4, 8, 9, 10, 12, 13, 22, 23, 24].

On the other hand, relatively little has been written on determinants of matrices with Motzkin number entries. The main results in this direction are those of Aigner [1], who showed that the determinant of the Hankel matrix (M_{i+j−2})_{i,j=1}^{n} is 1 for all n, while the determinant of the Hankel matrix (M_{i+j−1})_{i,j=1}^{n} is 1, 0, −1, −1, 0, 1 for n = 1, …, 6, repeating modulo 6 thereafter. Later, in [7], Cameron and Yip used combinatorial methods to evaluate Hankel determinants for the sequence of sums of consecutive t-Motzkin numbers.

In [14], the authors found determinants of several families of Toeplitz–Hessenberg matrices having various subsequences of the Catalan sequence for the nonzero entries. These determinant formulas could also be expressed equivalently as identities involving sums of products of Catalan numbers and multinomial coefficients. Further comparable results featuring combinatorial arguments have been found for the generalized Fibonacci, tribonacci, and tetranacci numbers [15, 16, 17].

This paper is organized as follows. In the next section, we find formulas giving algebraic proofs for the determinants of five Hessenberg–Toeplitz matrices whose entries are derived from translates of the Motzkin number sequence. In particular, we find new expressions involving determinants for the sequences M_{n}, R_{n}, and L_{n}. An equivalent multi-sum version of these expressions may be given using a result known as Trudi’s formula (see Lemma 1 below). Further formulas are found for determinants of matrices with entries from the R_{n} and L_{n} sequences and a related recurrence for sequence \underline{A109190} is shown. In the third section, we provide combinatorial proofs of all of our results where we make use of the definition of an n × n determinant as a signed sum over the set of permutations of [n] = {1, …, n}. We employ various counting techniques, perhaps most notably sign-changing involutions, in providing these proofs and draw upon the combinatorial interpretations of M_{n}, R_{n}, and L_{n} as enumerators of certain classes of lattice paths.

2 Determinant formulas of matrices with Motzkin number entries

A Hessenberg–Toeplitz matrix is one having 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. The following result is known as Trudi’s formula [20, Theorem 1] and gives a multinomial expansion of det(A_{n}) in terms of a sum of products of the a_{i}.

Lemma 1. Let n be a positive integer. Then

det(A_{n}) = ∑_{s̃=n}(−a_{0})^{n−|s|}\binom{|s|}{s_{1}, …, s_{n}}a_{1}^{s_{1}}a_{2}^{s_{2}} ⋯ a_{n}^{s_{n}},  (2)

where \binom{|s|}{s_{1},...,s_{n}} = \frac{|s|!}{s_{1}!s_{2}!···s_{n}!}, s̃ = s_{1} + 2s_{2} + ⋯ + ns_{n}, |s| = s_{1} + s_{2} + ⋯ + s_{n}, s_{i} ≥ 0. Equivalently, we have

det(A_{n}) = ∑_{k=1}^{n}(−a_{0})^{n−k} ∑_{\begin{matrix}i_{1},...,i_{k}≥1 \\ i_{1}+i_{2}+···+i_{k}=n \end{matrix}} a_{i_{1}}a_{i_{2}} ⋯ a_{i_{k}}.

The case a_{0} = 1 of Trudi’s formula is known as Brioschi’s formula [21]. Note that the sum in (2) may be regarded as being over the set of partitions of the positive integer n. Here, we will focus on some cases of det(A_{n}) when a_{0} = ±1. To simplify notation, we will write D_{±}(a_{1}, a_{2}, …, a_{n}) in place of det(A_{n}(±1; a_{1}, a_{2}, …, a_{n})).

Let C_{n} = \frac{1}{n+1} \binom{2n}{n} denote the n-th Catalan number [25, \underline{A000108}]. We have the following Hessenberg–Toeplitz determinant formulas and the corresponding multi-sum Motzkin number identities upon applying (2).

Theorem 2. We have

D_{+}(M_{0}, M_{1}, …, M_{n−1}) = (−1)^{n−1}R_{n−1} = ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}C_{k},  (3)

D_{+}(M_{1}, M_{2}, …, M_{n}) = (−1)^{n−1}M_{n−2} = ∑_{k=1}^{n−1}(−1)^{k}\binom{n − 2}{k − 1}C_{k}, n ≥ 2,  (4)

D_{−}(M_{0}, M_{1}, …, M_{n−1}) = L_{n} = ∑_{k=0}^{n−1}(−1)^{n−k−1}(2k + 1)\binom{n − 1}{k}C_{k},  (5)
D_{−}(M_{1}, M_{2}, …, M_{n}) = \frac{1}{2} \underline{A111961}(n),  (6)
D_{+}(M_{2}, M_{3}, …, M_{n+1}) = (−1)^{n−1}R_{n−1}, n ≥ 2,  (7)

which hold for n ≥ 1 unless stated otherwise.

Corollary 3. We have

∑_{s̃=n}(−1)^{|s|−1}\binom{|s|}{s_{1}, …, s_{n}}M_{0}^{s_{1}}M_{1}^{s_{2}} ⋯ M_{n−1}^{s_{n}} = R_{n−1},  (8)

∑_{s̃=n}(−1)^{|s|−1}\binom{|s|}{s_{1}, …, s_{n}}M_{1}^{s_{1}}M_{2}^{s_{2}} ⋯ M_{n}^{s_{n}} = M_{n−2}, n ≥ 2,  (9)

∑_{s̃=n} \binom{|s|}{s_{1}, …, s_{n}}M_{0}^{s_{1}}M_{1}^{s_{2}} ⋯ M_{n−1}^{s_{n}} = L_{n},  (10)

∑_{s̃=n} \binom{|s|}{s_{1}, …, s_{n}}M_{1}^{s_{1}}M_{2}^{s_{2}} ⋯ M_{n}^{s_{n}} = \frac{1}{2} \underline{A111961}(n),  (11)

∑_{s̃=n}(−1)^{|s|−1}\binom{|s|}{s_{1}, …, s_{n}}M_{2}^{s_{1}}M_{3}^{s_{2}} ⋯ M_{n+1}^{s_{n}} = R_{n−1}, n ≥ 2,  (12)

which hold for n ≥ 1 unless stated otherwise.

The identities in the preceding theorem and corollary are equivalent, so we need only to prove the former where we will draw upon (2).

Proof. We proceed to show (3)–(7) and will make use of generating functions. Let f(x) = ∑_{n≥1} det(A_{n})x^{n}, where A_{n} is of the form (1). By Trudi’s formula, we have

f (−\frac{x}{a_{0}} ) = ∑_{n≥1} x^{n} ∑_{s̃=n} \binom{|s|}{s_{1}, …, s_{n}} (−\frac{a_{1}}{a_{0}} )^{s_{1}} ⋯ (−\frac{a_{n}}{a_{0}} )^{s_{n}} = \frac{h(x)}{1 − h(x)},

where h(x) := −\frac{1}{a_{0}} ∑_{i≥1} a_{i}x^{i}, upon considering the contribution from each term of the expansion \frac{h(x)}{1−h(x)} = h(x) + h^{2}(x) + h^{3}(x) + · · ·. Thus, we get

f(x) = \frac{g(x)}{1 − g(x)},

where g(x) := ∑_{i≥1}(−a_{0})^{i−1}a_{i}x^{i}.

We now consider various cases on a_{i}. First suppose a_{i} = M_{i−r} for i ≥ 1, where r ≥ 1 is fixed and M_{j} := 0 if j < 0. In this case, we have

g(x) = ∑_{i≥1}(−a_{0})^{i−1}M_{i−r}x^{i} = ∑_{i≥0}(−a_{0})^{i+r−1}M_{i}x^{i+r} = (−a_{0})^{r−1}x^{r} ∑_{i≥0} M_{i}(−a_{0}x)^{i}
= (−a_{0})^{r−1}x^{r}M(−a_{0}x).

If r = a_{0} = 1 in the preceding, then we get

g(x) = xM(−x) = \frac{1 + x − \sqrt{1 + 2x − 3x^{2}}}{2x}

and

∑_{n≥1} D_{+}(M_{0}, …, M_{n−1})x^{n} = f(x) = \frac{g(x)}{1 − g(x)} = \frac{x − 1 + \sqrt{1 + 2x − 3x^{2}}}{2(1 − x)}

= xR(−x) = ∑_{n≥1}(−1)^{n−1}R_{n−1}x^{n},

which yields the first part of formula (3). If r = 1 and a_{0} = −1, then we get g(x) = xM(x) and

∑_{n≥1} D_{−}(M_{0}, …, M_{n−1})x^{n} = f(x) = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{3x − 1 + \sqrt{1 − 2x − 3x^{2}}}

= L(x) − 1 = ∑_{n≥1} L_{n}x^{n},

which yields the first part of (5).

Now suppose a_{i} = M_{i+r}, where r ≥ 0. In this case, we have

g(x) = ∑_{i≥1}(−a_{0})^{i−1}M_{i+r}x^{i} = −\frac{1}{a_{0}} ∑_{i≥r+1} M_{i}(−a_{0}x)^{i−r}

= \frac{1}{(−a_{0})^{r+1}x^{r}} (M(−a_{0}x) − ∑_{i=0}^{r} M_{i}(−a_{0}x)^{i}).

If r = 0 and a_{0} = 1 in the preceding, then

g(x) = 1 − M(−x) = \frac{2x^{2} − x − 1 + \sqrt{1 + 2x − 3x^{2}}}{2x^{2}}

and

f(x) = \frac{g(x)}{1 − g(x)} = \frac{2x^{2} − x − 1 + \sqrt{1 + 2x − 3x^{2}}}{x + 1 − \sqrt{1 + 2x − 3x^{2}}} .

Hence, we have

∑_{n≥2} D_{+}(M_{1}, …, M_{n})x^{n} = f(x) − x = \frac{\sqrt{1 + 2x − 3x^{2}} − x − 1}{2}

= ∑_{n≥2}(−1)^{n−1}M_{n−2}x^{n},

which yields the first part of (4). If r = 0 and a_{0} = −1, then g(x) = M(x) − 1 and

f(x) = \frac{M(x) − 1}{2 − M(x)} = \frac{K(x) − 1}{2} ,

where

K(x) := ∑_{n≥0} \underline{A111961}(n)x^{n} = \frac{1}{\sqrt{1 − 2x − 3x^{2}} − x} ,

which implies (6). If r = a_{0} = 1, then

g(x) = \frac{1}{x}(M(−x) − 1 + x) = \frac{1 + x − 2x^{2} + 2x^{3} − \sqrt{1 + 2x − 3x^{2}}}{2x^{3}}

and

f(x) = \frac{1 + x − 2x^{2} + 2x^{3} − \sqrt{1 + 2x − 3x^{2}}}{2x^{2} − x − 1 + \sqrt{1 + 2x − 3x^{2}}} .

Hence, we have

∑_{n≥2} D_{+}(M_{2}, …, M_{n+1})x^{n} = f(x) − 2x = \frac{x − 1 + \sqrt{1 + 2x − 3x^{2}}}{2(1 − x)} − x

= ∑_{n≥2}(−1)^{n−1}R_{n−1}x^{n},

which implies (7). Finally, the second parts of (3)–(5) may be shown by computing the respective generating functions using the formula ∑_{n≥0} C_{n}x^{n} = \frac{1−\sqrt{1−4x}}{2x}, the details of which we leave to the reader.

The R_{n} and L_{n} sequences satisfy the following further determinant identities. Theorem 4. We have

D_{−}(R_{0}, R_{1}, …, R_{n−1}) = M_{n−1},  (13)
D_{+}(R_{0}, R_{1}, …, R_{n−1}) = (−1)^{n−1}\underline{A344507}(n − 1),  (14)
D_{−}(R_{1}, R_{2}, …, R_{n}) = \frac{1}{2} \underline{A109190}(n),  (15)
D_{+}(R_{1}, R_{2}, …, R_{n}) = (−1)^{n−1}M_{n−2}, n ≥ 2,  (16)
D_{+}(R_{3}, R_{4}, …, R_{n+2}) = (−1)^{n−1}M_{n−2}, n ≥ 3,  (17)

which hold for n ≥ 1 unless stated otherwise. Theorem 5. We have

D_{−}(L_{1}, L_{2}, …, L_{n}) = \underline{A059738}(n − 1),  (18)
D_{+}(L_{1}, L_{2}, …, L_{n}) = (−1)^{n−1}M_{n−1},  (19)
D_{−}(L_{2}, L_{3}, …, L_{n+1}) = u_{n},  (20)
D_{+}(L_{2}, L_{3}, …, L_{n+1}) = (−1)^{n−1}M_{n−2}, n ≥ 2,  (21)

which hold for n ≥ 1 unless stated otherwise, where u_{n} denotes the sequence satisfying

u_{n} = 4u_{n−1} + M_{n−2} + 2 ∑_{i=0}^{n−3} M_{i}u_{n−2−i}

for n ≥ 3, with u_{1} = 2 and u_{2} = 9.

Proof. Proofs similar to those presented above for (3)–(7) may be given for (13)–(21). Alternatively, two of the preceding formulas follow from the previous identities and an inversion theorem [18, Lemma 4], which can be paraphrased as follows:

Let (b_{n})_{n≥0} be the sequence defined by b_{n} = det(A_{n}) for n ≥ 1 with b_{0} = 1, where A_{n} is given by (1) with a_{0} = 1. Then a_{n} = det(B_{n}) for n ≥ 1, where B_{n} is the Hessenberg–Toeplitz matrix associated with b_{0}, …, b_{n}.

Note that formulas (13) and (19) then follow respectively from (3) and (5) since

D_{+}(M_{0}, …, M_{n−1}) = (−1)^{n−1}R_{n−1} if and only if
D_{−}(R_{0}, …, R_{n−1}) = D_{+}(R_{0}, −R_{1}, …, (−1)^{n−1}R_{n−1}) = M_{n−1}

and

D_{+}(L_{1}, …, L_{n}) = (−1)^{n−1}M_{n−1} if and only if
D_{−}(M_{0}, …, M_{n−1}) = D_{+}(M_{0}, −M_{1}, …, (−1)^{n−1}M_{n−1}) = L_{n}.

The sequence \underline{A109190} used in formula (15) above for D_{−}(R_{1}, …, R_{n}) was conjectured previously by Mathar to satisfy a certain linear fourth-order recurrence (see discussion in the OEIS entry). We close this section by providing a proof of this conjectured recurrence.

Proposition 6. The sequence a_{n} = \underline{A109190}(n) is given recursively by

na_{n} = (4n − 3)a_{n−1} + 3(n − 1)a_{n−2} − 2(7n − 15)a_{n−3} − 12(n − 3)a_{n−4}, n ≥ 4, (22)

with initial values a_{0} = 1, a_{1} = 0, a_{2} = a_{3} = 2. Hence, if d_{n} = D_{−}(R_{1}, …, R_{n}), then d_{n} satisfies the same recurrence for n ≥ 5, but with initial values d_{1} = 0, d_{2} = d_{3} = 1, d_{4} = 4.

Proof. The second statement follows from the first and (15), so we need only show the first. Let

f(x) := ∑_{n≥0} a_{n}x^{n} = \frac{1}{x + \sqrt{1 − 2x − 3x^{2}}} .

Then we have

∑_{n≥4} (na_{n} − (4n − 3)a_{n−1} − 3(n − 1)a_{n−2} + 2(7n − 15)a_{n−3} + 12(n − 3)a_{n−4})x^{n}

= x(f′ − 4x − 6x^{2}) − x(f + 4xf′ − 1 − 18x^{2}) − 3x^{2}(f + xf′ − 1) + 2x^{3}(6f + 7xf′ − 6)

+ 12x^{4}(f + xf′) = x(1 − 4x − 3x^{2} + 14x^{3} + 12x^{4})f′ − x(1 + 3x − 12x^{2} − 12x^{3})f + x − x^{2}.

Recurrence (22) holds if and only if the last quantity is zero, i.e.,

(1 − 4x − 3x^{2} + 14x^{3} + 12x^{4})f′ = (1 + 3x − 12x^{2} − 12x^{3})f + x − 1 .  (23)

Now observe that f′ = (\frac{1+3x−\sqrt{1−2x−3x^{2}}}{\sqrt{1−2x−3x^{2}}} )f^{2} so that (23) is equivalent to

(1 − 4x − 3x^{2} + 14x^{3} + 12x^{4})(1 + 3x−\sqrt{1 − 2x − 3x^{2}})f^{2}
= (1 + 3x − 12x^{2} − 12x^{3})\sqrt{1 − 2x − 3x^{2}}f + (x − 1)\sqrt{1 − 2x − 3x^{2}}. (24)

Note the factorization 12x^{4} + 14x^{3} − 3x^{2} − 4x + 1 = (4x^{2} + 2x − 1)(3x^{2} + 2x − 1) and that f may be rewritten as f = \frac{x−\sqrt{1−2x−3x^{2}}}{4x^{2}+2x−1} . Upon clearing fractions, we then have that (24) is equivalent to

− (1 − 2x − 3x^{2})(1 + 3x − \sqrt{1 − 2x − 3x^{2}})(1 − 2x − 2x^{2} − 2x\sqrt{1 − 2x − 3x^{2}})

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

i.e.,

− (1 − 2x − 3x^{2})(1 + 3x − 12x^{2} − 12x^{3} − (1 + 4x^{2})\sqrt{1 − 2x − 3x^{2}})
= −(1 − 2x − 3x^{2})(1 + 3x − 12x^{2} − 12x^{3})
+ (x(1 + 3x − 12x^{2} − 12x^{3}) + (x − 1)(4x^{2} + 2x − 1))\sqrt{1 − 2x − 3x^{2}} .

The last equation is easily verified, which completes the proof of (22).

3 Combinatorial proofs

In this section, we give combinatorial proofs of formulas (3)–(7) and (13)–(21) above. Before doing so, let us recall the combinatorial interpretations of several integer sequences which we will make use of here and specify some further terminology. Let M_{n} denote the set of lattice paths (called Motzkin paths) from the origin to the point (n, 0) that never dip below the x-axis using u = (1, 1), d = (1, −1), and h = (1, 0) steps. Then M_{n} = |M_{n}| for all n ≥ 0, where M_{0} is understood to consist of the empty path of length zero. The number of steps in a Motzkin path λ will be denoted by |λ|. A u step (d step) is said to terminate at height j if it joins the points (i − 1, j − 1) and (i, j) (the points (i − 1, j + 1) and (i, j)) for some i. By the level of an h step within a member of M_{n}, we are referring to the y-coordinate of the two points in the path connected by the h. A low h will refer to an h step at level zero (i.e., one that begins and ends on the x-axis). Let M_{n}^{∗} denote the subset of M_{n} whose members contain no low h’s. Then it is well-known that |M_{n}^{∗}| = R_{n} for all n ≥ 0 (see, e.g., the discussion in \underline{A005043}), and members of M_{n}^{∗} are referred to as Riordan paths.

A member of M_{2n} that contains no h steps is called a Dyck path (of semilength n); i.e., it is a lattice path starting at the origin and terminating on the x-axis with 2n steps consisting of u’s and d’s that never goes below the x-axis. Then C_{n} enumerates the set C_{n} of Dyck paths of semilength n. Let L_{n} for n ≥ 1 denote the set of lattice paths starting at the origin and terminating on the line x = n − 1 using u, d, and h steps that never go below the x-axis (which are referred to as Motzkin left factors [2, p. 111]). Note that |L_{n}| = L_{n} for all n ≥ 1. By an internal return within a Motzkin path of length n, we mean a point (i, 0) on the x-axis with 0 < i < n where a d or h step terminates. A member of M_{n} for which there are no internal returns will be described as being primitive. Note that λ ∈ M_{n} for n ≥ 2 is primitive if and only if λ = uλ′d for some λ′ ∈ M_{n−2}, with the single member of M_{1} also assumed to be primitive. Finally, a unit of a lattice path will refer to a section lying between two consecutive returns to the x-axis or to the section lying to the left of the first return. Thus, a member of M_{n} is primitive if and only if it contains exactly one unit.

When computing the determinant of an n × n Hessenberg–Toeplitz matrix using the definition of a determinant as a signed sum over the set of permutations σ of [n], one need consider only those σ each of whose cycles when expressed disjointly with the smallest element first in each cycle comprises a set of consecutive integers in increasing order. Such σ are in one-to-one correspondence with the compositions of n, upon identifying the various cycle lengths with parts of a composition, and hence they number 2^{n−1}. Thus, the determinant sum for a matrix A_{n} of the form (1) may be regarded as a weighted sum over the set of compositions of n. In this sum when a_{0} = 1, a part of size r ≥ 1 has (signed) weight given by (−1)^{r−1}a_{r} (regardless of its position) and the weight of a composition is the product of the weights of its constituent parts. The sign of a composition is then given by (−1)^{n−m}, where m denotes the number of its parts. On the other hand, when a_{0} = −1, every part of size r is weighed by a_{r} and each term in the determinant sum for A_{n} is non-negative assuming a_{i} ≥ 0 for i ≥ 1. Equivalently, when one computes det(A_{n}) where a_{0} = −1, one is in fact finding the permanent of the matrix obtained from A_{n} by replacing a_{0} = −1 with a_{0} = 1. For other examples of weighted composition sums with combinatorial weights, see, e.g., [19] as well as the related literature on n-color compositions.

To find a combinatorial explanation of a purported formula for det(A_{n}) when a_{0} = 1, we make frequent use of sign-changing involutions defined on a (signed) structure S whose sum of signs coincides with det(A_{n}), which has the effect of cancelling out some of the terms in the formula. We then show that the sum of the signs of the remaining unpaired members of S (often referred to as the set of survivors of the involution) is given by the formula for det(A_{n}), which is clear in several instances or requires a further enumeration in others. When a_{0} = −1, then all terms in the expansion of det(A_{n}) are non-negative and some structure T is found whose cardinality is seen to coincide with det(A_{n}). An expression for the cardinality of T is subsequently found establishing its equality with det(A_{n}), which is done by a direct enumeration and/or bijection.

We now provide combinatorial proofs of the formulas from Theorems 2, 4, and 5 above.

3.1 Proof of Eq. (3)

We first develop a combinatorial interpretation for D_{+}(M_{0}, …, M_{n−1}). Let σ denote a composition of n with parts σ_{1}, …, σ_{m} for some m ≥ 1. For each part σ_{i}, we overlay a lattice path λ_{i} ∈ M_{σ_{i}−1} followed by an h. We then color any low h within λ_{i} black and each appended h step white. Then let λ = λ_{1}hλ_{2}h ⋯ λ_{m}h be the (colored) Motzkin path obtained as the concatenation of the paths λ_{i}h for 1 ≤ i ≤ m. Let A_{n} denote the set of all lattice paths that arise when one considers all possible compositions σ of n. Define the sign of λ as (−1)^{n−m}, where m denotes the number of white low h steps of λ (equivalently, the number of parts in the underlying composition σ). Then, by the interpretation of the determinant of a Hessenberg–Toeplitz matrix as a (signed) weighted sum over the set of compositions of n, we have that D_{+}(M_{0}, …, M_{n−1}) gives the sum of the signs of all members of A_{n}.

Note that members of A_{n} must end in a white h step. We then define a sign-changing involution on A_{n} by switching the color of the rightmost non-terminal low h step. This operation is not defined on the subset A_{n}^{∗} of A_{n} consisting of those paths whose only low h step is the terminal (white) h. Note that members of A_{n}^{∗} and M_{n−1}^{∗} are clearly synonymous, upon deleting the terminal h, with each member of A_{n}^{∗} having sign (−1)^{n−1}. Thus, we get D_{+}(M_{0}, …, M_{n−1}) = (−1)^{n−1}R_{n−1}. To establish the other formula in (3), we must show equivalently for all n ≥ 0 that R_{n} = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}C_{n−k}. Let B_{n} denote the subset of C_{n} consisting of those lattice paths ρ = ρ_{1}ρ_{2} ⋯ ρ_{2n} ∈ C_{n} such that ρ_{2i−1}ρ_{2i} ≠ ud for all 1 ≤ i ≤ n, i.e., there are no peaks at odd height. By an inclusion-exclusion argument considering the number k of peaks at odd height within a member of C_{n}, we have |B_{n}| = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}C_{n−k}. On the other hand, by the bijection from [6] between B_{n} and M_{n}^{∗} (see also [26]), we have |B_{n}| = R_{n}, which completes the proof of (3).

3.2 Proof of Eq. (4)

Let σ be a composition of n with parts σ_{1}, …, σ_{m}. On each σ_{i}, we overlay λ_{i} ∈ M_{σ_{i}} and then let λ = λ_{1} ⋯ λ_{m}. Further, we mark the final step of each subpath λ_{i} and define the sign of λ as (−1)^{n−m}. Let D_{n} denote the set of all the members of M_{n} so marked. Then we have that D_{+}(M_{1}, …, M_{n}) gives the sum of the signs of the members of D_{n}. Consider the rightmost non-terminal step that is either a (i) low h or (ii) d step terminating on the x-axis. We then either mark this step if it is unmarked or remove the marking from it if marked. This operation yields an involution on D_{n} that is not defined on the primitive members of D_{n}, which number M_{n−2} and are each of sign (−1)^{n−1}. This establishes the first formula in (4). For the second, we show equivalently that M_{n−1} = ∑_{k=0}^{n−1}(−1)^{k}\binom{n−1}{k}C_{n−k}, upon replacing n by n+1. Let E_{n} denote the set of Dyck paths ρ = ρ_{1}ρ_{2} ⋯ ρ_{2n} ∈ C_{n} in which ρ_{2i}ρ_{2i+1} ≠ ud for all 1 ≤ i ≤ n−1. By an inclusion-exclusion argument, we have |E_{n}| = ∑_{k=0}^{n−1}(−1)^{k}\binom{n−1}{k}C_{n−k}. By the bijection from [6], we have |E_{n}| = M_{n−1}, as desired, which completes the proof.

Let A_{n} be as in the proof above for (3). Note that, by changing each 1 to −1 along the superdiagonal of A_{n}(1; M_{0}, …, M_{n−1}), one introduces an extra sign factor to each term in the determinant expansion of D_{+}(M_{0}, …, M_{n−1}) that is equal to the sign of the member of A_{n} corresponding to the term. Thus, D_{−}(M_{0}, …, M_{n−1}) gives |A_{n}| instead of the sum of the signs of members of A_{n}. Let M′_{n} denote the set of colored Motzkin paths of length n in which each low h comes in one of two colors (say blue and green). Then members of A_{n+1} are synonymous with members of M′_{n}, and to establish the first formula, it suffices to define a bijection between M′_{n} and L_{n+1} for n ≥ 0. Given ρ ∈ M′_{n}, replace each green low h with u, leaving all other steps the same and ignoring the coloring of any blue h. Let ρ̃ denote the resulting lattice path and note that ρ̃ ∈ L_{n+1}. Then the mapping ρ ↦ ρ̃ is reversible, upon considering the final height t of ρ̃ and the rightmost u step terminating at a height i for 1 ≤ i ≤ t. Thus, we have |M′_{n}| = L_{n+1}, which implies the first formula in (5).

For the second formula in (5), we show

|M′_{n}| = ∑_{k=0}^{n}(−1)^{n−k}(2k + 1)\binom{n}{k}C_{k},  n ≥ 0.  (25)

Note that the right side of (25) may be rewritten as

∑_{k=0}^{n}(−1)^{k}(2(n − k) + 1)\binom{n}{k}C_{n−k} = 2n ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}C_{n−k} + ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}C_{n−k}.

In the combinatorial proofs of (3) and (4) above, it was seen that

∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}C_{n−k} = M_{n−1} and ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}C_{n−k} = R_{n}.

Thus, to establish (25), we need to show

|M′_{n}| = 2nM_{n−1} + R_{n}, n ≥ 0.  (26)

Since there are R_{n} members of M′_{n} that contain no low h’s, to show (26), we must argue that there are 2nM_{n−1} members of M′_{n} that contain at least one low h. Clearly, we may assume n ≥ 1 in (26). Let J_{n} denote the set of Motzkin paths of length n wherein there is at least one h step (at any level) such that exactly one of the h steps is colored either blue or green. Upon choosing the color and relative position of the colored h, we have |J_{n}| = 2nM_{n−1}. Let K_{n} denote the subset of M′_{n} whose members contain at least one low h. To complete the proof of (26), it suffices to define a bijection between J_{n} and K_{n}.

In order to do so, we consider the level ℓ, where ℓ ≥ 0, of the colored h within λ ∈ J_{n}. Then λ can be decomposed as

λ = \begin{cases}ρ_{0}u ⋯ ρ_{ℓ−1}uρ_{ℓ}\underline{h}ρ′_{ℓ}d ⋯ ρ′_{1}dρ′_{0}, & if ℓ ≥ 1; \\ ρ_{0}\underline{h}ρ′_{0}, & if ℓ = 0, \end{cases}  (27)

[figure]

Figure 1: Decomposition of colored Motzkin path λ ∈ J_{34}

where ρ_{0}, …, ρ_{ℓ}, ρ′_{0}, …, ρ′_{ℓ} are all (possibly empty) Motzkin paths and the colored h is underlined. Pictured above in Figure 1 is the decomposition of λ ∈ J_{n} where n = 34 and ℓ = 2, in which the ρ_{i} and ρ′_{i} sections for 0 ≤ i ≤ 2 are separated by red u and by red d steps, respectively, and the colored h is blue as indicated. We transform λ as given in (27) to a member of K_{n} as follows. First replace each u directly preceding a ρ_{i} section with an h of the same color as that of the underlined h in λ and do the same for each d directly following some ρ′_{j}. For each ρ_{i} and ρ′_{j} where 0 ≤ i, j ≤ ℓ, we color all low h steps contained therein with the color not used for the underlined h. Finally, we keep the color of the underlined h in λ the same (deleting the underlining). Let λ′ denote the resulting lattice path and one may verify λ′ ∈ K_{n}. Further, it must be the case that at least one of the colors is applied to an odd number of h steps in λ′ as an equal number of u and d in λ were converted to h with the same color as that of the underlined h. Pictured in Figure 2 is λ′ ∈ K_{34} corresponding to the λ illustrated above.

[figure]

Figure 2: The corresponding λ′ ∈ K_{34}

Let K_{n}^{(e,o)} denote the subset of K_{n} for which there are an even number of blue h and an odd number of green h steps, with the obvious analogous meanings for K_{n}^{(o,e)}, K_{n}^{(e,e)}, and K_{n}^{(o,o)}. Let J_{n}^{(1)} and J_{n}^{(2)} denote the subsets of J_{n} in which the colored h step is blue or green, respectively. Then the mapping λ ↦ λ′ is reversible when restricted to either J_{n}^{(1)} or J_{n}^{(2)} and hence yields a bijection between the sets J_{n}^{(1)} and K_{n}^{(o,e)} ∪ K_{n}^{(o,o)} as well as between J_{n}^{(2)} and K_{n}^{(e,o)} ∪ K_{n}^{(o,o)}. Thus, we get

|J_{n}| = |J_{n}^{(1)}| + |J_{n}^{(2)}| = |K_{n}^{(e,o)}| + |K_{n}^{(o,e)}| + 2|K_{n}^{(o,o)}|.  (28)

Now we have |K_{n}^{(e,e)}| = |K_{n}^{(o,o)}|, upon changing the color of the rightmost low h step within a member of K_{n}^{(e,e)} or K_{n}^{(o,o)}. Note that since each member of K_{n} contains at least one low h, the preceding operation is well-defined and bijective. Thus, |K_{n}^{(e,e)}| = |K_{n}^{(o,o)}|, together with (28), implies |J_{n}| = |K_{n}|, as desired, which completes the proof.

Let D_{n} be as in the proof of (4) and it is seen that D_{−}(M_{1}, …, M_{n}) = |D_{n}|. Let d_{n} = 2|D_{n}| for n ≥ 1 with d_{0} = 1 so that d_{n} enumerates the set of all marked Motzkin paths of length n wherein some subset (possibly empty) of the returns to the x-axis (including the final return) is marked. We make use of the symbolic enumeration method (see, e.g., [11]) and let D = D(x) := ∑_{n≥0} d_{n}x^{n}. We then have D = 1 + 2xD + 2x^{2}DM, where M = M(x), which follows from considering whether a nonempty lattice path σ counted by D can be expressed as σ = hσ′ or σ = uτdσ′′ such that σ′, σ′′ are paths of the form enumerated by d_{n} and τ is a Motzkin path. (Equivalently, we have the combinatorial recurrence d_{n} = 2d_{n−1} + 2 ∑_{i=0}^{n−2} M_{i}d_{n−2−i} for n ≥ 2, with d_{0} = 1 and d_{1} = 2.) Solving for D gives

D = \frac{1}{1 − 2x − 2x^{2}M} = \frac{1}{\sqrt{1 − 2x − 3x^{2}} − x} = ∑_{n≥0} \underline{A111961}(n)x^{n},

which implies (6).

3.5 Proof of Eq. (7)

Given n ≥ 2 and 1 ≤ k ≤ n, let G_{n,k} denote the set of k-tuples (λ_{1}, …, λ_{k}), where each λ_{i} is a Motzkin path of length at least two and ∑_{i=1}^{k} |λ_{i}| = n + k. Define the sign of λ ∈ G_{n,k} as (−1)^{n−k} and let G_{n} = ∪_{k=1}^{n}G_{n,k}. Then D_{+}(M_{2}, …, M_{n+1}) gives the sum of the signs of all members of G_{n}. To prove (7), we define a sign-changing involution on G_{n} in several steps as follows. Throughout, we let λ = (λ_{1}, …, λ_{k}) denote a member of G_{n,k} for some k ∈ [n].

First suppose that the last step of λ_{k} is h, with λ_{k} = ωh for some nonempty Motzkin path ω. If |λ_{k}| ≥ 3, then replace the final component λ_{k} of λ with the two components λ_{k} = ω and λ_{k+1} = h^{2}. If |λ_{k}| = 2, whence λ_{k} = h^{2} and n ≥ 2 implies k ≥ 2, then delete the final component of λ and append an h to the path λ_{k−1}. These two operations, taken together, define a sign-changing involution on the subset of G_{n} consisting of those members in which the final step of the final component path is an h, and thus their contribution towards the determinant D_{+}(M_{2}, …, M_{n+1}) is zero.

Henceforth, assume that the final component λ_{k} within λ ends in d. First suppose λ_{k} has one of the following four forms, where |λ_{k}| ≥ 3 and k ≥ 1:

(i) λ_{k} = hα, where α contains no low h’s,
(ii) λ_{k} = h^{2}β, where β contains no low h’s,
(iii) λ_{k} = uγd, where γ is a Motzkin path that has at least one low h,
(iv) λ_{k} has no low h, but does have at least one internal return to the x-axis.

Note that in case (iii), the lattice path λ_{k} has no internal returns to the x-axis, but contains an h at level one. We divide the case when |λ_{k}| = 2, and hence λ_{k} = ud with k ≥ 2, into the following four subcases based on the penultimate component λ_{k−1}:

(a) λ_{k−1} does not contain a low h,
(b) λ_{k−1} = hδ, where δ does not contain a low h,
(c) λ_{k−1} = hδ, where δ contains a low h,
(d) λ_{k−1} starts with u and has a low h.

We now pair cases (i)–(iv) with (a)–(d), respectively, as follows. If (i) occurs, then delete the initial h from λ_{k} and replace λ_{k} with the two components λ_{k} = α and λ_{k+1} = ud. If (ii) holds, then replace λ_{k} = h^{2}β with the components λ_{k} = hβ and λ_{k+1} = ud. If (iii), then replace λ_{k} = uγd with λ_{k} = hγ and λ_{k+1} = ud. Finally, if (iv), then consider the decomposition λ_{k} = ρ′ρ′′, where ρ′ and ρ′′ are both nonempty, ρ′ contains no low h’s and ρ′′ is primitive. Further, let ρ′′ = uσd, where σ is possibly empty with no restrictions. In this case, we replace the final component λ_{k} with λ_{k} = ρ′hσ and λ_{k+1} = ud. Moreover, it is understood in each case that all other components of λ are to remain unchanged. Then it is seen that each of the four mappings described above is reversible and changes the sign as the number of components increases by one in each case. Note that in order to reverse the mapping for case (iv), one needs to consider the position of the leftmost low h in the penultimate component within a member of G_{n} for which (d) above applies.

So the remaining cases for when λ_{k} ends in d are as follows:

(I) λ_{k} contains a low h, with the last low h occurring in the third step or beyond,
(II) λ_{k} is primitive and has no h at level one, with |λ_{k}| > 2 and k ≥ 2,
(III) k = 1 and λ_{1} ∈ M_{n+1} is primitive and has no h at level one.

We pair members of G_{n} for which (I) or (II) applies as follows. If (I), then write λ_{k} = τhτ′, where |τ| ≥ 2 and τ′ contains no low h’s. Note that the assumption that λ_{k} ends in d implies τ′ ≠ ∅. We then replace λ_{k} = τhτ′ with the two components λ_{k} = τ and λ_{k+1} = uτ′d, keeping all other components of λ the same. Note that λ_{k+1} is primitive and has no h at level one since τ′ does not contain a low h, whence (II) holds for the resulting member of G_{n}. Further, this operation is seen to be reversible and always changes the sign.

Thus, each member of G_{n} has been paired with another of opposite sign except for those where (III) above applies, each of which has sign (−1)^{n−1}. Upon deleting the initial u and the final d, members of G_{n} in (III) are synonymous with Riordan paths of length n − 1. This implies D_{+}(M_{2}, …, M_{n+1}) = (−1)^{n−1}R_{n−1} for n ≥ 2, as desired.

3.6 Proofs of Eqs. (13)–(16)

To show (13), let A_{n} be as in the proof of (3) and note that D_{−}(R_{0}, …, R_{n−1}) enumerates the subset A′_{n} of A_{n} consisting of those λ = λ_{1}h ⋯ λ_{m}h in which each λ_{i} is a Riordan path. Upon deleting the final h, one may identify members of A′_{n} with members of M_{n−1}, which yields (13). For (14), first note that D_{+}(R_{0}, …, R_{n−1}) gives the sum of the signs of the members of A′_{n}, where the sign is defined as (−1)^{n−m}. Equivalently, we have that (−1)^{n}D_{+}(R_{0}, …, R_{n}) equals the sign-balance of the low h statistic on M_{n}, i.e.,

(−1)^{n}D_{+}(R_{0}, …, R_{n}) = ∑_{π∈M_{n}}(−1)^{μ(π)} := v_{n}, n ≥ 1,

with v_{0} = 1, where μ(π) denotes the number of low h’s in π. Let V = V (x) := ∑_{n≥0} v_{n}x^{n}. Considering whether a nonempty Motzkin path starts with h or u gives V = 1−xV +x^{2}MV, and hence

V = \frac{1}{1 + x − x^{2}M} = \frac{2}{1 + 3x + \sqrt{1 − 2x − 3x^{2}}} .

A comparison with the generating function formula for \underline{A344507} then implies (14).

For (15), first let e_{n} = 2D_{−}(R_{1}, …, R_{n}) for n ≥ 1, with e_{0} = 1. Then e_{n} enumerates members of M_{n}^{∗} in which returns to the x-axis may be marked. By dropping the restriction that a member of M_{n} cannot go below the x-axis, one obtains the class of lattice paths known as the Grand Motzkin paths, denoted by GM_{n}. Then it is known that \underline{A109190}(n) enumerates the subset of GM_{n} consisting of those members with no h steps at level zero. By reflecting in the x-axis each unit to the left of a marked return within a marked member of M_{n}^{∗}, it is seen that e_{n} also enumerates the aforementioned subset of GM_{n}. Hence, e_{n} = \underline{A109190}(n) for all n ≥ 0, which implies (15). Finally, note that the proof above for the first part of (4) applies when restricted to the subset of D_{n} in which the corresponding λ are Riordan paths. Since this subset contains the set of survivors of the involution, formula (16) follows.

3.7 Proof of Eq. (17)

Given n ≥ 3 and 1 ≤ k ≤ n, let H_{n,k} denote the set of k-tuples λ = (λ_{1}, …, λ_{k}) such that each λ_{i} is a Riordan path of length at least three with ∑_{i=1}^{k} |λ_{i}| = n + 2k. Define the sign of λ ∈ H_{n,k} as (−1)^{n−k} and let H_{n} = ∪_{k=1}^{n}H_{n,k}. Then D_{+}(R_{3}, …, R_{n+2}) is seen to give the sum of the signs of all members of H_{n}. We define a sign-changing involution on H_{n} in three steps as follows. First let H_{n}^{(1)} ⊆ H_{n} comprise those λ = (λ_{1}, …, λ_{k}) where k can range over [n] such that either

(i) λ_{k} = αβ, or

(ii) λ_{k} = uβd,

where α is any Riordan path with |α| ≥ 3 and β is primitive with |β| ≥ 2 in both cases. Note, in (ii), that the only return to the line y = 1 within λ_{k} occurs with the penultimate step. We exchange cases (i) and (ii) by replacing λ_{k} in (i) with the two components λ_{k} = α and λ_{k+1} = uβd, and vice versa if (ii) holds with k > 1. This yields an involution of H_{n}^{(1)} which always reverses the sign that is not defined on the subset H̃_{n}^{(1)} comprising those members for which k = 1 and λ_{1} = uβd, where β is as described. Note that |H̃_{n}^{(1)}| = M_{n−2} since β is primitive and hence of length at least three (as k = 1), with each member of H̃_{n}^{(1)} having sign (−1)^{n−1}.

Next, let H_{n}^{(2)} consist of those λ = (λ_{1}, …, λ_{k}) in H_{n} where k can vary such that either (i) λ_{k} = uαd, where α is a Motzkin path that has at least one internal return to the x-axis and does not end in h, or (ii) λ_{k} = udβ, where β is primitive. Note that λ_{k} a Riordan path implies |β| ≥ 2 in (ii). Further, in (i), we let α = α′α′′, where α′′ is primitive. Then, by the assumptions on α, we have α′ ≠ ∅ and |α′′| ≥ 2. We now exchange cases (i) and (ii) as follows. If (i) holds, then replace λ_{k} = uα′α′′d with λ_{k} = uα′d and λ_{k+1} = udα′′, keeping all other components of λ the same. If (ii) holds, along with the further assumptions that k ≥ 2 and λ_{k−1} be primitive, then we reverse the operation just described.

Thus, at this point, we have paired each member of H_{n}^{(2)} with another of opposite sign except for those satisfying condition (ii) with k = 1 or with k ≥ 2 such that λ_{k−1} is not primitive. If the latter holds, then write λ_{k−1} = σσ′, where σ′ is primitive (and hence σ ≠ ∅). If |σ| ≥ 3, then replace λ_{k−1} = σσ′, λ_{k} = udβ with λ_{k−1} = σ, λ_{k} = udσ′ and λ_{k+1} = udβ, where β is primitive as before. If |σ| = 2 and k ≥ 3, then replace λ_{k−2} = τ, σ_{k−1} = udτ′ and σ_{k} = udβ with λ_{k−2} = ττ′ and λ_{k−1} = udβ, where τ′ is primitive. In either case, we keep all other components of λ the same. This mapping, taken together with the one defined in the preceding paragraph, yields a sign-changing involution on all members of H_{n}^{(2)} except for those satisfying condition (ii) with k = 1 or with k = 2 such that λ_{1} = udσ′, where σ′ is primitive.

Let H̃_{n}^{(2)} denote the subset of H_{n}^{(2)} for which the involution is not defined. Note that there are M_{n−2} possibilities for members of H̃_{n}^{(2)} where k = 1, each of sign (−1)^{n−1}, and ∑_{i=0}^{n−4} M_{i}M_{n−4−i} = M_{n−2} − M_{n−3} possibilities for members in which k = 2, each of sign (−1)^{n−2}, by the Motzkin number defining recurrence where i in the summation denotes |σ′| − 2. Thus, the sum of the signs of the members of H̃_{n}^{(2)} is given by

(−1)^{n−1}M_{n−2} + (−1)^{n−2}(M_{n−2} − M_{n−3}) = (−1)^{n−1}M_{n−3}.

Note that it is a straightforward matter at this point to pair members of H̃_{n}^{(2)} of opposite sign, if one desires, by considering the standard decomposition of a Motzkin path according to its first return to the x-axis.

Now let H_{n}^{(3)} = H_{n} − H_{n}^{(1)} − H_{n}^{(2)} and note that H_{n}^{(3)} consists of those members λ ∈ H_{n} for which the final component λ_{k} is primitive with the last two steps hd. If |λ_{k}| = 3, i.e., λ_{k} = uhd, then n ≥ 3 implies k ≥ 2 and we consider whether or not λ_{k−1} is primitive. If it is, then delete λ_{k} and insert an h directly preceding the terminal d step in λ_{k−1}. Note that the resulting lattice path is still primitive with length at least four. If |λ_{k}| ≥ 4, then remove the penultimate h step from λ_{k} and add the component λ_{k+1} = uhd. These two operations together yield an involution of H_{n}^{(3)} that is not defined if λ_{k} = uhd, with λ_{k−1} not primitive. In this case, we make use of a mapping similar to that employed in the second part of the involution defined above on H_{n}^{(2)} in which either the antepenultimate and penultimate components of λ were combined or the penultimate component was broken into two as described. Thus, each λ in H_{n}^{(3)} is paired with another of opposite sign except for those in which k = 2 with λ_{1} = udα and λ_{2} = uhd, where α is primitive, the subset of which we denote by H̃_{n}^{(3)}. Note that |H̃_{n}^{(3)}| = M_{n−3}, with each member of H̃_{n}^{(3)} having sign (−1)^{n−2}.

We have now defined sign-changing involutions on H_{n}^{(i)} for 1 ≤ i ≤ 3 with respective sets of survivors H̃_{n}^{(i)}. Hence, the sum of the signs of all members of H_{n} = ∪_{i=1}^{3}H_{n}^{(i)} is the same as the sum of the signs of members of ∪_{i=1}^{3}H̃_{n}^{(i)}. The contributions from H̃_{n}^{(2)} and H̃_{n}^{(3)} to this sum cancel and thus we get (−1)^{n−1}M_{n−2}. Note that it is a straightforward matter to pair the remaining unpaired members of H̃_{n}^{(2)} (i.e., those accounted for by (−1)^{n−1}M_{n−3}) with the members of H̃_{n}^{(3)}, if desired, as both sets are readily seen to be in one-to-one correspondence with M_{n−3}. Since D_{+}(R_{3}, …, R_{n+2}) equals the sum of the signs of all members of H_{n}, the proof of (17) is complete.

3.8 Proofs of Eqs. (18) and (19)

Given a composition σ of n with parts σ_{1}, …, σ_{m}, we overlay each σ_{i} with a member λ_{i} ∈ L_{σ_{i}} followed by an h step. Then let λ = λ_{1}h ⋯ λ_{m}h denote the corresponding member of L_{n+1} wherein we mark each appended h. Let Q_{n} denote the set of all λ ∈ L_{n+1} so marked. We then have D_{−}(L_{1}, …, L_{n}) = |Q_{n}| for all n ≥ 1. By a base h within a Motzkin left factor, we mean an h step (including possibly a terminal h step) for which there exists no step anywhere to its right that terminates at a strictly lower level. Upon deleting the final h, we may regard the λ ∈ Q_{n} as marked members of L_{n} in which some subset (possibly empty) of the base h’s is marked.

Let P_{n} denote the set of tricolored Motzkin paths of length n in which low h’s are colored either black, white or red. Then it is known that |P_{n}| is given by \underline{A059738}(n) for all n ≥ 0. Thus, to complete the proof of (18), it suffices to define a bijection between P_{n} and Q_{n+1}. To do so, consider replacing each red low h within ρ ∈ P_{n} by u and regard each white low h as being marked. Let ρ′ denote the resulting marked Motzkin left factor. One may verify that only base h’s can be marked in ρ′ and hence ρ′ ∈ Q_{n+1}. Let t denote the final height of a member of Q_{n+1}. Then the mapping ρ ↦ ρ′ may be reversed by considering the rightmost u step starting from the line y = i for each 0 ≤ i ≤ t − 1, which completes the proof of (18).

To show (19), define the sign of λ ∈ Q_{n} as (−1)^{n−ℓ}, where ℓ is the number of marked h steps in λ. Then D_{+}(L_{1}, …, L_{n}) equals the sum of the signs of all members of Q_{n}. Define an involution on Q_{n} by identifying the leftmost non-terminal base h and either marking it or removing the marking from it. This operation reverses the sign and fails to be defined on the subset Q_{n}^{∗} of Q_{n} whose members do not contain a base h outside of the terminal base h. Then members of Q_{n}^{∗} each have sign (−1)^{n−1} and, by the inverse of the mapping ρ ↦ ρ′ defined above, are equivalent to members of P_{n−1} in which each low h is red. As there are clearly M_{n−1} such members of P_{n−1}, formula (19) follows.

3.9 Proofs of Eqs. (20) and (21)

By a base step within a Motzkin left factor, we mean a non-terminal step for which there exists no step anywhere to its right that terminates at a strictly lower height. Let U_{n} denote the set of marked members of L_{n+1} in which some subset (possibly empty) of the base steps is marked. By reasoning similar to that used in the proof of (18), we have D_{−}(L_{2}, …, L_{n+1}) = |U_{n}| for n ≥ 1. Let u_{n} = |U_{n}| and one may verify u_{1} = 2 and u_{2} = 9, using the definitions. So assume n ≥ 3 and let λ ∈ U_{n}. If λ = uλ′ or λ ∈ hλ′, where λ′ ∈ U_{n−1}, then the first step of λ is a base step in either case, which implies 4u_{n−1} possibilities altogether. Now assume λ starts with u and returns to the x-axis at some point. Then λ = uτdλ′, where τ ∈ M_{i} and λ′ ∈ U_{n−2−i} for some i ≥ 0. If λ′ = ∅, then λ is primitive and there are no base steps in λ since the final step terminates at height zero and all other steps terminate at a positive height. Hence, there are M_{n−2} possibilities in this case. If λ′ ≠ ∅, then the d following the section τ within λ is a base step (with no others to its left). Considering all 0 ≤ i ≤ n − 3 in this case thus gives 2 ∑_{i=0}^{n−3} M_{i}u_{n−2−i} possibilities. Combining the prior cases then yields the recurrence stated for u_{n} and completes the proof of (20).

For (21), define the sign of a member of U_{n} by (−1)^{n−1−ℓ}, where ℓ denotes the number of base steps. Then D_{+}(L_{2}, …, L_{n+1}) equals the sum of the signs of the members of U_{n}. By either marking or unmarking the leftmost base step, each member of U_{n} is paired with another of opposite sign except for those which fail to contain a base step. From the analysis used to deduce the recurrence for u_{n}, members of U_{n} that do not contain a base step are precisely the primitive Motzkin paths and hence they number M_{n−2}, each with sign (−1)^{n−1}, which implies (21).

Remark 7. Sequences \underline{A111961} and \underline{A344507} have apparently only arisen before in algebraic settings and thus the structures used in conjunction with them in the proofs of (6) and (14) provide the first known combinatorial interpretations of these sequences. In particular, it was seen that \underline{A111961}(n) enumerates Motzkin paths of length n in which some subset of the steps terminating on the x-axis (either d or h) is marked whereas \underline{A344507}(n) corresponds to the sign-balance of the low h statistic on M_{n}. Further, the proofs of (15) and (18) provide new combinatorial interpretations for the sequences \underline{A109190} and \underline{A059738}, respectively.

References

[1] M. Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663–675.

[2] L. Alonso and R. Schott, Random Generation of Trees: Random Generators in Computer Science, Kluwer Academic Publishers, 1995.

[3] J.-L. Baril, S. Kirgizov, and A. Petrossian, Motzkin paths with a restricted first return decomposition, Integers 19 (2019), #A46.

[4] M. Barnabei, F. Bonetti, N. Castronuovo, and M. Silimbani, Motzkin and Catalan tunnel polynomials, J. Integer Sequences 21 (2018), Article 18.8.8.

[5] F. R. Bernhart, Catalan, Motzkin, and Riordan numbers, Discrete Math. 204 (1999), 73–112.

[6] D. Callan, Bijections for Dyck paths with all peak heights of the same parity, arxiv preprint arXiv:1702.06150 [math.CO], 2017. Available at https://arxiv.org/abs/

1702.06150.

[7] N. T. Cameron and A. C. M. Yip, Hankel determinants of sums of consecutive Motzkin numbers, Linear Algebra Appl. 434 (2011), 712–722.

[8] X.-K. Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, Electron. J. Combin. 19 (2016), #P1.8.

[9] W. Y. C. Chen, S. H. F. Yan, and L. L. M. Yang, Identities from weighted Motzkin paths, Adv. in Appl. Math. 41 (2008), 329–334.

[10] W. Fang, A partial order on Motzkin paths, Discrete Math. 343 (2020), 111802.

[11] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[12] R. Flórez, L. Junes, and J. L. Ramírez, Further results on paths in an n-dimensional cubic lattice, J. Integer Sequences 21 (2018), Article 18.1.2.

[13] L. Gan, S. Ouvry, and A. P. Polychronakos, Combinatorics of generalized Dyck and Motzkin paths, Phys. Rev. E. 106 (2022), 044123.

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

[15] T. Goy and M. Shattuck, Determinants of Toeplitz–Hessenberg matrices with generalized Fibonacci entries, Notes Number Theory Discrete Math. 25 (2019), 83–95.

[16] T. Goy and M. Shattuck, Determinant identities for Toeplitz–Hessenberg matrices with tribonacci numbers entries, Trans. Comb. 9 (2020), 89–109.

[17] T. Goy and M. Shattuck, Some Toeplitz–Hessenberg determinant identities for the tetranacci numbers, J. Integer Sequences 23 (2020), Article 20.6.8.

[18] T. Komatsu and J. L. Ramírez, Some determinants involving incomplete Fubini numbers, An. Şt. Univ. Ovidius Constanţa Ser. Mat. 26 (2018), 143–170.

[19] T. Mansour and M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. Math. Sci. 124 (2014), 127–140.

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

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

[22] R. Oste and J. Van der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, Electron. J. Combin. 22 (2015), #P2.8.

[23] A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, J. Integer Sequences 7 (2004), Article 04.2.5.

[24] L. W. Shapiro and C. J. Wang, A bijection between 3-Motzkin paths and Schröder paths with no peak at odd height, J. Integer Sequences 12 (2009), Article 09.3.2.

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

    https://oeis.org, 2022.

[26] J. O. Tirrell, Orthogonal polynomials, lattice paths, and skew Young tableaux, Ph.D. Thesis, Brandeis Univ., 2016. Available at https://people.brandeis.edu/~gessel/

    homepage/students/JordanTirrellThesis.pdf.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 11C20, 15B05. Keywords: Motzkin number, Motzkin path, Riordan number, Catalan number, Hessenberg– Toeplitz matrix, Trudi’s formula, generating function.

(Concerned with sequences \underline{A000108}, \underline{A001006}, \underline{A005043}, \underline{A005773}, \underline{A059738}, \underline{A109190}, \underline{A111961}, and \underline{A344507}.)

Received September 5 2022; revised version received March 12 2023. Published in Journal of Integer Sequences, March 14 2023.

Return to Journal of Integer Sequences home page.