% NEEDS PDFLATEX

%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{30}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%% theorem environments %%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{example}[theorem]{Example}


\usepackage{bm}
\usepackage{mathtools}
\usepackage{enumitem}
\setlist[enumerate,1]{itemsep=0pt}

%% new commands %%

\newcommand{\commentout}[1]{}

\newcommand{\euler}[2]{\genfrac{\langle}{\rangle}{0pt}{}{#1}{#2}}
\newcommand{\germans}{{\mathfrak{s}}}
\newcommand{\stirlingcycle}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\newcommand{\stirlingsubset}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}

\newcommand{\ba}{{\bm{a}}}
\newcommand{\bb}{{\bm{b}}}
\newcommand{\bc}{{\bm{c}}}
\newcommand{\bp}{{\bm{p}}}
\newcommand{\bq}{{\bm{q}}}
\newcommand{\bw}{{\bm{w}}}
\newcommand{\bfx}{{\mathbf{x}}}

\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}

\newcommand{\bA}{\bm{A}}
\newcommand{\bS}{\bm{S}}
\newcommand{\bT}{{\bm{T}}}
\newcommand{\bfa}{\bm{a}}
\newcommand{\bfe}{\bm{e}}
\newcommand{\wt}[1]{\mathrm{wt}(#1)}
\newcommand{\bP}{{\sf P}}

\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\Sym}{{\mathfrak{S}}}

\newcommand{\orp}{<_{\pi}}
\newcommand{\cop}{\lessdot_{\pi}}

\newcommand{\ceq}{\coloneqq}



\newcommand{\myge}{\succeq}

\newcommand{\R}{{\mathbb R}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\textbfit}[1]{\textbf{\textit{#1}}}
\newcommand{\tri}{\bigtriangleup}
\newcommand{\triceil}[1]{\lceil #1 \rceil^{\rm tri}}
\newcommand{\tridefect}[1]{\{ #1 \}^{\rm tri}}

\newcommand{\smallest}[1]{\mathop{\rm smallest}\nolimits(#1)}
\newcommand{\largest}[1]{\mathop{\rm largest}\nolimits(#1)}

%% For scaling equations (uses "graphicx" package):  see
%% http://tex.stackexchange.com/questions/60453/reducing-font-size-in-equation
\newcommand*{\Scale}[2][4]{\scalebox{#1}{$#2$}}


%% definitions %%
\def\reff#1{(\protect\ref{#1})}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

%% define your title in the usual way
\title{Coefficientwise total positivity of some matrices defined by linear recurrences}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details


%%\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}%%
\author[X.~Chen, B.~Deb, A.~Dyachenko, T.~Gilmore, and A.~D.~Sokal]{
		Xi Chen\addressmark{1,2}, 
		 Bishal Deb\addressmark{2}, 
		 Alexander Dyachenko\addressmark{2,3}, 
		 Tomack Gilmore\addressmark{2},
    \and Alan D.~Sokal\addressmark{2,4}}



%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematical Sciences, Dalian University of
                   Technology, Dalian 116024, China \\
         \addressmark{2}Department of Mathematics, University College London,
                    London WC1E 6BT, UK \\
         \addressmark{3}Department of Mathematics and Statistics,
                    Universit\"at Konstanz, \hbox{D-78457 Konstanz, Germany} \\
         \addressmark{4}Department of Physics, New York University,
                    New York, NY 10003, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
   We exhibit a lower-triangular matrix of polynomials $\bm{T}(a,c,d,e,f,g)$
   in~six indeterminates that appears empirically to be
   coefficientwise totally positive, and which includes
   as a special case the Eulerian triangle.
   We prove the coefficientwise total positivity of $\bm{T}(a,c,0,e,0,0)$,
   which includes the reversed Stirling subset triangle.
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{
%    Nous pr\'esentons une matrice triangulaire %% inf\'erieure
%    de polyn\^omes $\bT(a,c,d,e,f,g)$ en six ind\'etermin\'ees
%    qui semble empiriquement \^etre totalement positive par coefficients
%    et qui inclut le cas du triangle eul\'erien.
%    %% Nous d\'emontrons cette propri\'et\'e
%    Nous le d\'emontrons
%    pour $\bT(a,c,0,e,0,0)$,
%    qui inclut le cas du triangle renvers\'e de nombres de Stirling
%    de deuxi\`eme esp\`ece.
% }

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Total positivity, coefficientwise total positivity,
   Eulerian triangle.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{30Chen.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

A finite or infinite matrix with integer or real coefficients is
called \emph{totally positive} if all its minors are nonnegative,
and \emph{strictly totally positive} if all its minors are
strictly positive.\footnote{
   {\bf Warning:}  Many authors (e.g.\ \cite{Gantmacher_02,Fomin_00,Fallat_11})
   use the terms "totally nonnegative" and "totally positive"
   for what we have termed "totally positive" and
   "strictly totally positive", respectively.
}
Such matrices have a wide variety of applications across pure and
applied mathematics; background material on this topic can be
found in~\cite{Karlin_68,Gantmacher_02,Pinkus_10,Fallat_11}.
Many interesting lower-triangular matrices (hereafter simply referred
to as \emph{triangles}) that arise in combinatorics have been shown
to be totally positive:
well-known examples include the binomial coefficients $\binom{n}{k}$,
the Stirling cycle numbers $\stirlingcycle{n}{k}$,
and the Stirling subset numbers $\stirlingsubset{n}{k}$.
% \footnote{
%    Here we follow the terminology and notations of
%    Graham, Knuth and Patashnik \cite{Graham_94}.
%    The Stirling cycle numbers are also known as
%    the unsigned Stirling numbers of the first kind
%    $|s(n,k)| = \germans(n,k) = c(n,k)$,
%    and the Stirling subset numbers are also known as
%    the Stirling numbers of the second kind $S(n,k)$
%    \cite{Comtet_74,Stanley_86}.
% }
But there are also many other combinatorially interesting triangles
that appear to be totally positive but for which we have no proof.
Foremost among these is what we call the "clean Eulerian triangle"
\be
        \bA
        \;=\;
        \biggl( \euler{n}{k}^{\! \rm clean} \biggr)_{\!\! n,k \ge 0}
        \;=\;
        \Scale[0.85]{
        \begin{bmatrix}
        1 &    &    &    &    &    &           \\
        1 &  1 &    &    &    &    &           \\
        1 &  4 &  1 &    &    &    &           \\
        1 &  11 &  11 &  1 &    &    &           \\
        1 &  26 &  66 &  26 &  1 &    &           \\
        1 &  57 &  302 &  302 &  57 &  1 &           \\
        \vdots &  \vdots &  \vdots &  \vdots &  \vdots &  \vdots  & \ddots  \\
        \end{bmatrix}
        }
    \,,
\ee
which was conjectured by Brenti~\cite{Brenti_96} to be totally positive,
already a quarter of a century ago.\footnote{
   Note that there exist several different conventions for the
   Eulerian triangle. %% \cite{Comtet_74,Graham_94}.
   For our purposes, the "clean" version defined here
   is the most convenient, as it has 1's both on the diagonal
   and in the zeroth column and is reversal-symmetric
   (i.e.\ $\euler{n}{k}^{\! \rm clean} = \euler{n}{n-k}^{\! \rm clean}$).
   It is easy to see that the other versions are totally positive
   if and only if the "clean" one is.
}
Here $\euler{n}{k}^{\! \rm clean}$
is the number of permutations of $[n+1]$ with $k$ excedances (or $k$ descents),
or the number of increasing binary trees on the vertex set $[n+1]$
with $k$ left children. These numbers satisfy the recurrence
\be
	\euler{n}{k}^{\! \rm clean} \;=\; (n-k+1) \,
	\euler{n-1}{k-1}^{\! \rm clean} \:+\: (k+1) \,
	\euler{n-1}{k}^{\! \rm clean} \label{eq.eulerian.recurrence}
\ee
for $n\geq 1$,
with initial condition $\euler{0}{k}^{\! \rm clean} = \delta_{k0}$.

\begin{conjecture}[{\protect\cite[Conjecture~6.10]{Brenti_96}}]
  \label{conj.eulerian}
	The clean Eulerian triangle $\bA$ is totally positive.
\end{conjecture}

A similar problem concerns the reversed Stirling subset triangle. Recall that the Stirling subset number $\stirlingsubset{n}{k}$
is the number of partitions of an $n$-element set into $k$ non-empty blocks
\cite[A048993/A008277]{OEIS}.
We then write $\stirlingsubset{n}{k}^{\rm rev} = \stirlingsubset{n}{n-k}$.
The reversed Stirling subset triangle is \cite[A008278]{OEIS}
\be
   \bS^{\rm rev}
   \;=\;
   \biggl( \stirlingsubset{n}{k}^{\! \rm rev} \biggr)_{\!\! n,k \ge 0}
   \;=\;
   \Scale[0.85]{
   \begin{bmatrix}
	1 &    &    &    &    &    &         \\
	1 &  0 &    &    &    &    &         \\
	1 &  1 &  0 &    &    &    &         \\
	1 &  3 &  1 &  0 &    &    &         \\
	1 &  6 &  7 &  1 &  0 &    &         \\
	1 &  10 &  25 &  15 &  1 &  0 &         \\
	\vdots &  \vdots &  \vdots &  \vdots &  \vdots &  \vdots &   \ddots  \\
   \end{bmatrix}
   }
   \,.
\ee
These numbers satisfy the recurrence
\be
  \stirlingsubset{n}{k}^{\!\rm rev}
   \;=\;
   (n-k) \, \stirlingsubset{n-1}{k-1}^{\!\rm rev}
   \:+\:
   \stirlingsubset{n-1}{k}^{\!\rm rev}
 \label{eq.revstirling.recurrence}
\ee
for $n\geq 1$,
with initial condition $\stirlingsubset{0}{k}^{\!\rm rev} = \delta_{k0}$.
Please note that the total positivity of a lower-triangular matrix
does \emph{not} in general imply the total positivity of its reversal.
Nevertheless we conjecture:

\begin{conjecture}
	\label{conj.revstirling}
The reversed Stirling subset triangle $\bS^{\rm rev}$ is totally positive.
\end{conjecture}

In this extended abstract we present a more general triangle comprised
of \emph{polynomial} entries in \emph{six} indeterminates that
appears empirically to be \emph{coefficientwise} totally positive
and that yields, under suitable specialisations,
both $\bA$ and $\bS^{\rm rev}$.
We do not yet have any proof that this more general triangle
is totally positive; indeed, we do not yet have any proof
of Conjecture~\ref{conj.eulerian}.
But we are able to prove a special case that includes
a generalisation of Conjecture~\ref{conj.revstirling}.

Before stating our main conjecture,
we extend the notion of total positivity to matrices whose elements
are polynomials in one or more indeterminates $\bfx$.
% \footnote{
%    In applications these will often be generating polynomials that enumerate
%    some combinatorial objects with respect to one or more statistics.
% }
We equip the polynomial ring $\R[\bfx]$ with the
\emph{coefficientwise partial order}:
that is, we say that $P$ is nonnegative (and write $P \myge 0$)
in case $P$ is a polynomial with nonnegative coefficients.
We then say that a matrix with entries in $\R[\bfx]$ is
\emph{coefficientwise totally positive}
if all of its minors are polynomials with nonnegative coefficients.
% \footnote{
%    Similar definitions apply to the formal-power-series ring $\R[[\bfx]]$.
%    Most generally, we can consider matrices with entries in an arbitrary
%    partially ordered commutative ring $R$;
%    however, for the sake of brevity we refrain from considering
%    this most general setting.
% }

Comparing recurrences~\eqref{eq.eulerian.recurrence}
and~\eqref{eq.revstirling.recurrence}
invites us to consider the more general linear recurrence
\be
   T(n,k)  \;=\;  [a(n-k) + c] \, T(n-1,k-1) \:+\: (dk + e) \, T(n-1,k) 
 \label{eq.TT2e.b=0}
\ee
for $n \geq 1$, with initial condition $T(0,k) = \delta_{k0}$.
Here $a,c,d,e$ could be integers or real numbers,
but we prefer to treat them as algebraic indeterminates.
Thus, the elements of the matrix $\bT=(T(n,k))_{n,k\geq 0}$
belong to the polynomial ring $\Z[a,c,d,e]$, and we conjecture:

\begin{conjecture}
   \label{conj.TT2e}
The lower-triangular matrix $\bT = \bigl( T(n,k) \bigr)_{n,k \ge 0}$
defined by~\eqref{eq.TT2e.b=0}
is coefficientwise totally positive in the indeterminates $a,c,d,e$.
\end{conjecture}

\noindent
In particular, Conjecture~\ref{conj.eulerian} would follow
by specialising $(a,c,d,e) = (1,1,1,1)$,
while Conjecture~\ref{conj.revstirling} would follow
by specialising $(a,c,d,e) = (1,0,0,1)$.

This, however, is not the end of the story.
Inspired partly by the work of Brenti~\cite{Brenti_95}
and partly by our own experiments,
we were led to consider the \emph{more} general recurrence\hspace*{-2mm}
\be
   T(n,k)  \,=\,  [a(n-k) + c]  T(n-1,k-1) +
                  (dk + e)  T(n-1,k) +
                  [f(n-2) + g]  T(n-2,k-1)
 \label{eq.TT5a.intro}
\ee
for $n\geq 1$,
with initial conditions $T(0,k) = \delta_{k0}$ and $T(-1,k) = 0$.
Again, we treat $a,c,d,e,f,g$ as algebraic indeterminates,
so that the matrix elements $T(n,k)$ belong to
the polynomial ring $\Z[a,c,d,e,f,g]$.
Note that this family is invariant under the reversal $k\to n-k$
by interchanging $(a,c)\leftrightarrow(d,e)$ and leaving $f$ and $g$ unchanged:
\be
   T(n,k;\,a,c,d,e,f,g)  \;=\;  T(n,n-k;\,d,e,a,c,f,g)
   \;.
 \label{eq.TT5a.reversal}
\ee
Our main conjecture is the following:

\begin{conjecture}
   \label{conj.TT5a}
The lower-triangular matrix $\bT = \bigl( T(n,k) \bigr)_{n,k \ge 0}$
defined by~\eqref{eq.TT5a.intro}
is coefficientwise totally positive in the indeterminates $a,c,d,e,f,g$.
\end{conjecture}

Unfortunately, for the time being,
Conjectures~\ref{conj.eulerian}, \ref{conj.TT2e} and \ref{conj.TT5a}
remain unproven.
(We have verified Conjecture~\ref{conj.TT5a} up to $13 \times 13$;
this computation took 109 days CPU time.)
The rest of this extended abstract is devoted to proving
the following special case of Conjecture~\ref{conj.TT2e},
which is of some interest in its own right:

\begin{theorem}\label{thm.Tace}
The matrix $\bT=(T(n,k))_{n,k\geq 0}$ specialised to $d=f=g=0$
is coefficientwise totally positive.
\end{theorem}

The triangle that appears in Theorem~\ref{thm.Tace}
is a generalisation of the reversed Stirling subset triangle,
and reduces to it when $(a,c,e) = (1,0,1)$;
this proves Conjecture~\ref{conj.revstirling}.
%% Throughout what follows we use
%% $\bT(\gamma_0,\gamma_1,\gamma_2,\gamma_3)$ to denote the matrix
%% $\bT=(T(n,k))_{n,k\geq 0}$ with entries $T(n,k)$ specialised to
%% $(a,c,d,e,f,g) = (\gamma_0,\gamma_1,\gamma_2,\gamma_3,0,0)$.
In what follows we write $\bT(a,c,d,e,f,g)$
for the matrix defined by \eqref{eq.TT5a.intro},
and $\bT(a,c,d,e) = \bT(a,c,d,e,0,0)$
for the matrix defined by \eqref{eq.TT2e.b=0}.

It is possible to prove Theorem~\ref{thm.Tace} in at least two different ways:
one algebraic, the other combinatorial.
In this extended abstract we take the combinatorial path,
leaving the algebraic arguments to a longer paper
(currently under construction).
Section~\ref{sec.comb.interp} establishes combinatorial interpretations
of the entries of $\bT(a,c,0,e)$ and $\bT(0,c,d,e)$
as generating polynomials for set partitions with suitable weights.
In Section~\ref{sec.planarnetworks} we present a planar network $D'$
and show --- by two different arguments ---
that the corresponding path matrix is equal to $\bT(a,c,0,e)$;
Theorem~\ref{thm.Tace} then follows by the Lindstr\"om--Gessel--Viennot lemma.
%% We conclude with some final remarks.


\section{Set partitions and the matrices $T(a,c,0,e)$ and $T(0,c,d,e)$}
   \label{sec.comb.interp}

% Recall that the Stirling subset number $\stirlingsubset{n}{k}$
% is the number of partitions of an $n$-element set into $k$ nonempty blocks.
% These numbers satisfy the fundamental recurrence
% \be
%    \stirlingsubset{n}{k}
%    \;=\;
%    \stirlingsubset{n-1}{k-1}
%    \:+\: k \, \stirlingsubset{n-1}{k}
% \ee
% for $n \ge 1$, with initial condition $\stirlingsubset{0}{k} = \delta_{k0}$. The reversed Stirling numbers
% $\stirlingsubset{n}{k}^{\rm rev} = \stirlingsubset{n}{n-k}$ therefore satisfy the recurrence
% \be
%   \stirlingsubset{n}{k}^{\!\rm rev}
%    \;=\;
%    (n-k) \, \stirlingsubset{n-1}{k-1}^{\!\rm rev}
%    \:+\:
%    \stirlingsubset{n-1}{k}^{\!\rm rev}
% \ee
% [cf.\ \reff{eq.revstirling.recurrence}].
From the fundamental recurrence
$\stirlingsubset{n}{k} =
 \stirlingsubset{n-1}{k-1} \,+\, k \, \stirlingsubset{n-1}{k}$
for the Stirling subset numbers
and its consequence \reff{eq.revstirling.recurrence}
for the reversed Stirling subset numbers,
we see that the Stirling and reversed Stirling numbers
correspond to the matrix $\bT(a,c,d,e)$ 
%% defined by \reff{eq.TT2e.b=0}
with $(a,c,d,e) = (0,1,1,0)$ and $(1,0,0,1)$, respectively.
Moreover, if one considers instead
$\stirlingsubset{n+1}{k+1}$ and $\stirlingsubset{n+1}{k}^{\rm rev}$,
then these matrices correspond to $\bT(a,c,d,e)$
with $(a,c,d,e) = (0,1,1,1)$ and $(1,1,0,1)$, respectively.
We will now show how to generalise the combinatorial interpretations
of $\stirlingsubset{n+1}{k+1}$ and $\stirlingsubset{n+1}{k}^{\rm rev}$
in terms of set partitions to $\bT(0,c,d,e)$ and $\bT(a,c,0,e)$.

We write $\Pi_n$ (resp.\ $\Pi_{n,k}$)
for the set of all partitions of the set $[n]$ into nonempty blocks
(resp.\ into exactly $k$ nonempty blocks).
For $i \in [n]$ and $\pi \in \Pi_n$,
we write $\smallest{\pi,i}$ for the smallest element
of the block of $\pi$ that contains $i$.
We then have:

\begin{proposition}[Interpretation of $\bT(0,c,d,e)$ and $\bT(a,c,0,e)$
                    in terms of set partitions]
   \label{prop.deb}
%\hfill\break
\hspace{0pt}
%\vspace*{-4mm}
\begin{enumerate}[label=(\roman*)]
   \item  The matrix $\bT = \bT(0,c,d,e)$ has the combinatorial
interpretation
%\vspace*{-2mm}
\be
   T(n,k)  \;=\;  \sum_{\pi \in \Pi_{n+1,k+1}} \prod_{i=2}^{n+1} w_\pi(i)
 \label{eq.prop.deb.a1}
%\vspace*{-1mm}
\ee
where
\be
   w_\pi(i)
   \;=\;
   \begin{cases}
      e  & \textrm{if $\smallest{\pi,i} = 1$}  \\[-0.5mm]
      c  & \textrm{if $\smallest{\pi,i} = i$}  \\[-0.5mm]
      d  & \textrm{if $\smallest{\pi,i} \neq 1,i$}  \\
   \end{cases}
 \label{eq.prop.deb.a2}
\ee
   \item  The matrix $\bT = \bT(a,c,0,e)$ has the combinatorial
interpretation
%\vspace*{-2mm}
\be
   T(n,k)  \;=\;  \sum_{\pi \in \Pi_{n+1,n+1-k}} \prod_{i=2}^{n+1} w_\pi(i)
 \label{eq.prop.deb.b1}
%\vspace*{-1mm}
\ee
where
\be
   w_\pi(i)
   \;=\;
   \begin{cases}
      c  & \textrm{if $\smallest{\pi,i} = 1$}  \\[-0.5mm]
      e  & \textrm{if $\smallest{\pi,i} = i$}  \\[-0.5mm]
      a  & \textrm{if $\smallest{\pi,i} \neq 1,i$}  \\
   \end{cases}
 \label{eq.prop.deb.b2}
\ee
\end{enumerate}
\end{proposition}

% From \reff{eq.prop.deb.a1}/\reff{eq.prop.deb.b1}
% we see that the weight of a partition is the product
% of the weights of its elements $i \ge 2$.
%% and that the weights \reff{eq.prop.deb.a2}/\reff{eq.prop.deb.b2}
%% are applied only for $i \ge 2$.
%Please
% also
Note that if one restricts
a partition $\pi \in \Pi_{n+1}$ to $[m]$ for some $m < n+1$
--- let us call the result $\pi_m \in \Pi_m$ ---
then $w_\pi(i) = w_{\pi_m}(i)$ for $2 \le i \le m$,
because $\smallest{\pi,i} = \smallest{\pi_m,i}$.
% each element $i \in [m]$ gets the same weight
% in $\pi_m$ as it did in $\pi$,
% because its smallest element is unchanged.
This fact will play a key role in justifying the recurrences.

\begin{proof}[Proof of Proposition~\ref{prop.deb}]
To prove (i)  we will show that the quantities $T(n,k)$ defined by
\reff{eq.prop.deb.a1}/\reff{eq.prop.deb.a2} satisfy the desired recurrence.
Part (ii) follows immediately from (i)
by way of the reversal identity~\eqref{eq.TT5a.reversal} with $f=g=0$.

In a partition $\pi \in \Pi_{n+1,k+1}$,
consider the status of the element $n+1$
and what remains when it is deleted. If $n+1$ is a singleton, then it gets a weight $c$,
and what remains is a partition of $[n]$ with $k$ blocks,
in which each element gets the same weight as it did in $\pi$.
This gives a term $c \, T(n-1,k-1)$. If instead $n+1$ belongs to the block containing 1, then it gets a weight $e$,
and what remains is a partition of $[n]$ with $k+1$ blocks,
in which each element gets the same weight as it did in $\pi$.
This gives a term $e \, T(n-1,k)$. Finally, if $n+1$ belongs to a block whose smallest element lies in
$\{2,3,\ldots,n\}$, then it gets a weight $d$,
and what remains is a partition of $[n]$ with $k+1$ blocks,
in which each element gets the same weight as it did in $\pi$.
There are $k$ blocks not containing~1 to which the element $n+1$
could have been attached.
This gives a term $dk \, T(n-1,k)$.
Summing these terms gives the desired recurrence.
\end{proof}

Here is another recurrence satisfied by these matrices,
which will be useful later:

\begin{lemma}[Alternate recurrences for $\bT(0,c,d,e)$ and $\bT(a,c,0,e)$]
   \label{lemma.deb.recurrence}
%\hfill\break
\hspace{0pt}
%\vspace*{-6mm}
\begin{enumerate}[label=(\roman*)]
   \item  The matrix $\bT = \bT(0,c,d,e)$ satisfies the recurrence
%\vspace*{-1mm}
\be
   T(n,k)  \;=\;  e \, T(n-1,k) \:+\: 
                  \sum_{m=0}^{n-1} \binom{n-1}{m} d^m c \, T(n-1-m,k-1)
%\vspace*{-1mm}
 \label{eq.lemma.deb.recurrence.1}
\ee
for $n \ge 1$, where $T(n,k) \ceq 0$ if $n<0$ or $k<0$.
   \item  The matrix $\bT = \bT(a,c,0,e)$ satisfies the recurrence
%\vspace*{-1mm}
\be
   T(n,k)  \;=\;  c \, T(n-1,k-1) \:+\: 
                  \sum_{m=0}^{n-1} \binom{n-1}{m} a^m e \, T(n-1-m,k-m)
%\vspace*{-1mm}
 \label{eq.lemma.deb.recurrence.2}
\ee
for $n \ge 1$, where $T(n,k) \ceq 0$ if $n<0$ or $k<0$.
\end{enumerate}
\end{lemma}

\begin{proof}
(i)  Use the interpretation of Proposition~\ref{prop.deb}(i),
and consider the status of element $n+1$.
If it belongs to the block containing~1, then it gets a weight~$e$,
and what remains is a partition of $[n]$ with $k+1$ blocks;
%% in which each element gets the same weight as it did in $\pi$.
this gives a term $e \, T(n-1,k)$.
Otherwise, it belongs to a block of size $m+1$ where $0 \le m \le n-1$.
We choose the other $m$ elements of this block in $\binom{n-1}{m}$ ways;
then the smallest element of this block gets weight~$c$,
and the other $m$ elements get weight~$d$.
What remains is a partition of an $(n-m)$-element set with $k$~blocks,
corresponding to $T(n-1-m,k-1)$.

(ii) follows immediately from (i) by the reversal identity.
\end{proof}

We remark that these recurrences, supplemented by the initial
condition $T(0,k) = \delta_{k0}$, completely determine the matrices.

% {\bf QUESTION FOR LATER:
%    Can we go directly between the original recurrence and the
%    alternate recurrence, without using the combinatorial interpretation???}



\section{Planar networks and total positivity}\label{sec.planarnetworks}

One very useful tool in proving the total positivity of a matrix
is the famous Lindstr\"om--Gessel--Viennot (LGV) lemma
\cite[Chapter~32]{Aigner_18}.
Consider an acyclic digraph $\cal D$ equipped with edge weights $w_e$
and a distinguished set of sources $U:=\{u_0,u_1,\ldots\}$
and sinks $V:=\{v_0,v_1,\ldots\}$.
The weight $w(\mathcal{P})$ of a path $\mathcal{P}$
is the product of its edge weights;
and we define the \emph{path matrix} $\bm{P} :=(P(u_n\to v_k))_{n,k\geq 0}$ by
$
  P(u_n\to v_k)
  \ceq
  \sum_{\mathcal{P}\colon u_n\to v_k}  w(\mathcal{P})
$.
Now assume further that the digraph $\cal D$ is planar
and that the sources and sinks lie on the boundary of $\cal D$
in the order ``first $U$ in reverse order, then $V$ in order'';
we refer to this setup as a \emph{planar network}.
Then the collection of sources and sinks is \emph{fully compatible}
in the sense that, for any subset of
sources $u_{n_1},\dots,u_{n_r}$ (with $n_1< n_2< \cdots< n_r$)
and sinks $v_{k_1},\dots,v_{k_r}$ (with $k_1<k_2<\cdots<k_r$),
the only permutation $\sigma \in \Sym_r$ mapping
each source $u_{n_i}$ to the sink $v_{k_{\sigma(i)}}$
that gives rise to a nonempty family of nonintersecting paths in $\cal D$
is the identity permutation.
The LGV lemma then implies that every minor of the path matrix $\bm{P}$
is given by a sum over families of nonintersecting paths
between specified subsets of $U$ and $V$,
where each family has weight $\prod w(\mathcal{P}_i)$.
If furthermore every edge weight $w_e$ is a positive real number,
then $\bm{P}$ is totally positive;
and if every edge weight is a polynomial in some indeterminates $\bfx$
with nonnegative real coefficients,
then $\bm{P}$ is coefficientwise totally positive.
This argument goes back to Brenti~\cite{Brenti_95}.

Figure~\ref{fig.genericDigraph}(a) shows what we call the
\emph{standard binomial-like planar network}, which we denote $D$.
We label the vertices of $D$ by pairs $(i,j)$ with $0 \le i \le j$,
where $i$ increases from right to left
and $j$ increases from bottom to top.
The horizontal directed edge from $(i,j)$ to $(i-1,j)$
[where $1 \le i\leq j$] is given a weight $\alpha_{i,j-i+1}$,
while the diagonal directed edge from $(i,j)$ to $(i-1,j-1)$
[where $1 \le i\leq j$] is given a weight $\beta_{i,j-i}$.
The source vertices are $u_n = (n,n)$
and the sink vertices are $v_k = (0,k)$.


It is easy to see that if the weights depend only on the first index
(i.e.\ are constant within columns in the digraph), then
\be
   P(u_n\to v_k) \;=\;
   \alpha_{n,\bullet} P(u_{n-1}\to v_{k-1}) 
      \,+\, \beta_{n,\bullet} P(u_{n-1}\to v_k)
   \;,
\ee
so that the entries of the corresponding path matrix satisfy a
purely $n$-dependent linear recurrence.
Similarly, if the weights depend only on the second index
(i.e.\ are constant along diagonals in the digraph), then
\be
   P(u_n\to v_k) \;=\;
   \alpha_{\bullet,k} P(u_{n-1}\to v_{k-1}) 
      \,+\, \beta_{\bullet,k} P(u_{n-1}\to v_{k})
   \;,
\ee
so that the entries of the corresponding path matrix satisfy a
purely $k$-dependent recurrence.
In particular, by setting $\alpha_{n,k}=1$ and $\beta_{n,k}=k$,
we recover a digraph yielding the Stirling subset triangle
$P(u_n\to v_k) = \stirlingsubset{n}{k}$;
and more generally, by setting $\alpha_{n,k}=c$ and $\beta_{n,k}=dk+e$,
we recover $\bT(0,c,d,e)$ and prove its coefficientwise total positivity.
This too goes back to Brenti~\cite{Brenti_95}.

\begin{figure}[t]
\center
\includegraphics[scale=0.37]{genericDigraph.pdf} \\[3mm]
\includegraphics[scale=0.37]{DaeColouredPN.pdf}
%%\includegraphics[scale=0.52]{figures/DaeColouredPN.png}
\caption{
   (a) The standard binomial-like planar network $D$ (above), and
   (b) the planar network $D'$ (below),
   each shown up to source $u_4$ and sink $v_4$.
}
   \label{fig.genericDigraph}
\end{figure}



\subsection{The planar network $D'$}

We will now describe a digraph $D'$ that is obtained from $D$
by deleting certain edges (or equivalently, setting their weights to 0),
setting some of the other weights to 1,
and relabelling the remaining weights.
A special role will be played by the \emph{triangular numbers}
$\tri(n) := \binom{n+1}{2}$.
We also define the "triangular ceiling" $\triceil{k}$
to be the smallest triangular number that is $\ge k$,
and the "triangular defect" $\tridefect{k} := \triceil{k} - k$.

For the diagonal edges, we set
\be
   \beta_{i,l}
   \;=\;
   \begin{cases}
       e_{\tri^{-1}(i+l-1)-l,\: l}  &
             \textrm{if $i+l-1$ is triangular and $i+l-1 \ge \tri(l)$} \\
       1  &  \textrm{if $i+l-1$ is not triangular and $i+l-1 \ge \tri(l)$} \\
       0  &  \textrm{in all other cases}
   \end{cases}
\ee
for $i \ge 1$ and $l \ge 0$.
For the horizontal edges, we set
%% {\bf I am confused by your saying that $i+l-1$ is triangular
%%    but then giving weights for $\alpha_{i-j,l}$ for a whole range of $j$.
%%    Can't we just say what $\alpha_{i,l}$ is???}
\be
   \alpha_{i,l}
   \;=\;
   \begin{cases}
       a_{\tri^{-1}(\triceil{i+l-1})-l,\: \tridefect{i+l-1},\: l-1}  &
            \textrm{if $\tri^{-1}(\triceil{i+l-1})-l \ge \tridefect{i+l-1}$} \\
       1  &  \textrm{if $i+l-1$ is triangular and $i+l-1 < \tri(l)$} \\
       0  &  \textrm{in all other cases}
   \end{cases}
\ee
for $i,l \ge 1$.
We then delete the edges with zero weight.
Finally, we take the source vertices to be $u_n := (\tri(n),\tri(n))$
and the sink vertices to be $v_{k} := (0,\tri(k))$.
The resulting planar network $D'$ is shown in
Figure~\ref{fig.genericDigraph}(b).

% {\bf OLD TEXT:}
% For indices $i,l$ with $i\geq l$ let each diagonal edge
% $\beta_{i,l}$ in $D$ such that $i+l-1$ is triangular have weight
% $e_{\tri^{-1}(i+l-1)-l,l}$. For the remaining diagonal edges,
% (that is, $\beta_{i,l}$ where $i+l-1$ is not triangular)
% let $\beta_{i,l}=1$ if $i>l$ and $0$ otherwise. We apply a
% similar process to the horizontal edges. Given $i,l$ such
% that $i+l-1$ is triangular consider the horizontal edges
% $\alpha_{i-j,l}$ where $0\leq j \leq \tri^{-1}(i+l-1)-l-1$. If
% $(i+l+j-1)$ is triangular and $l< \tri^{-1}(i+l-1)$ set
% $\alpha_{i-j,l}=a_{\tri^{-1}(i+l-1)-l-1,j,l-1}$, and for $j=0$ and
% $l\geq \tri^{-1}(i+l-1)$ let $\alpha_{i,l}=1$. Finally we set all
% other horizontal edges to $0$.

It is clear that every edge of $D'$ either has weight 1
(we call these \emph{black edges})
or else has a unique weight in the set $\calA \cup \calE$, where
$\calA := \{a_{i,j,l} \colon\, (i,j,l)\in\N^3 \textrm{ and } j\leq i\}$
and $\calE := \{e_{i,l} \colon\, (i,l)\in\N^2\}$
(we call these \emph{coloured edges}).
Each path $\calP$ has a weight $w(\calP)$ that is
a monomial in $\Z[\calA,\calE]$.

Let $\bP_{n,k}$ be the set of all paths in $D'$ from $u_n$ to $v_k$.
It is easy to see that $\bP_{n,k}$ is nonempty
if and only if $n \ge k$.
%% (as we shall assume henceforth).
Furthermore, for any two distinct paths $\calP,\calP'$
from $U$ to $V$ in $D'$, we have $w(\calP)\neq w(\calP')$.
Lastly, note that each path $\calP \in \bP_{n,k}$
traverses precisely $n$ coloured edges,
so $w(\calP)$ is a monomial of total degree~$n$.

Applying the Lindstr\"om--Gessel--Viennot lemma to the digraph $D'$,
we can immediately conclude:

\begin{proposition}
   \label{prop.calAE}
The matrix $\bT = (T(n,k))_{n,k \ge 0}$ defined by
$T(n,k) = \sum_{\calP \in \bP_{n,k}} w(\calP)$,
with entries in $\Z[\calA,\calE]$,
is coefficientwise totally positive.
\end{proposition}

The trouble with Proposition~\ref{prop.calAE}
--- as with many applications of Lindstr\"om--Gessel--Viennot ---
is that the set of paths in a digraph can be a rather complicated object;
our goal is to find a simpler combinatorial interpretation.
This can be done either by obtaining a recurrence
that can be compared with Lemma~\ref{lemma.deb.recurrence},
or by constructing an explicit bijection between paths and set partitions.
We shall describe in detail the former approach, and then sketch the latter.

For $0 \le m \le n$, let $u_{n,m} \ceq (\tri(n)-m,\tri(n))$
be the vertex that lies $m$ steps to the right of $u_n$.
We observe that the subnetwork of $D'$ reachable from $u_{n,m}$ is isomorphic
--- after contraction of some black edges,
relabelling $u_n \to u_{n-m}$ and $v_k \to v_{k-m}$ of source and sink vertices,
and relabelling of edge weights ---
to the subnetwork reachable from $u_{n-m}$.
It follows that
\be
   P(u_{n,m} \to v_k)
   \;=\;
   P(u_{n-m} \to v_{k-m}) \bigr|_
    {a_{i,j,l} \to a_{i,j,l+m},\: e_{i,l} \to e_{i,l+m}}
   \;.
 \label{eq.unm.relabeling_identity}
\ee

Now consider a path $\calP$ from $u_n$ to $v_k$.
If the first step is to the right,
we obtain $a_{n-1,0,0}$ times $P(u_{n,1} \to v_k)$.
If the first step is diagonally downwards,
we enter a binomial-like network of size $n-1$,
from which we can emerge on the right wall
at some point $\widehat{u}_{n-1,m} \ceq (\tri(n-1),\tri(n-1)+m)$
for $0 \le m \le n-1$;
from there we follow edges diagonally downwards,
arriving at the point $u_{n-1,m}$
and picking up an extra factor $e_{n-1-m,m}$.
The contribution of the binomial-like network is a bit complicated,
but if we make the specialisation $a_{i,j,l} \to a$ whenever $j > 0$,
then its weight is just $\binom{n-1}{m} a^m$.
We also specialise $a_{i,0,l} \to c_i$ and $e_{i,l} \to e_i$
in order to trivialise the relabellings in \reff{eq.unm.relabeling_identity}.
It follows that with these specialisations the matrix $\bT$
satisfies the recurrence
\be
   T(n,k)
   \;=\;
   c_{n-1} \, T(n-1,k-1)
   \:+\: \sum_{m=0}^{n-1} \binom{n-1}{m} a^m \, e_{n-1-m} \, T(n-1-m,k-m)
 \label{eq.recurrence.acenetwork}
\ee
for $n \ge 1$.
% {\bf What is the combinatorial meaning, in terms of set partitions,
%    of the indices in $c_i$ and $e_i$???
%    And can we go from this recurrence back to an ``elementary'' recurrence
%  that includes the $i$-dependence in $c_i$ and $e_i$?????}
In particular, if $c_i = c$ and $e_i = e$ for all~$i$,
then we recover the recurrence \reff{eq.lemma.deb.recurrence.2}.
Applying Lemma~\ref{lemma.deb.recurrence}(ii), we conclude:

\begin{theorem}
   \label{thm.pathmatrix.ace}
The path matrix $\bT = (T(n,k))_{n,k \ge 0}$ defined by
$T(n,k) = \sum_{\calP \in \bP_{n,k}} w(\calP)$,
with the specialisations $e_{i,l} \to e$,
$a_{i,0,l} \to c$, and $a_{i,j,l} \to a$ for $j > 0$,
coincides with the matrix $\bT(a,c,0,e)$.
\end{theorem}

Combining Proposition~\ref{prop.calAE} with Theorem~\ref{thm.pathmatrix.ace}
proves Theorem~\ref{thm.Tace}.
More generally, Proposition~\ref{prop.calAE} shows that
the matrix $\bT$ defined by the recurrence \reff{eq.recurrence.acenetwork}
is coefficientwise totally positive
in the indeterminates $a$, $(c_i)_{i \ge 0}$ and $(e_i)_{i \ge 0}$.


\subsection{Bijection between paths and set partitions}

We now sketch the bijective approach to proving
Theorem~\ref{thm.pathmatrix.ace},
which is based on a detailed analysis of the paths in the set $\bP_{n,k}$.
The first step is provided by the following lemma,
in which $\wt{\calP}$ denotes the \emph{non-commutative} product of the weights
of $\calP$, taken in the order of traversal.

\begin{lemma}
   \label{lemma.pathword}
Fix integers $n \ge k \ge 0$,
and let $\bw$ be a word in the alphabet $\calA\cup\calE$.
Then~$\bw=\wt{\calP}$ for some path $\calP \in \bP_{n,k}$
if and only if and all of the following conditions hold:
\begin{enumerate}[label=(\roman*)]
\item The first letter of $\bw$ is either $e_{n-1,0}$ or $a_{n-1,j,0}$ where $0\leq j\leq n-1$.
\item The last letter of $\bw$ is either $e_{0,k}$ or $a_{0,0,k-1}$.
\item The letter following $a_{i,j,l}$ is either $e_{i-1,l+1}$ or $a_{i-1,j',l+1}$ where $j\leq j' \leq i-1$.
\item The letter following $e_{i,l}$ is either $e_{i-1,l}$ or $a_{i-1,j,l}$ where $ 0\leq j\leq i-1$.
\end{enumerate}
Furthermore, in this case the word $\bw$ has length $n$
and the path $\cal P$ is unique.
\end{lemma}

\begin{proof}[Sketch of proof]
Parts (i) and (ii) follow from examining the indices of the
first (resp.\ last) coloured edge in $\calP$.
Parts (iii) and (iv) follow from the observation that whenever a
horizontal edge is traversed, $l$ increases by $1$ and $i$ decreases
by $1$; and similarly, when a diagonal coloured edge is traversed,
$l$ remains unchanged and $i$ decreases by $1$. Furthermore, whenever a
coloured horizontal edge is followed immediately by another coloured
edge, the index $j$ is weakly increasing.
%% {\bf Alex suggests to augment this proof a bit.
%%    Or alternatively, we could say ``Sketch of proof.''}
\end{proof}

%% We now have a complete characterisation of the words
%% in the alphabet $\calA\cup\calE$ that correspond to
%% paths in the planar network $D'$.
%% In the following subsection we give
We now construct
a bijection between paths in $D'$
(represented via Lemma~\ref{lemma.pathword} as words)
and set partitions.
%
%\subsection{Set partitions to words, and vice versa}
%
%% Throughout the rest of the paper use the terms \emph{opener},
%% \emph{closer}, \emph{insider} and \emph{singleton} as defined in
%% Section~3.1 of \cite{Sokal_20}.
%
Given a set partition $\pi \in \Pi_n$,
we say that an element $i \in [n]$ is\hspace*{-2mm}
%\vspace*{-2mm}
\begin{itemize}
   \item an \emph{opener} if it is the smallest element of a
      block of size $\ge 2$;  \\[-8mm]
   \item a \emph{closer} if it is the largest element of a
      block of size $\ge 2$;  \\[-8mm]
   \item an \emph{insider} if it is a non-opener non-closer element of a
      block of size $\ge 3$;  \\[-8mm]
   \item a \emph{singleton} if it is the sole element of a block of size 1.
\end{itemize}
%\vspace*{-2mm}
% Clearly every element $i \in [n]$ belongs to precisely one of these
% four classes.
Also, for $i \in [n]$ and $\pi \in \Pi_n$,
we write $\mathrm{smallest}(\pi,i)$
%% [resp.\ $\mathrm{largest}(\pi,i)$]
for the smallest
%% (resp.\ largest)
element of the block of $\pi$ that contains $i$.

Given a set partition $\pi \in \Pi_{n+1,k}$
consisting of blocks $B_1,\ldots,B_k$,
we define a total order $\orp$ on $[n+1]$
by the following procedure:
start by taking the block containing~1 (we call it~$B_1$) together with the
largest elements of all the other blocks, and put them in increasing order;
then insert all the remaining elements of each block
% (other than the block containing~1)
(other than~$B_1$) in increasing order
immediately preceding its largest element.
For example,
for $\pi = \{ \{\textcolor{red}{1},\textcolor{red}{5},\textcolor{red}{8}\},
              \{2,3,\textcolor{red}{9}\}, \{4,\textcolor{red}{7}\},
              \{\textcolor{red}{6}\} \} \in \Pi_{9,4}$,
the order is $\textcolor{red}{156}4\textcolor{red}{78}23\textcolor{red}{9}$.
%
% according to the following relations:
% \begin{enumerate}[label=(\roman*)]
% \item For $i,j\in B$, $i\orp j$ if and only if $i<j$.
% 
% \item For $i\in B$, $j\in B'$, $B\neq B'$,
%      where $\smallest{\pi,i}\neq1$ and $\smallest{\pi,j}\neq 1$,
%      $i\orp j$ if and only if $\largest{\pi,i}<\largest{\pi,j}$.
% 
% \item If $\smallest{\pi,i}= 1$ and $\smallest{\pi,j}\neq 1$,
%      then $i\orp j$ if and only if $i<\largest{\pi,j}$.
% \end{enumerate}
%


Under this total order, $1$ is the smallest element and $n+1$ is the largest;
it can therefore be written as $1 p_1 p_2 \cdots p_n$ where $p_n = n+1$.
%
% and the covering relations $\cop$ are:
% \begin{enumerate}[label=(\roman*)]
% \item Given $j$ such that $\smallest{\pi,j}\neq j,1$ then $i\cop j$ where $i$ is the largest element smaller than $j$ in the block containing $j$.
% \item Let $L=\{i : i=\largest{\pi,i} \text{ and } \smallest{\pi,i}\neq 1\}$ and let $B_1$ be the block containing $1$. Also suppose we have $j$ such that $\smallest{\pi,j}$ is either $j$ or $1$. Let $j'=j$ if $j\in B_1$ and $j'=\largest{\pi,j}$ otherwise. Then $i\cop j$ implies $i$ is the largest element in $B_1\cup L$ smaller than $j'$.
% \end{enumerate}
%
We then define the word associated to a set partition $\pi\in\Pi_{n+1,n-k+1}$
to be $W(\pi) \ceq w_n \cdots w_1$
% \be
%     W(\pi) \;\ceq\; w_n \cdots w_1
% \ee
%% for $1\cop p_{1}\cop\ldots\cop p_{n-1}\cop p_{n}=n+1$, where
where
\be
   w_i
   \;\ceq\;
   \begin{cases}
      e_{i-1,\: l_i}       & \textrm{if $\smallest{\pi,p_i} = p_i$} \\
      a_{i-1,\: 0,\: l_i}  & \textrm{if $p_i\in B_1$ \ 
             [i.e.\ $\smallest{\pi,p_i} = 1$]}  \\
      a_{i-1,\: j,\: l_i}  & \textrm{if $\smallest{\pi,p_i}\neq 1,p_i$
                                     and $\largest{\bp,i}_j = p_{i-1}$}
   \end{cases}
 \label{def.wi}
\ee
Here $\largest{\bp,i}_j$ denotes the $j$th largest element
of the set $[2,n+1]\setminus\{p_i,\ldots,p_n\}$.
The index $l_i$ is defined recursively:
we set $l_n=0$, and for $i<n$ we define
% $l_{i-1} = l_i + \mathcal{I}[\smallest{\pi,p_i}\neq p_i]$,
% where $\mathcal{I}[\mathbb{P}]$ is the indicator function
% evaluating to $1$ if the predicate $\mathbb{P}$ is true
% and $0$ if $\mathbb{P}$ is false.
$l_{i-1} = l_i$ if $\smallest{\pi,p_i} = p_i$,
and $l_{i-1} = l_i + 1$ otherwise.
%% Note that $l_1$ is either $k-1$ (if $p_1 \in B_1$)
%% or $k$ (if $p_1 \notin B_1$).
                

\begin{lemma}
   \label{lemma.setpartword}
Given $\pi\in \Pi_{n+1,n-k+1}$, the word $W(\pi)$
consists of letters from $\calA\cup \calE$ and satisfies the conditions
in Lemma~\ref{lemma.pathword}, thereby corresponding to a path
$\calP \in \bP_{n,k}$.
\end{lemma}

\begin{proof}[Outline of proof]
We first verify that $w_i\in \calA\cup \calE$ (this is easy);
then we check the four conditions of Lemma~\ref{lemma.pathword}
(this requires some consideration of cases).
\end{proof}


\commentout{
{\bf FULL PROOF, TO BE COMMENTED OUT WHEN WE'RE FINISHED:}
\begin{proof}
To check that $w_i\in \calA\cup \calE$, we need only verify
that if $w_i=a_{i-1,j,l}$ then $j \leq i-1$.
This is clearly true if $p_i\in B_1$, in which case $j=0$.
Otherwise, since $[2,n+1]\setminus\{p_i,\ldots,p_n\}$ has cardinality $i-1$,
and $\largest{\bp,i}_j=p_{i-1}$ is the $j^{\mathrm{th}}$-largest
element in this set, $j$ can be at most $i-1$.
%% In both cases we have $0\leq j\leq i-1$.
Now we check the four conditions of Lemma~\ref{lemma.pathword}.

(i) The element $p_n=n+1$ is the largest element of some block $B$.
If it is a singleton we have $w_n=e_{n-1,0}$, and if $B=B_1$ we have
$w_n=a_{n-1,0,0}$. Otherwise, the next-largest element in $B$ is
$p_{n-1} = n+1-j$ for some $1\leq j \leq n-1$, so $p_{n-1}$ is the
$j$th-largest element in $[2,n+1]\setminus\{n+1\}=[2,n]$,
and $w_n = a_{n-1,j,0}$.

(ii) Since $\pi$ comprises $n-k+1$ blocks (one of which is $B_1$),
there are exactly $n-k$ indices $i$ for which $\smallest{\pi,p_i} = p_i$.
These are exactly the indices for which $l_{i-1} = l_i$;
and for them we have $w_i = e_{i-1,l_i}$.
Note that $p_1$ is either the smallest element of its block
or the second-smallest element of $B_1$.
In the first case $l_1 = k$ and $w_1 = e_{0,k}$,
while in the second case $l_1 = k-1$ and $w_1 = a_{0,0,k-1}$.

(iii) If $w_{i+1} = a_{i,j,l}$ (where $l = l_{i+1}$),
we have $\smallest{\pi,p_{i+1}} \neq p_{i+1}$ and hence $l_i = l + 1$;
we also have $\largest{\bp,i+1}_j = p_i$.
We treat the cases $j=0$ and $j\neq 0$ separately.
If $j=0$, then $p_{i+1} \in B_1$. If $p_i$ is a singleton,
then $w_i = e_{i-1,l+1}$. Otherwise, $w_i = a_{i-1,j',l+1}$ for some
$0\leq j'\leq i-1$, where the inequality follows from the fact that
$w_i\in \calA$. If instead $j\neq 0$, then $p_{i+1}$ is contained
in a block $B\neq B_1$ and $\min(B)\neq p_{i+1}$.
The element $p_{i}$ is thus the next-largest element of $B$
(just below $p_{i+1}$).
If $p_i=\min(B)$, then $w_i=e_{i-1,l+1}$.
Otherwise, $w_{i} = a_{i-1,j',l+1}$ and we only need to check that
$j\leq j'\leq i-1$. The upper bound is clearly true since $w_i\in \calA$.
If $j'<j$, then $\largest{\bp,i+1}_{j'}>p_i$,
which implies $\largest{\bp,i}_{j'}=\largest{\bp,i+1}_{j'}$, that is,
$p_{i-1}>p_i$, a contradiction.

(iv) If $w_{i+1} = e_{i,l}$ (where $l = l_{i+1}$),
we have $\smallest{\pi,p_{i+1}} = p_{i+1}$ and hence $l_i = l$.
If $p_i$ is a singleton, then $w_{i}=e_{i-1,l}$;
otherwise, $w_i=a_{i-1,j,l}$, where $0\leq j\leq i-1$ because $w_i\in \calA$.
This completes the proof.
\end{proof}
}


Lemmas~\ref{lemma.pathword} and \ref{lemma.setpartword} together define
a map $\Phi_{n,k} \colon\, \Pi_{n+1,n-k+1}\to \bP_{n,k}$.

\begin{theorem}
   \label{thm.bijection}
The map $\Phi_{n,k}$ is a bijection of $\Pi_{n+1,n-k+1}$ onto $\bP_{n,k}$.
\end{theorem}

\begin{proof}[Outline of proof]
Given a word $\bw=w_n\cdots w_1$
satisfying the conditions in Lemma~\ref{lemma.pathword},
we construct a set partition $\pi \in \Pi_{n+1,n-k+1}$
satisfying $W(\pi) = \bw$; this will show surjectivity.
We also show that $\pi$ is the unique set partition
with this property, showing injectivity.
We build up $\pi$ by inserting elements into its blocks,
one at a time, as we read the word $\bw$ from left to right,
beginning from $\pi_0 = \{\{1\}\}$ and ending with $\pi_n = \pi$.
Each block will be built up in decreasing order,
starting with its largest element;
indeed, each block other than $B_1$
will be built from start to finish in successive stages of the algorithm.
Whenever we insert an element $q_i \in [2,n+1]$ into a block $B \neq B_1$,
we also declare whether that block is
\emph{finished} (i.e.\ $q_i$ is an opener or a singleton in $\pi$)
or \emph{unfinished} (i.e.\ $q_i$ is a closer or an insider in $\pi$).
At each stage there will be at most one unfinished block.
We show \emph{a~posteriori} that $q_i$ equals
the $p_i$ associated to the total order $\orp$.

When we read a letter $w_i$,
we choose an element $q_i \in [2,n+1]$
that is not already contained in $\pi_{n-i}$,
and insert it into $\pi_{n-i}$ in one of five ways:
insert $q_i$ into the block $B_1$;
insert $q_i$ as an opener into an unfinished block $B\neq B_1$;
% (thereby declaring the block finished);
insert $q_i$ as an insider into an unfinished block $B\neq B_1$;
% (thereby declaring the block still unfinished);
create a new block containing $q_i$ as a singleton;
% (thereby declaring the block finished);
or create a new block containing $q_i$ as a closer.
% (thereby declaring the block unfinished).
The result is called $\pi_{n-i+1}$.
% Let us remark that, at each stage,
% there will be at most one unfinished block $B \neq B_1$;
% moreover, a new block will be created only if there are no unfinished blocks
% $B \neq B_1$.

To construct the sequence $\bq = q_n \cdots q_1$,
%% from the word $\bw = w_n \cdots w_1$.
we start from $q_n = n+1$.
Then, for $i < n$, we proceed inductively:
if $w_{i+1} = a_{i,j,l}$ with $j > 0$,
we set $q_i$ to be the $j$th largest element
of the set $[2,n+1] \setminus \{q_{i+1},\ldots,q_n\}$;
otherwise we set $q_i$ to be the largest element
of $[2,n+1] \setminus \{q_{i+1},\ldots,q_n\}$.
%% In the former case this is obviously the only choice
%% compatible with \reff{def.wi};
%% the latter choice will be justified later. {\bf ?????}

The elements $q_n,\ldots,q_1$ are inserted successively
into the set partition as follows:
By Lemma~\ref{lemma.pathword}
there are three possibilities for the letter $w_i$:
$e_{i-1,l}$, $a_{i-1,0,l}$, or $a_{i-1,j,l}$ for some $1\leq j\leq i-1$.

Case 1: $w_i = e_{i-1,l}$.
If there is an unfinished block, we insert $q_i$ into that block as an opener;
otherwise, we create a new block with $q_i$ as a singleton.
% In both cases the block is declared finished.

Case 2: $w_i = a_{i-1,0,l}$.
We insert $q_i$ into block $B_1$.
% (We remark that whenever this happens, $\pi_{n-i}$ has no unfinished blocks.)

Case 3: $w_i = a_{i-1,j,l}$ for some $1\leq j\leq i-1$.
If there is an unfinished block, we insert $q_i$ into that block as an insider;
otherwise, we create a new block with $q_i$ as a closer.
% In both cases the block is declared unfinished.

We then prove: 1) the claims about the order in which the blocks are built;
2) that $\bp = \bq$; 3) that $W(\pi) = \bw$; and 4) that the map is injective.
All these steps require some consideration of cases.
\end{proof}


\commentout{
{\bf FULL PROOF, TO BE COMMENTED OUT WHEN WE'RE FINISHED:}
\begin{proof}
Given a word $\bw=w_n\cdots w_1$ in the alphabet $\calA\cup\calE$
satisfying the conditions in Lemma~\ref{lemma.pathword},
we will construct a set partition $\pi \in \Pi_{n+1,n-k+1}$
satisfying $W(\pi) = \bw$; this will show surjectivity.
We will also show that $\pi$ is the unique set partition
with this property, thereby showing injectivity.
We will build up $\pi$ by inserting elements into its blocks,
one at a time, as we read the word $\bw$ from left to right,
beginning from $\pi_0 = \{\{1\}\}$ and ending with $\pi_n = \pi$.
Each block will be built up in decreasing order,
starting with its largest element;
indeed, each block other than $B_1$
will be built from start to finish in successive stages of the algorithm.
Whenever we insert an element $q_i \in [2,n+1]$ into a block $B \neq B_1$,
we will also declare whether that block is
\emph{finished} (i.e.\ $q_i$ is an opener or a singleton in $\pi$)
or \emph{unfinished} (i.e.\ $q_i$ is a closer or an insider in $\pi$).
We will show \emph{a posteriori} that $q_i$ equals
the $p_i$ associated to the total order $\orp$.

Every time we read a letter $w_i$,
we choose an element $q_i \in [2,n+1]$
that is not already contained in $\pi_{n-i}$,
and insert it into $\pi_{n-i}$ in one of five ways:
insert $q_i$ into the block $B_1$;
insert $q_i$ as an opener into an unfinished block $B\neq B_1$
(thereby declaring the block finished);
insert $q_i$ as an insider into an unfinished block $B\neq B_1$
(thereby declaring the block still unfinished);
create a new block containing $q_i$ as a singleton
(thereby declaring the block finished);
or create a new block containing $q_i$ as a closer
(thereby declaring the block unfinished).
The result is called $\pi_{n-i+1}$.
% Let us remark that, at each stage,
% there will be at most one unfinished block $B \neq B_1$;
% moreover, a new block will be created only if there are no unfinished blocks
% $B \neq B_1$.

We first specify how to construct the sequence $\bq = q_n \cdots q_1$.
%% from the word $\bw = w_n \cdots w_1$.
We start from $q_n = n+1$.
Then, for $i < n$, we proceed inductively:
if $w_{i+1} = a_{i,j,l}$ with $j > 0$,
we set $q_i$ to be the $j$th largest element
of the set $[2,n+1] \setminus \{q_{i+1},\ldots,q_n\}$;
otherwise we set $q_i$ to be the largest element
of $[2,n+1] \setminus \{q_{i+1},\ldots,q_n\}$.
%% In the former case this is obviously the only choice
%% compatible with \reff{def.wi};
%% the latter choice will be justified later. {\bf ?????}

We now explain how the elements $q_n,\ldots,q_1$ will be inserted
into the set partition.
At stage $i$ (starting from $i=n$ and proceeding downwards),
by Lemma~\ref{lemma.pathword}
there are three possibilities for the letter $w_i$:
$e_{i-1,l}$, $a_{i-1,0,l}$, or $a_{i-1,j,l}$ for some $1\leq j\leq i-1$.

Case 1: $w_i = e_{i-1,l}$.
If there is an unfinished block, we insert $q_i$ into that block as an opener;
otherwise, we create a new block with $q_i$ as a singleton.
In both cases the block is declared finished.

Case 2: $w_i = a_{i-1,0,l}$.
We insert $q_i$ into block $B_1$.
(We remark that whenever this happens, $\pi_{n-i}$ has no unfinished blocks.)

Case 3: $w_i = a_{i-1,j,l}$ for some $1\leq j\leq i-1$.
If there is an unfinished block, we insert $q_i$ into that block as an insider;
otherwise, we create a new block with $q_i$ as a closer.
In both cases the block is declared unfinished.

It is clear that each stage there is at most one unfinished block,
so the algorithm is well-defined.
Moreover, Lemma~\ref{lemma.pathword}(iii)
guarantees that last $a_{i,j,l}$ with $j>0$
must be immediately followed by an $e_{i-1,l+1}$,
so the algorithm will terminate with all blocks finished;
and an element $q_i$ inserted as an insider, closer, etc.\ 
will indeed have that status in the final set partition $\pi_n$.

Let us now prove the claims about the order in which each block is built.
For blocks $B \neq B_1$, we observe from Lemma~\ref{lemma.pathword}(iii)
that each maximal subword of $\bw$ consisting of letters $a_{i,j,l}$
with $j > 0$ must be immediately followed by an $e_{i',l'}$,
and in this subword the indices $j$ must be weakly increasing.
These facts ensure that the elements of $B$ are inserted in decreasing order,
and in successive stages.
(The first element of $B$ was the largest available element
 at the time of its insertion,
 because the letter $w_{i+1}$ immediately preceding this subword
 was \emph{not} of the form $a_{i,j,l}$ with $j > 0$.)
For the block $B_1$, elements (other than~1) were also inserted
in decreasing order:  by Lemma~\ref{lemma.pathword}(iii),
$a_{i-1,0,l}$ cannot be immediately preceded by $a_{i,j,l}$ with $j > 0$,
so again each element inserted into $B_1$ was the largest available element.
Finally, the union of $B_1$ with the largest elements of the
remaining blocks was also inserted in decreasing order,
because each such element was the largest available element
at the time of its insertion.
All this taken together shows that the sequence $\bq$
%% in the algorithm
coincides with the sequence $\bp$ associated to the total order $\orp$.

We now show that $w_i = W(\pi)_i$ for $1 \le i \le n$.
% We now claim that the resulting set partition $\pi \ceq \pi_n$
% satisfies $W(\pi) = \bw$ and is the unique set partition that does so.
% We will do this by showing inductively that
% $(w_i,\ldots,w_n) = (W(\pi)_i,\ldots,W(\pi)_n)$
% for $1 \le i \le n$.
We first observe that the ``type'' of $w_i$
--- that is, $e$, $a_0$ or $a_{\neq 0}$ ---
coincides with that of $W(\pi)_i$,
because $q_i = p_i$ and Cases~1--3 of the algorithm
correspond to inserting $q_i$ with a status that
corresponds to the three cases of \reff{def.wi}.
Next we match the indices $i,j,l$.
Lemmas~\ref{lemma.pathword} and \ref{lemma.setpartword}
guarantee that the indices $i$ and $l$
in both $\bw$ and $W(\pi)$  are determined by the types, and therefore agree.
The indices $j$ matter only in the type $a_{\neq 0}$,
and the third case of \reff{def.wi} coincides with how $q_{i-1}$ is chosen.
This proves that $W(\pi) = \bw$.

Finally we prove injectivity.
Let $\pi$ and $\pi'$ be set partitions with $W(\pi) = W(\pi') = \bw$,
and let $\bp$ and $\bp'$ be the sequences associated to
the total orders $<_{\pi}$ and $<_{\pi'}$, respectively.
We will show inductively that $p_{i}=p_{i}'$
and $\pi|{\{1,p_i,\ldots,p_n\}} =\pi'|{\{1,p_i',\ldots,p_n'\}}$.

For the base case $i=n$, $p_n=p'_n = n+1$ is obvious.
Moreover, from Lemmas~\ref{lemma.setpartword} and \ref{lemma.pathword},
$w_n$ is either $e_{n-1,0}$ or $a_{n-1,j,0}$ for $0\leq j\leq n-1$.
From \reff{def.wi}, if $w_n$ is of type $e$ or $a_{\neq 0}$,
then $\pi|\{1,p_n\} = \{\{1\},\{n+1\}\} = \pi'|\{1,p'_n\}$;
and if $w_n$ is of type $a_{0}$,
then $\pi|\{1,p_n\} = \{\{1,n+1\}\} = \pi'|\{1,p'_n\}$.
This settles the base case.
 
Now consider $i < n$: we have two cases, depending on whether
$w_{i+1}$ is of type $a_{\neq 0}$ or types $a_{0},e$. 

$\bullet$ If $w_{i+1}= a_{i,j,l}$ for some $1\leq j \leq i$,
then $p_i=p'_{i}$ is clearly determined by the induction hypothesis
and \reff{def.wi};
moreover, $p_{i}=p_{i}'$ and $p_{i+1} = p_{i+1}'$
are in the same block $B \neq B_1$,
which establishes
$\pi|{\{1,p_i,\ldots,p_n\}} =\pi'|{\{1,p_i',\ldots,p_n'\}}$. 

$\bullet$ If $w_{i+1}$ is of type $e$ or $a_0$,
then by definition of the total order,
$p_i$ and $p_i'$ are both equal to the largest element of
$[2,n+1]\setminus\{p_i,\ldots,p_n\}$;
furthermore, this element $p_i = p'_i$ can either be in $B_1$
or else be the largest element of some block $B\neq B_1$.
From \reff{def.wi}, we see that the former (resp.\ latter)
will be true if $w_i$ is of type $a_0$ (resp.\ $e$ or $a_{\neq 0}$).
In both cases we have
$\pi|{\{1,p_i,\ldots,p_n\}} =\pi'|{\{1,p_i',\ldots,p_n'\}}$.
This concludes the proof.
%
%
% The index $i$ is determined:
% it simply decreases in both $\bw$ and $W(\pi)$.
% By Lemma~\ref{lemma.pathword}(iii,iv),
% the index $l$ increases except after a letter $e_{i,l}$,
% in which case it remains the same;
% this corresponds precisely to the definition of $l_i$
% in \reff{def.wi} ff.
%
% The base case $i=n$ is straightforward:
% and $w_n = W(\pi)_n$ follows by using Lemma~\ref{lemma.pathword}(i)
% and comparing the three cases in the algorithm
% with the three cases of \reff{def.wi}.
%
% Now consider $i < n$ and assume that
% $(p_{i+1},\ldots,p_n) = (q_{i+1},\ldots,q_n)$
% and $(w_{i+1},\ldots,w_n) = (W(\pi)_{i+1},\ldots,W(\pi)_n)$.
% 
% $\bullet$ If $w_{i+1} = a_{i,j,l}$ with $j > 0$, then 
% %% $w_{i+1}$ was in Case~3 and
% stage $i+1$ ended with an unfinished block,
% and Lemma~\ref{lemma.pathword}(iii) implies that $w_i$ cannot be in Case~2;
% therefore $q_i$ and $q_{i+1}$ are in the same block
% 
% 
% 
% given $p_{i+1},\ldots,p_n$ and $\pi_{n-i}$,
% there is a unique choice of $p_i$ and
% and a unique way of inserting it into $\pi_{n-i}$
% that is compatible with \reff{def.wi},
% in the sense that ????????????????????????????.
% We will also show inductively that $q_i$ equals
% the $p_i$ associated to the total order $\orp$.
% 
% The base case is clear: $p_n = q_n = n+1$.
% Given $(p_{i+1},\ldots,p_n) = (q_{i+1},\ldots,q_n)$
% and the letters $w_{i+1},\ldots,w_n$
%
%
% By Lemma~\ref{lemma.pathword}(i) there are three possibilities for $w_n$:
% $e_{n-1,0}$, $a_{n-1,0,0}$, or $a_{n-1,j,0}$ for some $1\leq j\leq n-1$.
% In the first case, we insert $n+1$ into $\pi_0$ as a singleton
% (and hence declare that block finished);
% in the second case, we adjoin $n+1$ to the block containing~1;
% and in the third case, we insert $n+1$ as the largest element of a block
% in which the next-largest element of that block will be $p_{n-1} = n+1-j$.
% {\bf Is this compatible with how $p_{n-1}$ will be determined
%   when we read the letter $w_{n-1}$???
%   I am confused about \emph{when} we make these different choices.}
%
% \bigskip
% 
% {\bf OLD STUFF:}
% Now suppose that the current letter is $w_i$ (with $i < n$).
% % If the preceding letter $w_{i+1}$ is $a_{i,j,l}$ with $1 \le j \le i$,
% % then from the construction of $\Phi_{n,k}$ we see that,
% % given $p_{i+1},\ldots,p_n$, there is at most one allowable choice for $p_i$,
% % namely the $j$th-largest element of the set
% % $[2,n+1]\setminus\{p_{i+1},\ldots,p_n\}$, which has cardinality $i$.
% % hence $w_{i+1}$ determines $p_i$ in this case.
% By Lemma~\ref{lemma.pathword}(iii),
% the letter $w_i$ is either $e_{i-1,l+1}$ or $a_{i-1,j,l+1}$,
% which determines if $p_i$ is the closer of the block containing $p_{i+1}$
% or if it is an insider of that block, respectively.
% {\bf Can't $w_i$ be $a_{i-1,j',l+1}$ for any $j' \in [j,i-1]$???}
% 
% If $w_{i+1}=a_{i,0,l}$ or $w_{i+1}=e_{i,l}$
% then either $p_i\in B_1$ or $p_i\in L$.
% {\bf What is $L$?????}
% By definition, $p_i$ must be the largest element in
% $[2,n+1]\setminus\{p_{i+1},\ldots,p_n\}$,
% since if we have $p_{i'}$ such that $p_{i'}>p_i$ for $i'>i$,
% then $p_{i'}\orp p_{i}$ in some set partition.
% This also implies that $p_i$ and $p_{i'}$ cannot be in the same block,
% hence $p_{i'}<\largest{\bp,i}=p_i$, a contradiction.
% It follows that we have exactly one choice for $p_i$,
% thereby completing the proof.
% 
% {\bf Have we proven both surjectivity and injectivity???}
\end{proof}
}



% Everything is now in place for us to prove Theorem~\ref{thm.pathmatrix.ace}.

\begin{proof}[Second proof of Theorem~\ref{thm.pathmatrix.ace}]
%% Theorem~\ref{thm.bijection} and its proof(?????) tell us that,
The definition \reff{def.wi} tells us that,
within each word $\bw$,
the letters $a_{i,0,l}$ correspond to elements in $B_1$,
and the letters $e_{i,l}$ (resp.\ $a_{i,j,l}$ for $j>0$)
correspond to minimal (resp.\ non-minimal) elements of blocks $B \neq B_1$.
After the specialisations $e_{i,l} \to e$,
$a_{i,0,l} \to c$, and $a_{i,j,l} \to a$ for $j > 0$,
by Proposition~\ref{prop.deb}(ii) this is precisely the matrix $\bT(a,c,0,e)$.
\end{proof}

% {\bf OLD STUFF, CAN BE COMMENTED OUT:}
% Everything is now in place for us to prove Theorem~\ref{thm.Tace}.
% 
% \begin{proof}[Proof of Theorem~\ref{thm.Tace}]
% In the matrix $\bT$ of Proposition~\ref{prop.calAE},
% let us make the specializations $e_{i,l} \to e$,
% $a_{i,0,l} \to c$, and $a_{i,j,l} \to a$ for $j > 0$.
% The resulting matrix with entries in $\Z[a,c,e]$
% is coefficientwise totally positive.
% On the other hand, Theorem~\ref{thm.bijection} and its proof(?????)
% tell us that, within each word $\bw$,
% the letters $a_{i,0,l}$ correspond to elements in $B_1$,
% and the letters $e_{i,l}$ (resp.\ $a_{i,j,l}$ for $j>0$)
% correspond to minimal (resp.\ non-minimal) elements of blocks $B \neq B_1$.
% By Proposition~\ref{prop.deb}(ii) this is precisely the matrix
% $\bT(a,c,0,e)$.
% \end{proof}

%% {\bf Can we do better, and interpret at least \emph{some} of the indices
%%   $i,j,l$ in terms of set partitions???}

% By virtue of the bijection $\Phi_{n,k}$ it follows that the
% $(n,k)$-entry of the path matrix corresponding to $D'$ is the sum
% over weighted set partitions of $[n+1]$ into $n-k+1$ blocks where the
% weight of each partition corresponds to a word of length $n$ comprising
% letters from the alphabet $\calA\cup\calE$. Within each word, the
% letters $a_{i,0,l}$ correspond to elements in $B_1$ and $a_{i,j,l},$
% and $e_{i,l}$ correspond to non-minimal, and minimal elements of
% the other blocks respectively, so by replacing $a_{i,0,l}$ with $c$,
% $a_{i,j,l}$ with $a$, and $e_{i,l}$ with $e$ for $i,j,l$ where $j>0$
% we obtain a matrix $M_D$ whose entries are polynomials in $\Z[a,c,e]$
% corresponding to sums over set partitions weighted according
% to~\eqref{eq.prop.deb.b2} in Proposition~\ref{prop.deb}. It follows
% that $M_D=\bT(a,c,0,e)$, so according to the Lindstr\"om-Gessel-Viennot
% Lemma $\bT(a,c,0,e)$ is coefficientwise totally positive.  \end{proof}




%% \section{Final remarks}

\section*{Acknowledgements}
We wish to thank Sergey Fomin for helpful correspondence.
This research was supported in part by
the U.K.~Engineering and Physical Sciences Research Council grant EP/N025636/1,
a fellowship from the China Scholarship Council,
and a fellowship from the Deutsche Forschungsgemeinschaft.

%% if you use biblatex then this generates the bibliography
%% if you use some other method
%% then remove this and do it your own way

\printbibliography



\end{document}
