\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \usepackage{tikz} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \begin{document} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries\\ \vskip .1in } \vskip 1cm \large Taras Goy\\ Faculty of Mathematics and Computer Science\\ Vasyl Stefanyk Carpathian National University \\ Ivano-Frankivsk, 76018\\ Ukraine\\ \href{mailto:taras.goy@pnu.edu.ua}{\tt taras.goy@pnu.edu.ua} \\ \vskip .2 in Mark Shattuck\\ Department of Mathematics\\ University of Tennessee\\ Knoxville, TN 37996\\ USA\\ \href{mailto:mshattuc@utk.edu}{\tt mshattuc@utk.edu} \\ \end{center} \vskip .2 in \begin{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. \end{abstract} \section{Introduction} The \emph{Fuss}-\emph{Catalan} numbers $A_n(p,r)$ were introduced in \cite{GRan} and are given explicitly by \begin{equation*} A_n(p,r)=\frac{r}{pn+r}\binom{pn+r}{n}=\frac{r}{n!}\prod_{i=1}^{n-1}(pn+r-i), \quad n \geq 0. \end{equation*} The $A_n(p,r)$ are given recursively by \begin{equation*} A_n(p,r)=A_n(p,r-1)+A_{n-1}(p,p+r-1), \qquad n \geq 1, \end{equation*} 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 \cite{Stanley}. The $A_n(p,r)$ are referred to as the \emph{Raney} numbers by some authors, with the \emph{Fuss}-\emph{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 \geq 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 \cite[Chapter~7]{GKP} 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 \cite[Lemma~4.1]{Edel}. See also, for example, the following references for other appearances of the Fuss-Catalan numbers in algebra \cite{Arm,HShap}, probability \cite{DM,Mlot}, and combinatorics \cite{AFKQ,Aval,Ma,PS,QG,SchW}. In \cite{GSh-Cat}, it was shown $$D_+(C_1,C_2,\ldots,C_n)=(-1)^{n-1}C_{n-1}, \qquad n \geq 1,$$ and $$D_{-}(C_1,C_2,\ldots,C_n)=(2n-1)C_{n-1}, \qquad n \geq 1,$$ by both algebraic and combinatorial arguments, where $D_{\pm}(a_1,\ldots,a_n)$ denotes the determinant of a Toeplitz-Hessenberg matrix of the form \eqref{HessToe} below in which $a_0=\pm1$. Here, we extend these and other results from \cite{GSh-Cat} 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 \cite{Sloane}. By contrast, Toeplitz-Hessenberg matrices whose determinants work out to the Fuss-Catalan numbers have previously been considered in \cite{Feng}. 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 \cite{GSh-Motz}, Leonardo \cite{GSh-Leo}, Schr\"oder, and Fine \cite{GSh-Sh+F} numbers. The organization of this paper is as follows. In the second section, we establish a general formula for $D_+(A_1(p,r),\ldots,A_n(p,r))$, and note some particular cases corresponding to entries in \cite{Sloane}. 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 \cite{Sloane}. 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,\ldots,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),\ldots,A_{n-1}(3,1))$, see \eqref{Hn-Jne2} 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},\ldots,K_{n-2})$ and $D_+(K_0,\ldots,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 \seqnum{A014137} in \cite{Sloane}). \section{Fuss-Catalan determinants} Consider an $n\times n$ matrix $A_n$ for some $n\geq 1$ of the form \begin{equation}\label{HessToe} A_n:= A_n(a_0; a_1,\ldots,a_n)=\left(\begin{array}{ccccccc} a_1 & a_0 & 0 & \cdots & 0 & 0 \\ a_2 & a_1 & a_0 & \cdots & 0 & 0 \\ a_3 & a_2 & a_1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n-1} & a_{n-2} & a_{n-3} & \cdots & a_1 & a_0 \\ a_{n} & a_{n-1}& a_{n-2} & \cdots & a_2 & a_1 \end{array}\right)\!, \end{equation} where $a_0\neq0$. Such a matrix $A_n$ is described as being \emph{Toeplitz-Hessenberg} (see, e.g., \cite{Muir}). The following expression for $\det(A_n)$ in terms of the $a_i$ is known as \emph{Trudi's} formula \cite[Theorem~1]{MM1}, the $a_0=1$ case of which has been attributed to Brioschi \cite{Muir}. \begin{lemma}\label{lem1} If $n\geq1$, then \begin{equation}\label{lem1e1} \det(A_n)=\sum_{\widetilde{\alpha}=n}(-a_0)^{n-|\alpha|}m_n(\alpha)a_1^{\alpha_1}a_2^{\alpha_2}\cdots a_n^{\alpha_n}, \end{equation} where the sum is over all $n$-tuples $\alpha=(\alpha_1,\ldots,\alpha_n)$ of non-negative integers such that $\widetilde{\alpha}=\alpha_1+2\alpha_2+\cdots+n\alpha_n=n$, with $|\alpha|=\alpha_1+\cdots+\alpha_n$ and $m_n(\alpha)=\frac{|\alpha|!}{\alpha_1!\cdots\alpha_n!}$. \end{lemma} Note that the sum in \eqref{lem1e1} may be regarded as being over the set of all partitions of the integer $n$. Consider now the generating functions $$f(x)=\sum_{n\geq1}\det(A_n)x^n \quad \text{and} \quad g(x)=\sum_{i\geq1}a_ix^i,$$ where $A_n$ is of the form in \eqref{HessToe}. Using \eqref{lem1e1}, one can establish the following relation (see, e.g., \cite{GSh-Leo}) between $f(x)$ and $g(x)$, which will be made frequent use of. \begin{lemma}\label{lem2} We have \begin{equation}\label{lem2e1} f(x)=\frac{-\frac{1}{a_0}g(-a_0x)}{1+\frac{1}{a_0}g(-a_0x)}. \end{equation} \end{lemma} To simplify notation, we denote the specific cases of $\det(A_n(a_0;a_1,\ldots,a_n))$ when $a_0=\pm1$ by $D_{\pm}(a_1,\ldots,a_n)$. We have the following general determinant formula involving Fuss-Catalan numbers, where the binomial coefficient $\binom{\alpha}{k}$ is taken to be $\frac{\alpha(\alpha-1)\cdots (\alpha-k+1)}{k!}$ for any number $\alpha$ and non-negative integer $k$. \begin{theorem}\label{genth} Let $p,r \geq0$ be fixed integers. Then we have \begin{equation}\label{genthe1} D_{+}(A_1(p,r),A_2(p,r),\ldots,A_n(p,r))=(-1)^{n-1}\frac{r}{n}\binom{pn-r-1}{n-1}, \qquad n\geq 1. \end{equation} \end{theorem} \begin{proof} Let $u(x)=\sum_{n\geq1}A_n(p,r)x^n$ and $v(x)=\sum_{n\geq1}(-1)^{n-1}\frac{r}{n}\binom{pn-r-1}{n-1}x^n$. By Lemma \ref{lem2}, to establish \eqref{genthe1}, it suffices to show $$\frac{-u(-x)}{1+u(-x)}=v(x), \quad \text{i.e.}, \quad u(x)+v(-x)=-u(x)v(-x),$$ upon replacing $x$ with $-x$. Consider equating coefficients of $x^n$ for $n\geq1$ on both sides of the last equation, taking into account a convolution on the right-hand side. Then \eqref{genthe1} is seen to be equivalent to the following binomial identity for all $n\geq1$: \begin{equation}\label{genthe2} \frac{r}{n}\binom{pn+r-1}{n-1}-\frac{r}{n}\binom{pn-r-1}{n-1}=\sum_{i=1}^{n-1}\frac{r^2}{i(n-i)}\binom{pi+r-1}{i-1}\binom{pn-pi-r-1}{n-i-1}. \end{equation} To show \eqref{genthe2}, we first recall the general convolution identity for all integers $n,t\geq0$ and real numbers $r$ and $s$ from \cite[p.\ 202,~Eq.\ (5.63)]{GKP}: $$\sum_{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 \begin{equation}\label{genthe3} \sum_{k=0}^n\frac{r^2}{(tk+r)(tn-tk-r)}\binom{tk+r}{k}\binom{tn-tk-r}{n-k}=0. \end{equation} Now consider separating the $k=0$ and $k=n$ terms in \eqref{genthe3} and then applying the fact $\binom{\alpha}{k}=\frac{\alpha}{k}\binom{\alpha-1}{k-1}$ for any real number $\alpha$ and positive integer $k$. This yields \begin{align*} \sum_{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}, \end{align*} which is equivalent to \eqref{genthe2} and completes the proof of \eqref{genthe1}. \end{proof} The following special cases of Theorem \ref{genth} correspond to entries in \cite{Sloane}. \begin{corollary}\label{genthcor1} We have \begin{align} (-1)^{n-1}D_+(A_1(2,3),A_2(2,3),\ldots,A_n(2,3))&=C_{n-1}-C_{n-2}=\seqnum{A000245}(n-2), \quad n \geq 2, \label{genthcor1e1}\\ (-1)^{n-1}D_+(A_1(2,4),A_2(2,4),\ldots,A_n(2,4))&=C_{n-1}-2C_{n-2}=-\seqnum{A115143}(n), \quad n \geq 3, \label{genthcor1e2}\\ (-1)^{n-1}D_+(A_1(3,1),A_2(3,1),\ldots,A_n(3,1))&=\frac{1}{n}\binom{3n-2}{n-1}=\seqnum{A006013}(n-1), \quad n \geq 1,\label{genthcor1e3}\\ (-1)^{n-1}D_+(A_1(3,2),A_2(3,2),\ldots,A_n(3,2))&=\frac{2}{n}\binom{3n-3}{n-1}=\seqnum{A007226}(n-1), \quad n \geq 1.\label{genthcor1e4} \end{align} \end{corollary} \begin{remark} Using the fact $\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}$, we have that the $p=0$ case of \eqref{genthe1} is equivalent to \begin{equation}\label{genthremarke1} D_{+}\left(\binom{r}{1},\binom{r}{2},\ldots,\binom{r}{n}\right)=\binom{n+r-1}{n}, \qquad n,r \geq 1. \end{equation} \end{remark} Let $K_n:=A_n(2,3)=C_{n+2}-C_{n+1}$ for $n \geq-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$. \begin{theorem}\label{genth1} If $n\geq1$, then \begin{align} D_{-}(C_1,C_3,\ldots,C_{2n-1})&=\seqnum{A066357}(n),\label{C_n/K_ne1}\\ D_{-}(C_2,C_3,\ldots,C_{n+1})&=p_n,\label{C_n/K_ne2}\\ D_{+}(K_{-1},K_0,\ldots,K_{n-2})&=(-1)^{n-1}\sum_{i=1}^{n-1}C_i,\label{C_n/K_ne3}\\ D_{+}(K_0,K_1,\ldots,K_{n-1})&=(-1)^{n-1}\sum_{i=0}^{n-1}C_i=(-1)^{n-1}\seqnum{A014137}(n-1),\label{C_n/K_ne4}\\ D_{-}(K_0,K_1,\ldots,K_{n-1})&=\seqnum{A026674}(n),\label{C_n/K_ne5} \end{align} where $p_n$ is given by $\frac{1}{2-C^2}=1+\sum_{n\geq1}p_nx^n$. \end{theorem} \begin{proof} To show \eqref{C_n/K_ne1}, first note $$\sum_{n\geq1}C_{2n-1}x^{2n-1}=\frac{C(x)-C(-x)}{2}=\frac{2-\sqrt{1-4x}-\sqrt{1+4x}}{4x},$$ and hence $$\sum_{n\geq1}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 \eqref{lem2e1}, we then have $$\sum_{n\geq1}D_{-}(C_1,\ldots,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 $$\sum_{n\geq1}\seqnum{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 \eqref{C_n/K_ne1} holds if and only if the generating functions for $n\geq 1$ corresponding to the two sides are equal, i.e., \begin{align*} &\big(2-\sqrt{1-4x^{1/2}}-\sqrt{1+4x^{1/2}}\big)\big(1+2x^{1/2}+\sqrt{1+4x^{1/2}}\big)\\ &=\big(2+\sqrt{1-4x^{1/2}}+\sqrt{1+4x^{1/2}}\big)\big(1-2x^{1/2}-\sqrt{1-4x^{1/2}}\big), \end{align*} which may subsequently be verified. For \eqref{C_n/K_ne2}, note $$\sum_{n\geq1}C_{n+1}x^n=\sum_{n\geq2}C_nx^{n-1}=\frac{1}{x}(C-1-x),$$ and hence $$\sum_{n\geq1}D_{-}(C_2,\ldots,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 \eqref{C_n/K_ne3}, first note $$\sum_{n\geq1}K_{n-2}x^n=\sum_{n\geq1}(C_n-C_{n-1})x^n=(1-x)C-1,$$ and thus, by the $a_0=1$ case of \eqref{lem2e1}, we have $$\sum_{n\geq1}D_{+}(K_{-1},\ldots,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, $$\sum_{n\geq1}\left((-1)^{n-1}\sum_{i=1}^{n-1}C_i\right)x^n=\sum_{i\geq1}C_i\sum_{n\geq 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 \eqref{C_n/K_ne3}. A similar proof applies to \eqref{C_n/K_ne4}. Finally, for \eqref{C_n/K_ne5}, note $$\sum_{n\geq1}K_{n-1}x^n=\sum_{n\geq0}(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 $$\sum_{n\geq1}D_{-}(K_0,\ldots,K_{n-1})x^n=\frac{xC^3}{1-xC^3}=\sum_{n\geq1}\seqnum{A026674}(n)x^n,$$ as desired. \end{proof} \begin{remark} Note that $\seqnum{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 \eqref{C_n/K_ne1} above is seen to provide a new combinatorial interpretation for \seqnum{A066357} in terms of weighted compositions of $n$ (see preliminary discussion in third section). A comparable remark applies to the other sequences from \cite{Sloane} that arise here as determinants of matrices with Fuss-Catalan entries. \end{remark} One may obtain an explicit formula for the sequence $p_n$ as follows, which apparently does not occur in \cite{Sloane}. Upon writing $$\sum_{n\geq1}p_nx^n=\frac{1}{2-C^2}-1=\frac{C^2-1}{1-(C^2-1)}=\sum_{i\geq1}(C^2-1)^i,$$ we have \begin{align*} p_n&=[x^n]\sum_{i\geq1}(C^2-1)^i=\sum_{i=1}^n\sum_{k=1}^i(-1)^{i-k}\binom{i}{k}[x^n]C^{2k}\\ &=\sum_{i=1}^n\sum_{k=1}^i(-1)^{i-k}\binom{i}{k}\frac{2k(2n+2k-1)!}{n!(n+2k)!}, \end{align*} 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 \geq 1$; see, e.g., \cite[p.\ 54, Eq.\ (2.5.16)]{Wilf}. The last expression may be rewritten to give \begin{equation}\label{p_nform} p_n=\sum_{k=1}^n\sum_{i=0}^{n-k}(-1)^i\frac{k}{n+k}\binom{2n+2k}{n}\binom{i+k}{k}, \qquad n \geq1. \end{equation} Let $$H_n:=A_n(3,1)=\frac{1}{3n+1}\binom{3n+1}{n}=\seqnum{A001764}(n)$$ and $$J_n:=A_n(3,2)=\frac{2}{3n+2}\binom{3n+2}{n}=\seqnum{A006013}(n)$$ for $n \geq0$. In addition to those given above in Corollary \ref{genthcor1}, we have the following determinant formulas involving $H_n$ and $J_n$. \begin{theorem}\label{genth2} Let $n\geq1$, unless stated otherwise. Then we have \begin{align} D_{+}(H_0,H_1,\ldots,H_{n-1})&=(-1)^{n-1}\seqnum{A023053}(n-1),\label{Hn-Jne1}\\ D_{-}(H_0,H_1,\ldots,H_{n-1})&=\seqnum{A098746}(n),\label{Hn-Jne2}\\ D_{-}(H_1,H_2,\ldots,H_n)&=\seqnum{A047099}(n),\label{Hn-Jne3}\\ D_{+}(H_2,H_3,\ldots,H_{n+1})&=\frac{2(-1)^{n-1}}{n}\binom{3n-3}{n-1}=(-1)^{n-1}\seqnum{A007226}(n-1), \quad n \geq2,\label{Hn-Jne4}\\ D_{+}(J_0,J_1,\ldots,J_{n-1})&=(-1)^{n-1}\seqnum{A121545}(n), \label{Hn-Jne5}\\ D_{-}(J_0,J_1,\ldots,J_{n-1})&=H_n. \label{Hn-Jne6} \end{align} \end{theorem} \begin{proof} We provide proofs of \eqref{Hn-Jne4} and \eqref{Hn-Jne6}, the others being similar. For \eqref{Hn-Jne4}, first note $$\sum_{n\geq1}H_{n+1}x^n=\frac{1}{x}(H-1-x),$$ where the power series $\sum_{n\geq0}H_nx^n$ is denoted by $H=H(x)$. Recall that $H$ satisfies $H=1+xH^3$. By Lemma \ref{lem2}, we get $$\sum_{n\geq1}D_+(H_2,\ldots,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 $$\sum_{n\geq2}D_+(H_2,\ldots,H_{n+1})x^n=\frac{x}{1-H(-x)}-1-3x.$$ On the other hand, from the known generating function formula for $\seqnum{A007226}(n)$, we have \begin{align*} &\sum_{n\geq2}(-1)^{n-1}\seqnum{A007226}(n-1)x^n=x\left(\sum_{n\geq0}\seqnum{A007226}(n)(-x)^n-2\right)\\ &=x\left(\frac{1-H^{-2}(-x)}{-x}-2\right)=H^{-2}(-x)-1-2x. \end{align*} So to complete the proof of \eqref{Hn-Jne4}, 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 \eqref{Hn-Jne6}, first note $\sum_{n\geq1}J_{n-1}x^n=xH^2$, by the known generating function formula for $J_n$. By \eqref{lem2e1}, we then get $$D_{-}(J_0,\ldots,J_{n-1})x^n=\frac{xH^2}{1-xH^2}.$$ Since $\sum_{n\geq1}H_nx^n=H-1$, equality \eqref{Hn-Jne6} is equivalent $xH^2=(H-1)(1-xH^2)$, which follows from the relation for $H$. \end{proof} By formula \eqref{lem1e1} and Theorems \ref{genth}, \ref{genth1}, and \ref{genth2}, we obtain the following multi-sum identities involving the Fuss-Catalan numbers. \begin{corollary} Let $n \geq 1$, unless stated otherwise. Then we have \begin{align*} \sum_{\widetilde{\alpha}=n}(-1)^{|\alpha|-1}m_n(\alpha)A_1(p,r)^{\alpha_1}A_2(p,r)^{\alpha_2}\cdots A_n(p,r)^{\alpha_n}&=\frac{r}{n}\binom{pn-r-1}{n-1},\\ \sum_{\widetilde{\alpha}=n}m_n(\alpha)C_1^{\alpha_1}C_3^{\alpha_2}\cdots C_{2n-1}^{\alpha_n}&=\seqnum{A066357}(n),\\ \sum_{\widetilde{\alpha}=n}m_n(\alpha)C_2^{\alpha_1}C_3^{\alpha_2}\cdots C_{n+1}^{\alpha_n}&=p_n,\\ \sum_{\widetilde{\alpha}=n}(-1)^{|\alpha|-1}m_n(\alpha)K_{-1}^{\alpha_1}K_0^{\alpha_2}\cdots K_{n-2}^{\alpha_n}&=\sum_{i=1}^{n-1}C_i,\\ \sum_{\widetilde{\alpha}=n}(-1)^{|\alpha|-1}m_n(\alpha)K_{0}^{\alpha_1}K_1^{\alpha_2}\cdots K_{n-1}^{\alpha_n}&=\sum_{i=0}^{n-1}C_i,\\ \sum_{\widetilde{\alpha}=n}m_n(\alpha)K_0^{\alpha_1}K_1^{\alpha_2}\cdots K_{n-1}^{\alpha_n}&=\seqnum{A026674}(n), \end{align*} \begin{align*} \sum_{\widetilde{\alpha}=n}(-1)^{|\alpha|-1}m_n(\alpha)H_{0}^{\alpha_1}H_1^{\alpha_2}\cdots H_{n-1}^{\alpha_n}&=\seqnum{A023053}(n-1),\\ \sum_{\widetilde{\alpha}=n}m_n(\alpha)H_{0}^{\alpha_1}H_1^{\alpha_2}\cdots H_{n-1}^{\alpha_n}&=\seqnum{A098746}(n),\\ \sum_{\widetilde{\alpha}=n}m_n(\alpha)H_{1}^{\alpha_1}H_2^{\alpha_2}\cdots H_{n}^{\alpha_n}&=\seqnum{A047099}(n),\\ \sum_{\widetilde{\alpha}=n}(-1)^{|\alpha|-1}m_n(\alpha)H_{2}^{\alpha_1}H_3^{\alpha_2}\cdots H_{n+1}^{\alpha_n}&=\seqnum{A007226}(n-1), \quad n \geq2,\\ \sum_{\widetilde{\alpha}=n}(-1)^{|\alpha|-1}m_n(\alpha)J_{0}^{\alpha_1}J_1^{\alpha_2}\cdots J_{n-1}^{\alpha_n}&=\seqnum{A121545}(n),\\ \sum_{\widetilde{\alpha}=n}m_n(\alpha)J_{0}^{\alpha_1}J_1^{\alpha_2}\cdots J_{n-1}^{\alpha_n}&=H_n, \end{align*} where $p_n$ is given by \eqref{p_nform} and we make use of the notation from Lemma \ref{lem1}. \end{corollary} \section{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 \times n$ matrix $A$ as a (signed) sum over the set $\mathcal{S}_n$ of permutations of $[n]$ given by \begin{equation}\label{combpre1} \det(A)=\sum_{\sigma \in \mathcal{S}_n}\text{sgn}(\sigma)a_{1,\sigma(1)}\cdots a_{n,\sigma(n)}, \end{equation} where $A=(a_{i,j})_{1\leq i,j \leq n}$ and $\text{sgn}(\sigma)$ denotes the sign of $\sigma\in \mathcal{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 $\sigma$ each of whose cycles comprises a set of consecutive integers in their natural order can make a nonzero contribution towards the sum in \eqref{combpre1}. Otherwise, one of the factors $a_{i,\sigma(i)}$ in the product of terms corresponding to $\sigma$ in \eqref{combpre1} is ensured of being zero. Recall that a \emph{composition} of $n\geq1$ is a sequence of positive integers, called \emph{parts}, whose sum is $n$. Let $\mathcal{C}_{n,k}$ denote the set of compositions of $n$ whose members have exactly $k$ parts and let $\mathcal{C}_n=\cup_{k=1}^n\mathcal{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 $\mathcal{C}_n$, upon identifying the various cycle lengths as parts. Suppose that each part of size $i$ for $i \geq1$ within a member of $\mathcal{C}_n$ is to receive a weight of $a_i$, where $(a_i)_{i\geq0}$ denotes the sequence associated with the Toeplitz-Hessenberg matrix $A$ defined by \eqref{HessToe}. Then one may regard the sum in \eqref{combpre1} in this case as being over $\mathcal{C}_n$, where the (signed) weight of a member $\pi=(\pi_1,\ldots,\pi_k)\in\mathcal{C}_{n,k}$ is given by $(-a_0)^{n-k}\prod_{i=1}^ka_{\pi_i}$. When $a_0=-1$, then all of the terms in the expansion of $\det(A)$ are non-negative, assuming $(a_i)_{i\geq1}$ is non-negative, and one gets \begin{equation}\label{combpre2} \det(A)=\sum_{\pi \in \mathcal{C}_n}a_{\pi_1}a_{\pi_2}\cdots, \qquad a_0=-1, \end{equation} where $\pi_i$ denotes the $i$-th part of $\pi=(\pi_1,\pi_2,\ldots)\in \mathcal{C}_n$. On the other hand, if $a_0=1$, then one gets the signed sum \begin{equation}\label{combpre3} \det(A)=\sum_{\pi \in \mathcal{C}_n}(-1)^{n-\mu(\pi)}a_{\pi_1}a_{\pi_2}\cdots, \qquad a_0=1, \end{equation} where $\mu(\pi)$ denotes the number of parts of the composition $\pi$. So to obtain combinatorial arguments for the determinant formulas from the prior section wherein $a_0=\pm1$, we interpret $\det(A)$ as a positive or signed sum over $\mathcal{C}_n$ in which parts are weighted as in \eqref{combpre2} or \eqref{combpre3}. The problem of finding combinatorial expressions (and explanations thereof) for positive composition sums such as those on the right-hand side of \eqref{combpre2} is one that has been encountered previously on occasion; see, e.g., \cite[p.\,46,~Exercises~14.f, 14.g, and 14.h]{Stan}. For the signed sums considered here of the form \eqref{combpre3}, we will make use of sign-changing involutions to establish the result. See, e.g., the text \cite[Chapter~6]{BQ} as well as \cite{BQ2} 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 \eqref{combpre2} or \eqref{combpre3} where $a_i$ corresponds to the cardinality of some set of lattice paths. See \cite[Section~4]{GSh-Cat} for comparable combinatorial arguments in which the sequence represented by $a_i$ for $i \geq 1$ is derived from the classical Catalan numbers. Before proceeding, let us recall some standard terminology. By a \emph{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 \emph{semi}-\emph{length} of a Dyck path $\rho$, denoted by $|\rho|$, is defined as the number of $u$ steps in $\rho$ (i.e., half the total number of steps of $\rho$). Let $\mathcal{D}_n$ for $n \geq1$ denote the set of all Dyck paths of semi-length $n$, with $\mathcal{D}_0$ the singleton set consisting of the empty lattice path. It is well-known that $|\mathcal{D}_n|=C_n$ for all $n\geq0$. By a \emph{unit} $\alpha$ within a Dyck path $\rho$, we mean a string of consecutive steps of $\rho$ of the form $\alpha=u\alpha'd$, where the initial $u$ starts and terminal $d$ ends on the $x$-axis and $\alpha'$ does not touch the $x$-axis at any point. That is, $\alpha'$ itself is a Dyck path (possibly empty) when viewed as starting from the origin. We now provide combinatorial proofs of the identities \eqref{C_n/K_ne1}, \eqref{C_n/K_ne2}, \eqref{C_n/K_ne5}, \eqref{genthremarke1}, \eqref{C_n/K_ne3}, \eqref{C_n/K_ne4}, \eqref{genthcor1e1}, \eqref{genthcor1e3}, \eqref{Hn-Jne6}, and \eqref{Hn-Jne2} 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$. \subsection{Proofs of \eqref{C_n/K_ne1}, \eqref{C_n/K_ne2}, and \eqref{C_n/K_ne5}} To show \eqref{C_n/K_ne1}, first note that $D_{-}(C_1,\ldots,C_{2n-1})$ enumerates compositions of $n$ in which parts of size $i$ are weighted by $C_{2i-1}$ for each $i\geq1$. To capture this idea combinatorially, let $\pi=(\pi_1,\pi_2,\ldots) \in \mathcal{C}_{n}$ and $\lambda=(\lambda_1,\lambda_2,\ldots)$, with each $\lambda_i \in \mathcal{D}_{2\pi_i-1}$. Note that the number of parts of $\pi$, and hence components of $\lambda$, may vary from $1$ to $n$. Then $D_{-}(C_1,\ldots,C_{2n-1})$ gives the cardinality of the set $S$ of all possible ordered pairs $(\pi,\lambda)$, as $\pi$ ranges over $\mathcal{C}_{n}$ and $\lambda$ can be any one of the vectors of Dyck paths corresponding to $\pi$. Given $\alpha=(\pi,\lambda)\in S$, define $g(\alpha)$ as the concatenation of the lattice paths $u\lambda_id$ for $i\geq1$, i.e., $g(\alpha)=\prod_{i\geq1}u\lambda_id$. From this, it is seen that $D_{-}(C_1,\ldots,C_{2n-1})$ gives the cardinality of the subset of $\mathcal{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 $\seqnum{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^\circ$ clockwise and dilating by a factor of $\sqrt{2}$, such lattice paths are seen to be synonymous with the aforementioned subset of $\mathcal{D}_{2n}$ enumerated by $D_{-}(C_1,\ldots,C_{2n-1})$, which implies \eqref{C_n/K_ne1}. We now show \eqref{C_n/K_ne2}. Given $n \geq 1$ and $1 \leq k \leq n$, let $\mathcal{A}_{n,k}$ denote the set of vectors $\lambda=(\lambda_1,\ldots,\lambda_k)$ of Dyck paths such that $\sum_{i=1}^k|\lambda_i|=n+k$ and $|\lambda_i|\geq 2$ for all $i$. Then we have $D_-(C_2,\ldots,C_{n+1})=|\mathcal{A}_n|$ for $n \geq 1$, where $\mathcal{A}_n=\cup_{k=1}^n\mathcal{A}_{n,k}$. We seek to show $|\mathcal{A}_n|=p_n$, where $p_n$ is as defined above. Since $$\sum_{n\geq1}p_nx^n=\frac{1}{2-C^2}-1=\frac{C^2-1}{1-(C^2-1)}=\sum_{k\geq1}(C^2-1)^k,$$ we have that $p_n$ gives the cardinality of the set $\mathcal{A}_n'$ consisting of all vectors of the form $\rho=(\rho_1,\ldots,\rho_k)$ where $k \in [n]$ in which $\sum_{i=1}^k|\rho_i|=n$ and each $\rho_i$ is a nonempty Dyck path wherein a point of $\rho_i$ along the $x$-axis is marked (possibly the first or last point). That is, each $\rho_i$ can be expressed as $\rho_i=\alpha_i\beta_i$, where $\alpha_i$ and $\beta_i$ are Dyck paths such that the final point of $\alpha_i$ is marked (with this point being the origin if $\alpha_i$ is empty). Consider decomposing each component $\lambda_i$ for $i\geq1$ within $\lambda=(\lambda_1,\lambda_2,\ldots) \in \mathcal{A}_n$ as $\lambda_i=\gamma_iu\delta_id$, where $\gamma_i$ and $\delta_i$ denote possibly empty Dyck paths. Define $f(\lambda)$ by $(\gamma_1\delta_1,\gamma_2\delta_2,\ldots)$ wherein the final point of $\gamma_i$ is marked in each component lattice path. Then $f(\lambda)\in \mathcal{A}_n'$ for each $\lambda$ as $|\lambda_i|\geq 2$ for all $i$ and $f$ is seen to be a bijection between $\mathcal{A}_n$ and $\mathcal{A}_n'$. This implies $|\mathcal{A}_n|=|\mathcal{A}_n'|=p_n$, as desired, and completes the proof of \eqref{C_n/K_ne2}. Finally, to show \eqref{C_n/K_ne5}, first observe that $K_{n-1}=C_{n+1}-C_n$ enumerates members of $\mathcal{D}_{n+1}$ starting with $uu$, by subtraction. Thus, we have that $D_-(K_0,\ldots,K_{n-1})$ counts the set $\mathcal{B}_n$ consisting of all vectors $\nu=(\nu_1,\nu_2,\ldots)$ of Dyck paths such that $\sum_{i\geq1}|\nu_i|=n+k$, where each $\nu_i$ starts $uu$ and $k$ denotes the number of components of the specific vector in question. Recall that $\seqnum{A026674}(n)$ is the coefficient of $x^n$ in the expansion of $\frac{xC^3}{1-xC^3}=xC^3+x^2C^6+\cdots$, and a combinatorial interpretation for this sequence in terms of lattice paths may be realized as follows. Given $n \geq1$, let $\mathcal{B}_n'$ denote the set of vectors $\pi=(\pi_1,\pi_2,\ldots)$ wherein $\sum_{i\geq1}|\pi_i|=n$ and each $\pi_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 $\pi_i$ within $\pi$ is accounted for by $xC^3$. Hence, the coefficient of $x^kC^{3k}$ enumerates the subset of vectors in $\mathcal{B}_n'$ which contain exactly $k$ components for each $k \geq 1$. Considering all possible $k$ thus implies $|\mathcal{B}_n'|=\seqnum{A026674}(n)$ for $n \geq 1$. To complete the proof of \eqref{C_n/K_ne5}, it then suffices to define a bijection between $\mathcal{B}_n$ and $\mathcal{B}_n'$. To do so, first note that since each component $\nu_i$ of $\nu \in \mathcal{B}_n$ starts with $uu$, we have $\nu_i=u\alpha_i\beta_id\gamma_i$, where $\alpha_i$ is a unit and $\beta_i$ and $\gamma_i$ are possibly empty Dyck paths. Define $\nu_i'=\beta_i\alpha_i\gamma_i$, where the unit $\alpha_i$ is to be marked, and let $\nu'=(\nu_1',\nu_2',\ldots)$. Note that $\nu' \in \mathcal{B}_n'$ for all $\nu$ since a single $u$ and $d$ have been removed from each component $\nu_i$ of $\nu$. The mapping $\nu \mapsto \nu'$ then provides a bijection between $\mathcal{B}_n$ and $\mathcal{B}_n'$, which implies \eqref{C_n/K_ne5}. \hfill \qed \medskip 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 $\sigma(S)$. \subsection{Proofs of \eqref{genthremarke1} and \eqref{C_n/K_ne3}} To show \eqref{genthremarke1}, where $r \geq1$ is fixed, first note that a member of $\mathcal{C}_n$ containing a part greater than $r$ does not contribute to the determinant in \eqref{genthremarke1}, so we may restrict attention to members of $\mathcal{C}_n$ with all parts in $[r]$. Given $1\leq k \leq n$, let $\mathcal{C}_{n,k}^{(r)}$ denote the subset of $\mathcal{C}_{n,k}$ consisting of those members whose parts all lie in $[r]$. Note that $\mathcal{C}_{n,k}^{(r)}=\varnothing$ if $km_j$. Let $\alpha'$ be the member of $\mathcal{T}_{n}^{(r)}$ obtained from $\alpha$ by either adding $r$ to each element of $\alpha$ greater than $m_{j_0}$ if ($i$) holds, or subtracting $r$ from each such element of $\alpha$ if ($ii$). Then one may verify that the mapping $\alpha \mapsto \alpha'$ provides the desired sign-changing involution, which completes the proof of \eqref{genthremarke1}. To show \eqref{C_n/K_ne3}, 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 \geq 2$ within $\pi \in \mathcal{C}_n$ a member of $\mathcal{D}_i$ that starts $u^2$, where it is assumed that $\pi$ contains no $1$'s. We will describe a $u^2$ string in which the first $u$ originates on the $x$-axis as \emph{basal}. Concatenating the various Dyck paths that arise as one considers all of the parts of $\pi$ from left to right yields a marked member of $\mathcal{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 $\mathcal{E}_n$ denote the set of marked members of $\mathcal{D}_n$ starting with $u^2$ and marked as described. Define the sign of $\rho \in \mathcal{E}_n$ as $(-1)^{n-k}$, where $k$ denotes the number of marked basal $u^2$ occurring in $\rho$. Then we have $D_+(K_{-1},\ldots,K_{n-2})=\sigma(\mathcal{E}_n)$ for $n \geq 1$. Define a sign-reversing involution on $\mathcal{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 $\rho \in \mathcal{E}_n$ of the form $\rho=u\rho'd(ud)^{n-i-1}$ for some $1 \leq i \leq n-1$, where $\rho'$ is a Dyck path. Such $\rho$ all have sign $(-1)^{n-1}$ and are enumerated by $\sum_{i=1}^{n-1}C_i$, upon considering the semi-length of $\rho'$. Thus, we have that $\sigma(\mathcal{E}_n)$ is given by the right side of \eqref{C_n/K_ne3} as well, which completes the proof. \hfill \qed \medskip The combinatorial proofs of the subsequent two identities require more intricate sign-changing involutions. \subsection{Proof of \eqref{C_n/K_ne4}} Given $n\geq1$ and $1 \leq k \leq n$, let $\mathcal{F}_{n,k}$ denote the set of sequences of ordered pairs $(i_1,\lambda_1),\ldots,(i_k,\lambda_k)$ such that $(i_1,\ldots,i_k)\in\mathcal{C}_{n,k}$ and $\lambda_j \in \mathcal{D}_{i_j+1}$ for all $j \in [k]$, with each $\lambda_j$ starting $u^2$. Define the sign of a member of $\mathcal{F}_{n,k}$ by $(-1)^{n-k}$ and let $\mathcal{F}_n=\cup_{k=1}^n\mathcal{F}_{n,k}$. Then we have $D_+(K_0,\ldots,K_{n-1})=\sigma(\mathcal{F}_n)$ for $n\geq1$. We define a preliminary sign-changing involution on $\mathcal{F}_n$ as follows. Let $(x,\lambda)$ denote the final ordered pair within $\pi \in \mathcal{F}_n$. Suppose first that $\lambda$ contains two or more units, that is, we may write $\lambda=\lambda'\lambda''$, where $\lambda' \neq \varnothing$ and $\lambda''$ is the final unit of $\lambda$. In this case, we replace $(x,\lambda)$ with the two components $(y,\lambda')$, $(z,u\lambda''d)$, leaving the rest of $\pi$ undisturbed, where $|\lambda'|=y+1$, $|\lambda''|=z$ and $x=y+z$. Note $\lambda'\neq \varnothing$ implies it must start $u^2$ and hence $y \geq 1$, as required. We perform the reversal of the procedure just described if $\lambda$ consists of a single unit of the form $\lambda=u^2\nu d^2$ for some Dyck path $\nu$. We will describe such a unit $\lambda$ as being \emph{simple}, with all other units $\neq ud$ being \emph{non-simple}. This involution may be extended by considering, if it exists, the rightmost component $(x,\lambda)$ within $\pi$ such that $\lambda$ 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 $\lambda$ is a simple unit, we require that $(x,\lambda)$ not be the first ordered pair of $\pi$. Then the set $\mathcal{F}_n'$ of survivors of this extended involution on $\mathcal{F}_n$ consists of those sequences of pairs $(i_1,\lambda_1),(i_2,\lambda_2),\ldots$ in $\mathcal{F}_n$ such that $\lambda_j$ for each $j \geq 2$ is a non-simple unit, with $\lambda_1$ a unit of either kind. Upon deleting the initial $u$ and terminal $d$ steps of $\lambda_j$ for each $j \geq 1$, one may regard members of $\mathcal{F}_n'$ as sequences of the form $(i_1,\rho_1),(i_2,\rho_2),\ldots$ such that $(i_1,i_2,\ldots)\in \mathcal{C}_n$ and $\rho_j\in \mathcal{D}_{i_j}$ for all $j$, with each $\rho_j$ containing two or more units except for possibly $\rho_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 $\mathcal{F}_n'$ as follows. Suppose $\rho=(i_1,\rho_1),\ldots,(i_k,\rho_k)$ is a member of $\mathcal{F}_n'$ for some $1 \leq k \leq n$. We consider several cases on $\rho_1$. If $\rho_1$ is a unit and $k>1$, then replace $(i_1,\rho_1),(i_2,\rho_2)$ with $(i_1+i_2,\rho_1\rho_2)$. Conversely, if $\rho_1$ contains at least three units, then we split the first ordered pair of $\rho$ so as to create two pairs, the first of which will have a unit for its second coordinate. On the other hand, if $\rho_1$ is a unit with $k=1$, then there are $C_{n-1}$ possibilities for $\rho$, each having sign $(-1)^{n-1}$. So suppose $\rho_1$ within $(i_1,\rho_1)$ contains exactly two units, and write $\rho_1=\alpha\beta$, with $\alpha$ and $\beta$ denoting the two units. If $\alpha=ud$ and $k>1$, then replace $(i_1,ud\beta), (i_2,\rho_2)$ with $(i_1+i_2,u\rho_2d\beta)$ and, conversely, split the first ordered pair of $\rho$ as indicated if $\alpha$ is non-simple with $k\geq1$. On the other hand, if $\alpha=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 $\beta$ is a unit with $|\beta|=n-1$ in this case. So assume $\alpha$ is a simple unit. If $\beta=ud$ and $k>1$, then replace $(i_1,\alpha ud),(i_2,\rho_2)$ with $(i_1+i_2,\alpha u\rho_2d)$ and, conversely, split the first ordered pair of $\rho$ as indicated if $\beta$ is non-simple with $k \geq 1$. If $\beta=ud$ and $k=1$, then, assuming $n \geq 3$, there is a contribution towards $\sigma(\mathcal{F}_{n}')$ of $(-1)^{n-1}C_{n-3}$ in this case, as $\rho_1=\alpha ud$ with $\alpha$ simple. So assume $n\geq4$ and $\rho_1=\alpha\beta$, where $\alpha$ and $\beta$ are both simple. Then we have $\alpha=u\alpha'd$ and $\beta=u\beta'd$, where $\alpha'$ and $\beta'$ are units. We then repeat the argument given in the preceding paragraph with $\alpha'\beta'$ in place of $\alpha\beta$. 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 $\mathcal{F}_{n-2}'$ after the transformations described above are made using $\alpha'\beta'$ in place of $\alpha\beta$. 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 $\mathcal{F}_n'$ with $k=1$ of the form $(n,\nu)$, where $\nu$ is one of the following: ($i$) $\nu$ a unit, ($ii$) $\nu=\alpha\beta$, where $\alpha=u^id^i$ and $\beta=u^{i-1}\beta'd^{i-1}$ for some $i\geq1$, with $\beta'$ a unit, or ($iii$) $\nu=\alpha\beta$, where $\alpha=u^i\alpha'd^i$ and $\beta=u^{i}d^{i}$ for some $i\geq1$, with $\alpha'$ a unit. This implies that the cardinality of the set of survivors is given by $$C_{n-1}+\sum_{i=1}^{\lfloor n/2 \rfloor}(C_{n-2i}+C_{n-2i-1}),$$ which may be rewritten as $\sum_{i=0}^{n-1}C_i$. As each survivor has sign $(-1)^{n-1}$, we have that $\sigma(\mathcal{F}_n)=\sigma(\mathcal{F}_n')$ is also given by the right side of \eqref{C_n/K_ne4}, which completes the proof. \hfill \qed \subsection{Proof of \eqref{genthcor1e1}} Given $n \geq 2$ and $1 \leq k \leq n$, let $\mathcal{G}_{n,k}$ denote the set of sequences of ordered pairs $(i_1,\lambda_1),\ldots,(i_k,\lambda_k)$ such that $(i_1,\ldots,i_k)\in\mathcal{C}_{n,k}$ and $\lambda_j \in \mathcal{D}_{i_j+2}$ for all $j \in [k]$, with each $\lambda_j$ starting $u^2$. Define the sign of a member of $\mathcal{G}_{n,k}$ by $(-1)^{n-k}$ and let $\mathcal{G}_n=\cup_{k=1}^n\mathcal{G}_{n,k}$ so that $D_+(K_1,\ldots,K_{n})=\sigma(\mathcal{G}_n)$. We define a preliminary sign-changing involution on $\mathcal{G}_n$ as follows. Let $(x,\lambda)$ denote the final ordered pair within $\pi \in \mathcal{G}_{n,k}$ for some $k \in [n]$. First suppose $\lambda$ contains two or more units. Let $\lambda=\alpha\beta\gamma$, where $\alpha$ and $\gamma$ are units and $\beta$ is possibly empty. Let $y=|\alpha|+|\beta|$ and we consider cases on $y$. If $y \geq 3$, then replace $(x,\lambda)$ with the two ordered pairs $(y-2,\alpha\beta), (z,u^2d^2\gamma)$, leaving the rest of $\pi$ undisturbed, where $z=|\gamma|$ and hence $x=y+z-2$. If $y=2$, then $\alpha=u^2d^2$ and $\beta=\varnothing$, in which case we perform the reversal of the operation just described and merge the final two pairs of $\pi$ accordingly, which can be done provided $k>1$. We extend this involution by considering the largest $j$, if it exists, such that $\lambda_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 $\mathcal{G}_n'$ of survivors of this extended involution on $\mathcal{G}_n$ consists of those sequences of pairs $(i_1,\lambda_1),(i_2,\lambda_2),\ldots$ such that $\lambda_j$ is a unit for all $j \geq 2$, with $\lambda_1$ either a unit or of the form $\lambda_1=u^2d^2\nu$ for a unit $\nu$. Let $\pi=(i_1,\lambda_1),\ldots,(i_k,\lambda_k)$ for some $k \in [n]$ denote a member of $\mathcal{G}_n'$. First suppose $\lambda_1$ is a unit. If $\lambda_k=u^2\delta d^2$, where $\delta$ is a Dyck path with $|\delta|\geq2$, then replace $(i_k,\lambda_k)$ with $(i_k-1,u\delta d),(1,u^3d^3)$, and vice versa, if $\delta=ud$. Note $n\geq 2$ implies $k>1$ in cases when $(i_k,\lambda_k)=(1,u^3d^3)$, whence there is a predecessor and the merging of the final two pairs of $\pi$ can indeed be implemented. On the other hand, if $\lambda_k$ is expressible as $\lambda_k=u\alpha\beta d$, where $\alpha$ is a unit and $\beta$ is a Dyck path with $|\beta|\geq 2$, then replace $(i_k,\lambda_k)$ with $(x,u\beta d),(y,u\alpha ud^2)$, where $x=|\beta|-1$ and $y=|\alpha|$. Note that $i_k=x+y$, as required, since $|\lambda_k|=|\alpha|+|\beta|+1=x+y+2$. If $\beta=ud$ in $\lambda_k$, then we perform the reverse operation on $\pi$, provided $k>1$. Note that members of $\mathcal{G}_{n}'$ with $k=1$ of the form $(i_1,\lambda_1)=(n,u\alpha ud^2)$, where $\alpha$ is a unit, remain unpaired. There are $C_{n-1}$ possibilities for such members of $\mathcal{G}_n'$ as $|\alpha|=n$ in this case, and each has sign $(-1)^{n-1}$. Now suppose $\lambda_1=u^2d^2\nu$ for a unit $\nu$. Each such sequence $\pi$ in $\mathcal{G}_n'$ where $k \geq 3$ is paired with another of opposite sign, by the preceding. Thus, the unpaired $\pi \in \mathcal{G}_n'$ at this point wherein $\lambda_1=u^2d^2\nu$ are those for which $k=1$ or $k=2$ with $\lambda_2=u^3d^3$ or $\lambda_2=u\delta ud^2$ for a unit $\delta$. Consider the following further pairings: \begin{align*} (i)&\,(n,u^2d^2u\alpha d) \leftrightarrow (n-1,u^2d^2\alpha), (1,u^3d^3),\\ (ii)&\,(n,u^2d^2u\alpha\beta d) \leftrightarrow (a,u^2d^2\alpha), (b,u^2\beta dud^2), \end{align*} where $\alpha$ is a unit, $\beta$ is a nonempty Dyck path, $a=|\alpha|$ and $b=|\beta|+1$. Note that $n \geq 2$ implies the section $\alpha$ is indeed nonempty in ($i$). It is seen that sequences $\pi$ with $k=2$ of the form $(n-1,u^2d^2\alpha),(1,u^2dud^2)$ are not paired by ($i$) or ($ii$). Then $\alpha$ a unit with $|\alpha|=n-1$ implies there are $C_{n-2}$ possibilities for such $\pi$, each having sign $(-1)^{n-2}$. Combining with the survivors above of the form $(i_1,\lambda_1)=(n,u\alpha ud^2)$ implies $$\sigma(\mathcal{G}_n)=\sigma(\mathcal{G}_n')=(-1)^{n-1}(C_{n-1}-C_{n-2}),$$ which completes the proof of \eqref{genthcor1e1}. \hfill \qed \medskip Before proving the next pair of identities, we recall some further terminology. A (\emph{rooted}) \emph{ternary tree} $T$ is a set of connected vertices (called \emph{nodes}) in which each node either has exactly three children or is childless, where one node (namely, the \emph{root}) is the ancestor of all other nodes. Nodes of $T$ for which there are no children are referred to as \emph{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 \emph{descendants} of $v$ is the subtree of $T$ for which $v$ is the root. Finally, the \emph{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 $\mathcal{R}_n$ denote the set of all ternary trees $T$ with $|T|=n$. Recall $H_n=\seqnum{A001764}(n)=|\mathcal{R}_n|$ for $n\geq0$, with $J_n=\seqnum{A006013}(n)$ enumerating the set of all ordered pairs $(\rho,\lambda)$ of ternary trees for which $|\rho|+|\lambda|=n$. \subsection{Proofs of \eqref{genthcor1e3} and \eqref{Hn-Jne6}} We first show \eqref{genthcor1e3}. Given $n \geq 1$ and $1 \leq k \leq n$, let $\mathcal{H}_{n,k}$ denote the set of vectors $(\lambda_1,\ldots,\lambda_k)$ of ternary trees such that $\sum_{j=1}^k|\lambda_j|=n$ and $|\lambda_j|\geq1$ for each $j$. Define the sign of a member of $\mathcal{H}_{n,k}$ by $(-1)^{n-k}$ and let $\mathcal{H}_n=\cup_{k=1}^n\mathcal{H}_{n,k}$. Then it is seen $D_+(H_1,\ldots,H_n)=\sigma(\mathcal{H}_n)$ for $n \geq 1$. To define a sign-changing involution on $\mathcal{H}_n$, we consider cases on the first component $\lambda_1$ of $\lambda=(\lambda_1,\lambda_2,\ldots) \in \mathcal{H}_n$ as follows. Let $r$ denote the root of $\lambda_1$ and $r_i$ for $1 \leq i \leq 3$ the left, middle, and right child of $r$, respectively. Let $\rho$ denote the subtree of $\lambda_1$ obtained by considering the complete set of descendants of $r_2$, with $r_2$ understood to be the root of $\rho$, and let $a=|\rho|$. If $a>0$, then we form the two ternary trees $\alpha$ and $\beta$, where $\alpha$ is obtained from $\lambda_1$ by deleting all of the descendants of $r_2$ (which would make $r_2$ a leaf in $\alpha$) and $\beta$ is taken to be a copy of the subtree $\rho$. One may verify $|\alpha|+|\beta|=|\lambda_1|$, with this operation reversing the sign of $\lambda$ as the number of components changes by one. On the other hand, if $a=0$, i.e., if $r_2$ is a leaf of $\lambda_1$, then we perform the reverse operation and merge the components $\lambda_1$ and $\lambda_2$ of $\lambda$ so that the root of $\lambda_2$ coincides with the middle child $r_2$ of $r$ in $\lambda_1$ (and hence the non-root nodes of $\lambda_2$ become the set of descendants of $r_2$). Note that this latter operation can be done provided $\lambda \in \mathcal{H}_{n,k}$ for some $k>1$. Combining the preceding two operations then yields a sign-changing involution on $\mathcal{H}_n$ that fails to be defined on members of $\mathcal{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 $\sigma$ and $\nu$ of $\lambda_1$ corresponding to the set of descendants of the children $r_1$ and $r_3$ of $r$, noting $|\sigma|+|\nu|=n-1$ since $r_2$ is a leaf. Thus, we also have that $\sigma(\mathcal{H}_n)$ is given by $(-1)^{n-1}J_{n-1}$ for $n\geq 1$, which completes the proof of \eqref{genthcor1e3}. \begin{figure}[ht] \centering \begin{tikzpicture}[ scale=1.14, every node/.style={inner sep=1pt}, dot/.style={circle, fill=black, inner sep=1.3pt} ] \node at (0,1.6) {$\pi_1=$}; \begin{scope}[xshift=1.2cm] \draw (0,2) -- (-0.6,1.3); \draw (0,2) -- (0,1.2); \draw (0,2) -- (0.6,1.3); \node[dot] at (0.0,2.0) {}; \node[dot] at (-0.6,1.3) {}; \node[dot] at (0,1.2) {}; \node[dot] at (0.6,1.3) {}; \end{scope} \node at (3.7,1.6) {$\pi_2=$}; \begin{scope}[xshift=4.8cm] \draw (0,2) -- (-0.5,1.3); \draw (0,2) -- (0,1.2); \draw (0,2) -- (0.7,1.4); \node[dot] at (0.0,2.0) {}; \node[dot] at (-0.5,1.3) {}; \node[dot] at (0,1.2) {}; \node[dot] at (0.7,1.4) {}; \end{scope} \node at (7.5,1.6) {$\pi_3=$}; \begin{scope}[xshift=8.7cm] \draw (0,2) -- (-0.6,1.3); \draw (0,2) -- (0,1.2); \draw (0,2) -- (0.8,1.6); \draw (0.8,1.6) -- (0.4,0.9); \draw (0.8,1.6) -- (0.8,0.8); \draw (0.8,1.6) -- (1.3,0.9); \node[dot] at (0.0,2.0) {}; \node[dot] at (.8,1.6) {}; \node[dot] at (-0.6,1.3) {}; \node[dot] at (0,1.2) {}; \node[dot] at (0.4,0.9) {}; \node[dot] at (0.8,0.8) {}; \node[dot] at (1.3,0.9) {}; \end{scope} \node at (11.5,1.6) {$\pi_4=$}; \begin{scope}[xshift=13.2cm] \draw (0,2) -- (-0.6,1.4); \draw (0,2) -- (0,1.2); \draw (0,2) -- (0.8,1.4); \draw (-0.6,1.4) -- (-1.0,0.8); \draw (-0.6,1.4) -- (-0.6,0.8); \draw (-0.6,1.4) -- (-0.2,0.8); \node[dot] at (0.0,2.0) {}; \node[dot] at (-0.6,1.4) {}; \node[dot] at (-1.0,0.8) {}; \node[dot] at (-0.6,0.8) {}; \node[dot] at (-0.2,0.8) {}; \node[dot] at (0,1.2) {}; \node[dot] at (0.8,1.4) {}; \end{scope} \node at (4.6,-2.0){$f(\pi)=$}; \begin{scope}[xshift=6.6cm, yshift=-0.3cm] \draw (0,0) -- (0,-0.6); \node[dot] at (0,-0.6) {}; \draw (0,-0.6) -- (0,-1.2); \node[dot] at (0,-1.2) {}; \draw (0,-1.2) -- (0,-1.8); \node[dot] at (0,-1.8) {}; \draw (0,-1.8) -- (0,-2.4); \node[dot] at (0.0,0.0) {}; \node[dot] at (0,-2.4) {}; \draw (0,0) -- (-0.7,-0.6); \draw (0,0) -- (0.7,-0.6); \node[dot] at (-0.7,-0.6) {}; \node[dot] at (0.7,-0.6) {}; \draw (0,-0.6) -- (-0.7,-1.2); \draw (0,-0.6) -- (0.7,-1.2); \node[dot] at (-0.7,-1.2) {}; \node[dot] at (0.7 ,-1.2) {}; \draw (0,-1.2) -- (-0.7,-1.8); \draw (0,-1.2) -- (1.1,-2.2); \node[dot] at (-0.7,-1.8) {}; \node[dot] at (1.1,-2.2) {}; \draw (0.,-1.8) -- (-0.7,-2.4); \draw (0.,-1.8) -- (0.7,-2.4); \node[dot] at (-0.7,-2.4) {}; \node[dot] at (0.7,-2.4) {}; \node[dot] at (-0.7,-3.0) {}; \node[dot] at (-1.2,-3.0) {}; \node[dot] at (-0.2,-3.0) {}; \draw (-1.2,-3.0) -- (-0.7,-2.4); \draw (-0.7,-2.4) -- (-0.2,-3.0); \draw (-0.7,-3.0) -- (-0.7,-2.4); \draw (1.1,-2.2) -- (1.1,-2.8); \draw (1.1,-2.2) -- (0.6,-2.8); \draw (1.1,-2.2) -- (1.6,-2.8); \node[dot] at (1.1,-2.8) {}; \node[dot] at (0.6,-2.8){}; \node[dot] at (1.6,-2.8){}; \end{scope} \end{tikzpicture} \caption{$\pi=(\pi_1,\pi_2,\pi_3,\pi_4)\in\mathcal{J}_6$ and $f(\pi)\in\mathcal{R}_6$.}\label{Fig1} \end{figure} To show \eqref{Hn-Jne6}, first let $\mathcal{J}_{n,k}$ for $1 \leq k \leq n$ denote the set of vectors $(\pi_1,\ldots,\pi_k)$ such that $\pi_i$ for each $i$ is a ternary tree with $|\pi_i|\geq 1$ wherein the middle child of the root is a leaf and $\sum_{i=1}^k|\pi_i|=n$. Note that if $|\pi_i|=b$, then there are $J_{b-1}$ possibilities for the component $\pi_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,\ldots,J_{n-1})=|\mathcal{J}_n|$ for $n \geq 1$, where $\mathcal{J}_n=\cup_{k=1}^n\mathcal{J}_{n,k}$, since the combined size of all the component trees $\pi_i$ is $n$. To complete the proof of \eqref{Hn-Jne6}, we need to show $|\mathcal{J}_n|=H_n$ for $n \geq 1$, and for this, we seek a bijection between $\mathcal{J}_n$ and $\mathcal{R}_n$. To do so, suppose $\pi=(\pi_1,\pi_2,\ldots) \in \mathcal{J}_n$. Let $r_i$ denote the root and $v_i$ the middle child of the root of $\pi_i$ for each $i\geq1$. Let $f(\pi)$ be the ternary tree obtained from $\pi$ by fusing $\pi_i$ to $\pi_{i+1}$ such that $r_{i+1}$ coincides with $v_i$ for all $i$. See Figure \ref{Fig1} above for an example of $f$ when $n=6$. Then $\sum_{i\geq1}|\pi_i|=n$ implies $f(\pi) \in \mathcal{R}_n$ for all $\pi$. Note that $\pi \in \mathcal{J}_{n,k}$ implies the level of the descendant $\delta$ reached by starting with the root of $f(\pi)$ and picking the middle child each time until one encounters a leaf is given by $k$ for each $k \in [n]$. Thus, to reverse $f$, one may start with the root $r$ of $\lambda \in \mathcal{R}_n$ and note the sequence of descendants $r=p_0,p_1,\ldots,p_k=\delta$ wherein $p_j$ is the middle child of $p_{j-1}$ for each $j \in [k]$ and $\delta$ is childless. Then use the subtrees of $\lambda$ obtained by considering the descendants of the two siblings of $p_j$ for each $j$ to construct the various components of $f^{-1}(\lambda)$. Hence, the mapping $f$ between $\mathcal{J}_n$ and $\mathcal{R}_n$ is seen to be reversible, and thus provides the desired bijection between the two sets. \hfill \qed \medskip Before proving our last identity, let us recall some terminology related to finite set partitions. By a \emph{partition} of a set, we mean a collection of nonempty pairwise disjoint subsets, called \emph{blocks}, whose union is the set. Let $\mathcal{P}_n$ denote the set of all partitions of $[n]$ for $n \geq1$, with $\mathcal{P}_0$ consisting of the single empty partition with no blocks. A partition $\Pi=B_1/B_2/\cdots \in \mathcal{P}_n$ is said to be in \emph{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 $\Pi$, expressed in standard form, is obtained by writing $\pi=\pi_1\cdots\pi_n$ wherein $i \in B_{\pi_i}$ for each $i \in [n]$ (see, e.g., \cite{SW}). The sequence $\pi$ is referred to as the \emph{canonical sequential form} of the partition $\Pi$. It is straightforward to show $\pi_{i+1}\leq \max(\pi_1\cdots\pi_i)+1$ for $1 \leq i \leq n-1$ with $\pi_1=1$, which is referred to as the \emph{restricted growth} condition (see, e.g., \cite{Mi}). Recall that a partition $\Pi$ is said to be \emph{non-crossing} (see \cite{Kl}) if its canonical form contains no subsequences of the form $a$-$b$-$a$-$b$, where $a