# Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness

Bishal Deb, Alan D Sokal

<figure><img src="image_1.png" /></figure>

## To cite this version:

Bishal Deb, Alan D Sokal. Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness. 2025. hal-05213917

HAL Id: hal-05213917

https://hal.science/hal-05213917v1

Preprint submitted on 19 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness

Bishal Deb¹ and Alan D. Sokal²,³

¹Yau Mathematical Sciences Center, Tsinghua University, Beijing 100084, China

²Department of Mathematics, University College London, London WC1E 6BT, UK

³Department of Physics, New York University, New York, NY 10003, USA

bishal@gonitsora.com, sokal@nyu.edu

July 24, 2025

## Abstract

Given a lower-triangular matrix of real numbers, one can ask the following four total-positivity questions: total positivity of the triangle itself; total positivity of its row-reversal; Toeplitz-total positivity of its row sequences (equivalent to negative-real-rootedness of the row-generating polynomials); and coefficientwise Hankel-total positivity of the sequence of row-generating polynomials. In this paper, we introduce two infinite families of lower-triangular matrices generalising the Stirling cycle and subset triangles, parametrised by an integer $r \ge 1$; we call these the $r$th-order Stirling cycle and subset numbers. We then ask the foregoing four questions for each of these triangles, leading us to several conjectures. We then prove some of these conjectures for the case $r=2$.

**Key Words:** Totally positive matrix, Hankel matrix, zeros of polynomials, higher-order Stirling cycle numbers, higher-order Stirling subset numbers, Stirling permutations, increasing ternary trees, increasing ordered trees, branched continued fractions, permutations, set partitions, phylogenetic trees, log-concavity.

**Mathematics Subject Classification (MSC 2020) codes:** 05A15 (Primary); 05A05, 05A18, 05A19, 05A20, 11B73, 15B48, 30B70 (Secondary).
# Contents

<table><tbody><tr><td>1</td><td>Introduction and statement of main results</td><td>3</td></tr><tr><td>1.1</td><td>Higher-order Stirling cycle and subset numbers</td><td>5</td></tr><tr><td>1.2</td><td>Relation with the second-order Eulerian numbers</td><td>8</td></tr><tr><td>1.3</td><td>Statement of main conjectures and results</td><td>9</td></tr><tr><td>1.4</td><td>Higher-order Eulerian and quasi-Eulerian numbers: Statement of conjectures</td><td>12</td></tr><tr><td>1.5</td><td>Structure of this paper</td><td>14</td></tr><tr><td>2</td><td>Algebraic proof of Proposition 1.2</td><td>15</td></tr><tr><td>3</td><td>Combinatorial proof of Proposition 1.2(a)</td><td>16</td></tr><tr><td>3.1</td><td>Interpretation I: Derangements</td><td>16</td></tr><tr><td>3.2</td><td>Interpretation II: Stirling permutations</td><td>16</td></tr><tr><td>3.3</td><td>Proof of Proposition 1.2(a) and Theorem 1.5</td><td>17</td></tr><tr><td>4</td><td>Second-order Stirling cycle numbers: Three further combinatorial interpretations</td><td>19</td></tr><tr><td>4.1</td><td>Interpretation III: Increasing ternary trees</td><td>19</td></tr><tr><td>4.2</td><td>Interpretation IV: Increasing ordered trees</td><td>21</td></tr><tr><td>4.2.1</td><td>Bijective proof of Proposition 4.5</td><td>21</td></tr><tr><td>4.2.2</td><td>Generating-function proof of Proposition 4.5</td><td>25</td></tr><tr><td>4.2.3</td><td>Vertex-marked increasing ordered trees</td><td>29</td></tr><tr><td>4.3</td><td>Interpretation V: Cyclically-ordered phylogenetic trees</td><td>30</td></tr><tr><td>4.4</td><td>A final remark</td><td>34</td></tr><tr><td>5</td><td>Interpretation for r-th order Stirling cycle numbers</td><td>35</td></tr><tr><td>6</td><td>Location of zeros for the second-order Stirling cycle and subset polynomials</td><td>37</td></tr><tr><td>7</td><td>Location of zeros for order r ≥ 3</td><td>38</td></tr><tr><td>7.1</td><td>Existence of nonreal roots for r ≥ 3</td><td>39</td></tr><tr><td>7.2</td><td>Stirling cycle polynomials of order r ≥ 3</td><td>41</td></tr><tr><td>7.3</td><td>Stirling subset polynomials of order r ≥ 3</td><td>44</td></tr><tr><td>A</td><td>Tables of higher-order Stirling cycle and subset numbers</td><td>46</td></tr><tr><td>A.1</td><td>Higher-order Stirling cycle numbers</td><td>46</td></tr><tr><td>A.2</td><td>Higher-order Stirling subset numbers</td><td>47</td></tr><tr><td>B</td><td>Tables of higher-order quasi-Eulerian cycle and subset numbers</td><td>48</td></tr><tr><td>B.1</td><td>Higher-order quasi-Eulerian cycle numbers</td><td>48</td></tr><tr><td>B.2</td><td>Higher-order quasi-Eulerian subset numbers</td><td>49</td></tr><tr><td>C</td><td>Report on systematic verification of conjectures</td><td>50</td></tr><tr><td></td><td>Bibliography</td><td>51</td></tr></tbody></table>
# 1 Introduction and statement of main results

A (finite or infinite) matrix of real numbers is called **totally positive** (TP) if all its minors are nonnegative. A matrix of polynomials with real coefficients is called **coefficientwise totally positive** if all its minors are polynomials with nonnegative coefficients. Let $A = (a_{n,k})_{n,k\ge 0}$ be a lower-triangular matrix of nonnegative real numbers. One can then ask the following four questions:

(a) Is $A$ totally positive?

(b) Is the lower-triangular matrix $A^{\text{rev}} \stackrel{\text{def}}{=} (a_{n,n-k})_{n,k\ge 0}$, obtained by reversing the rows of $A$, totally positive? (Here $a_{n,n-k} \stackrel{\text{def}}{=} 0$ when $n < k$.)

(c) Let $A_n(x) = \sum_{k=0}^n a_{n,k} x^k$ denote the row-generating polynomial of the $n$-th row of $A$. Are the polynomials $A_n(x)$ negative-real-rooted?<fnref n="1" /> This is equivalent [33, pp. 395, 399] to asking if the Toeplitz matrix of the $n$-th row sequence $(a_{n,k})_{k\ge 0}$ — that is, the matrix $(a_{n,i-j})_{i,j\ge 0}$ with $a_{n,k} \stackrel{\text{def}}{=} 0$ for $k < 0$ — is totally positive. In this situation we say that the $n$-th row sequence $(a_{n,k})_{k\ge 0}$ is **Toeplitz-totally positive**.<fnref n="2" />

(d) Is the Hankel matrix of the polynomial sequence $(A_n(x))_{n\ge 0}$ — that is, the matrix $(A_{i+j}(x))_{i,j\ge 0}$ — coefficientwise totally positive in the variable $x$? In this situation we say that the sequence $(A_n(x))_{n\ge 0}$ is **coefficientwise Hankel-totally positive**. One sufficient but far-from-necessary condition for this to hold is for the ordinary generating function $\sum_{n=0}^{\infty} A_n(x) t^n$ to have a Stieltjes-type continued fraction (or more generally, a Thron-type continued fraction) with coefficients that are polynomials with nonnegative coefficients in the variable $x$.<fnref n="3" />

For several important combinatorial triangles, the answers to all four of these questions have either been proven to be yes or are conjectured to be yes. Some examples are:

(a) When $A = ((n)_{n,k})_{n,k\ge 0}$ is the matrix of binomial coefficients. The binomial matrix $A$ is well known to be totally positive, and there are many proofs of

<footnote n="1">¹A polynomial with real coefficients is said to be **real-rooted** if it is either identically zero or all its (complex) zeros are real; it is said to be **negative-real-rooted** if it is either identically zero or all its (complex) zeros lie in $(-\infty, 0]$. Since we are here assuming that all the matrix entries $a_{n,k}$ are nonnegative, clearly $A_n(x)$ cannot have any **positive** real zeros unless it is identically zero. So negative-real-rootedness and real-rootedness are equivalent here.</footnote>

<footnote n="2">²Sequences whose Toeplitz matrices are totally positive are also known as **Pólya frequency sequences**. The just-cited characterisation of *finitely supported* Pólya frequency sequences is a special case of the (much more difficult) theorem of Aissen, Edrei, Schoenberg and Whitney [3, 20] that characterises arbitrary Pólya frequency sequences [33, p. 412, Theorem 5.3].</footnote>

<footnote n="3">³This result for Stieltjes-type continued fractions (S-fractions) was first stated explicitly in [41]; see [38, Theorem 9.8] for a published proof (in fact of a much more general result). However, this result is in fact an easy corollary of Flajolet's [25] combinatorial interpretation of Stieltjes-type continued fractions together with Viennot's [46, Chapter 4, Section 3] combinatorial characterization of the Hankel minors. The generalization to Thron-type continued fractions (T-fractions) is given (again in much greater generality) in [38, Theorem 9.9].</footnote>
this fact: see e.g. [2, pp. 232–233] for a proof using the Lindström–Gessel–Viennot lemma. Here $A^{\text{rev}} = A$ as the rows are palindromic. The row-generating polynomials $A_n(x) = (1+x)^n$ are clearly negative-real-rooted. And finally, the sequence $((1+x)^n)_{n \ge 0}$ is coefficientwise Hankel-totally positive in the variable $x$: this can easily be seen directly, or it follows from the continued fraction $\sum_{n=0}^{\infty} (1+x)^n t^n = 1/[1-(1+x)t]$.

(b) When $A = (\begin{bmatrix} n \\ k \end{bmatrix})_{n,k \ge 0}$ is the matrix of Stirling cycle numbers, which count the permutations of $[n] \stackrel{\text{def}}{=} \{1, \dots, n\}$ with $k$ cycles. The total positivity of the matrix $A$ and its reversal $A^{\text{rev}}$ are due to Brenti [8] in 1995: they hold because the entries $\begin{bmatrix} n \\ k \end{bmatrix}$ satisfy a binomial-like recurrence with nonnegative $n$-dependent coefficients. The row-generating polynomials $A_n(x) = x(x+1)\cdots(x+n-1)$ are clearly negative-real-rooted. The sequence $(A_n(x))_{n \ge 0}$ has a Stieltjes-type continued fraction, first discovered by Euler [24] in 1760: see e.g. [42, eqn. (1.2)] [43, eqns. (2.2)/(2.6)]. This implies the coefficientwise Hankel-total positivity.

(c) When $A = (\begin{Bmatrix} n \\ k \end{Bmatrix})_{n,k \ge 0}$ is the matrix of Stirling subset numbers, which count the set partitions of $[n]$ with $k$ blocks. The total positivity of the matrix $A$ is due to Brenti [8] in 1995: it holds because the entries $\begin{Bmatrix} n \\ k \end{Bmatrix}$ satisfy a binomial-like recurrence with nonnegative $k$-dependent coefficients. However, the total positivity of the reversal $A^{\text{rev}}$ was only recently shown by us in [14]. The real-rootedness of the row-generating polynomials $A_n(x)$ was proven by Harper [30] in 1967. The sequence $(A_n(x))_{n \ge 0}$ has a Stieltjes-type continued fraction, discovered by various people in the second half of the twentieth century: see e.g. [43, eqns. (3.2)/(3.5) and footnote 19]. This implies the coefficientwise Hankel-total positivity.

(d) When $A = (\begin{Bmatrix} n \\ k \end{Bmatrix})_{n,k \ge 0}$, is the matrix of Eulerian numbers, which count the permutations on $[n]$ with $k$ descents (or $k$ excedances). The row-generating polynomials $A_n(x)$ were shown to be real-rooted by Frobenius [26] in 1910. The sequence $(A_n(x))_{n \ge 0}$ has a Stieltjes-type continued fraction going back to Stieltjes [45]: see e.g. [43, eqns. (2.2)/(2.8) and footnote 4]. This implies the coefficientwise Hankel-total positivity. In 1996, Brenti [9] conjectured that the matrix $A$ is totally positive; this conjecture is, alas, still open.<fnref n="4" /> Here the rows of $A$ are almost-palindromic in the sense that $\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{Bmatrix} n \\ n-1-k \end{Bmatrix}$ for $n \ge 1$; it easily follows from this that $A^{\text{rev}}$ is totally positive if and only if $A$ is. In [14] we have generalized Brenti's conjecture: we conjecture the coefficientwise total positivity of a lower-triangular matrix in six indeterminates that is defined by a particular recurrence; this matrix includes the Eulerian matrix, the Stirling subset matrix and the reversed Stirling subset matrix as special cases.

In this paper, we introduce two infinite families of lower-triangular matrices generalizing the Stirling cycle and subset triangles, parametrized by an integer $r \ge 1$: we call them the **r**$^{th}$-order Stirling cycle and subset triangles. For $r = 1$

<footnote n="4">⁴Dyachenko [18] has verified this conjecture for the leading 512 × 512 submatrix of the matrix $(\begin{Bmatrix} n+1 \\ k \end{Bmatrix})_{n,k \ge 0}$, by computing the bidiagonal factorization using Neville elimination [27].</footnote>
they reduce to the ordinary Stirling cycle and subset triangles. The central theme of this paper is to investigate the foregoing four questions for these triangular arrays. We have combined an experimental approach with proofs using both bijective and generating-function methods. Even though we are able to prove only very few of our conjectures — notably those for the case $r = 2$ — we have proven several interesting combinatorial interpretations for the $r$th-order Stirling triangles, and our results suggest further interesting consequences in the form of combinatorial interpretations and additional conjectures.

The rest of this introduction is structured as follows: In Section 1.1 we define the $r$th-order Stirling cycle and subset numbers and state some recurrences that these numbers satisfy; we also set up some basic notation for this paper. Then in Section 1.2 we introduce the second-order Eulerian numbers and relate them to the second-order Stirling cycle and subset numbers; this connection will play a major role in our proofs. We will also introduce two generalisations: the higher-order Eulerian numbers and the higher-order quasi-Eulerian numbers. In Section 1.3 we state our main conjectures on the higher-order Stirling cycle and subset numbers, and also state our theorems. In Section 1.4 we state some conjectures for the higher-order Eulerian and quasi-Eulerian numbers. In Section 1.5 we present the outline of the remainder of this paper.

## 1.1 Higher-order Stirling cycle and subset numbers

Several generalizations and extensions of the Stirling cycle and subset numbers have been introduced in the literature. One such family of generalizations are the *r-associated Stirling cycle and subset numbers*, defined as follows:

The *r-associated Stirling cycle number* $\begin{bmatrix} n \\ k \end{bmatrix}_r$ is the number of permutations on $[n]$ with $k$ cycles, all of which are of size $\ge r$ [16, pp. 256–257, 295]. Thus we have $\begin{bmatrix} n \\ k \end{bmatrix}_1 = \begin{bmatrix} n \\ k \end{bmatrix}$. Note that $\begin{bmatrix} n \\ k \end{bmatrix}_r$ is nonzero only when $n \ge rk$, or equivalently $k \le \lfloor n/r \rfloor$. See [35, A132393/A106828/A050211/A050212/A050213] for $1 \le r \le 5$.

Similarly, the *r-associated Stirling subset number* $\begin{Bmatrix} n \\ k \end{Bmatrix}_r$ is the number of set partitions of $[n]$ into $k$ blocks, all of which are of size $\ge r$ [16, pp. 221–222]. Thus we have $\begin{Bmatrix} n \\ k \end{Bmatrix}_1 = \begin{Bmatrix} n \\ k \end{Bmatrix}$. Note that $\begin{Bmatrix} n \\ k \end{Bmatrix}_r$ is nonzero only when $n \ge rk$, or equivalently $k \le \lfloor n/r \rfloor$. See [35, A048993/A008299/A059022/A059023/A059024/A059025] for $1 \le r \le 6$.

It is not difficult to show, by considering the possibilities for the element $n$ in the permutation or set partition, that the *r-associated Stirling cycle and subset numbers* satisfy the recurrences [16, pp. 222, 257]

$$ \begin{bmatrix} n \\ k \end{bmatrix}_r = (r-1)! \binom{n-1}{r-1} \begin{bmatrix} n-r \\ k-1 \end{bmatrix}_r + (n-1) \begin{bmatrix} n-1 \\ k \end{bmatrix}_r \quad (1.1) $$

$$ \begin{Bmatrix} n \\ k \end{Bmatrix}_r = \binom{n-1}{r-1} \begin{bmatrix} n-r \\ k-1 \end{bmatrix}_r + k \begin{Bmatrix} n-1 \\ k \end{Bmatrix}_r \quad (1.2) $$

For $r \ge 2$, the sequences of row-generating polynomials of these triangles are *not* coefficientwise Hankel-totally positive. This is because the $n$-th row-generating polynomial is of degree $\lfloor n/r \rfloor$ — not $n$ — and it follows from this that even the $2 \times 2$ Hankel minors must have some negative coefficients.
Instead, we modify these triangles by shifting the columns up until we get a lower-triangular matrix with nonzero diagonal entries. That is, we define, for each $r \ge 1$,

$$ \begin{bmatrix} n \\ k \end{bmatrix}^{(r)} \stackrel{\text{def}}{=} \begin{bmatrix} n + (r-1)k \\ k \end{bmatrix}_{r} \qquad (1.3) $$

$$ \begin{Bmatrix} n \\ k \end{Bmatrix}^{(r)} \stackrel{\text{def}}{=} \begin{Bmatrix} n + (r-1)k \\ k \end{Bmatrix}_{r} \qquad (1.4) $$

We call these the **r**$^{th}$-order Stirling cycle and subset numbers, respectively; and we call the lower-triangular matrices

$$ C^{(r)} \stackrel{\text{def}}{=} \left( \begin{bmatrix} n \\ k \end{bmatrix}^{(r)} \right)_{n,k \ge 0} \qquad (1.5a) $$

$$ S^{(r)} \stackrel{\text{def}}{=} \left( \begin{Bmatrix} n \\ k \end{Bmatrix}^{(r)} \right)_{n,k \ge 0} . \qquad (1.5b) $$

the **r**$^{th}$-order Stirling cycle and subset triangles. Of course we have

$$ \begin{bmatrix} n \\ k \end{bmatrix}^{(1)} = \begin{bmatrix} n \\ k \end{bmatrix}_{1} = \begin{bmatrix} n \\ k \end{bmatrix} \qquad (1.6) $$

$$ \begin{Bmatrix} n \\ k \end{Bmatrix}^{(1)} = \begin{Bmatrix} n \\ k \end{Bmatrix}_{1} = \begin{Bmatrix} n \\ k \end{Bmatrix} \qquad (1.7) $$

so that the numbers of order $r = 1$ are the usual Stirling cycle and subset numbers, respectively. For the convenience of the reader and for our use in the rest of the paper, we rewrite $(1.3)/(1.4)$ for $r = 2$:

$$ \begin{bmatrix} n \\ k \end{bmatrix}^{(2)} = \begin{bmatrix} n+k \\ k \end{bmatrix}_{2} \qquad (1.8) $$

$$ \begin{Bmatrix} n \\ k \end{Bmatrix}^{(2)} = \begin{Bmatrix} n+k \\ k \end{Bmatrix}_{2} \qquad (1.9) $$

The triangle $C^{(2)}$ is [35, A259456/A269940/A111999] and its row sums are [35, A032188]. The triangle $S^{(2)}$ is [35, A134991/A269939] and its row sums are [35, A000311]. The second-order Stirling subset numbers are often referred to as the **Ward numbers** [4, 13, 15, 23, 47]. The row sums of $C^{(r)}$ and $S^{(r)}$ for $r \ge 3$ are not currently in the OEIS [35]. In the Appendix we provide tables of the triangles $C^{(r)}$ and $S^{(r)}$ for $1 \le r \le 4$ and the first few values of $n$.

From the combinatorial definition one sees that the diagonal elements of the arrays $C^{(r)}$ and $S^{(r)}$ are

$$ \begin{bmatrix} n \\ n \end{bmatrix}^{(r)} = \begin{bmatrix} rn \\ n \end{bmatrix}_{r} = \frac{(rn)!}{r^n n!} \qquad (1.10) $$

$$ \begin{Bmatrix} n \\ n \end{Bmatrix}^{(r)} = \begin{Bmatrix} rn \\ n \end{Bmatrix}_{r} = \frac{(rn)!}{(r!)^n n!} \qquad (1.11) $$
[35, A001147/A052502/A060706/A052504] [35, A001147/A025035/A025036/A025037/A025038]. In particular, for $r = 2$ we have

$$ \begin{bmatrix} n \\ n \end{bmatrix}^{(2)} = \begin{Bmatrix} n \\ n \end{Bmatrix}^{(2)} = (2n-1)!!. \qquad (1.12) $$

The numbers $(2n-1)!!$ [10] [35, A001147] will play a central role in this paper: see Section 4.4 for an observation about this.

The recurrence relations $(1.1)/(1.2)$ for the $r$-associated Stirling cycle and subset numbers easily imply, by change of variables, the following recurrence relations for the $r$th-order Stirling cycle and subset numbers:

**Lemma 1.1.** (a) The numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)}$ satisfy the recurrence

$$ \begin{bmatrix} n \\ k \end{bmatrix}^{(r)} = (r-1)! \begin{pmatrix} n + (r-1)k - 1 \\ r-1 \end{pmatrix} \begin{bmatrix} n-1 \\ k-1 \end{bmatrix}^{(r)} + (n+(r-1)k-1) \begin{bmatrix} n-1 \\ k \end{bmatrix}^{(r)} \qquad (1.13) $$

for $n \ge 1$, with initial conditions $\begin{bmatrix} 0 \\ k \end{bmatrix}^{(r)} = \delta_{k0}$ and $\begin{bmatrix} n \\ -1 \end{bmatrix}^{(r)} = 0$.

(b) The numbers $\begin{Bmatrix} n \\ k \end{Bmatrix}^{(r)}$ satisfy the recurrence

$$ \begin{Bmatrix} n \\ k \end{Bmatrix}^{(r)} = \begin{pmatrix} n + (r-1)k - 1 \\ r-1 \end{pmatrix} \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}^{(r)} + k \begin{Bmatrix} n-1 \\ k \end{Bmatrix}^{(r)} \qquad (1.14) $$

for $n \ge 1$, with initial conditions $\begin{Bmatrix} 0 \\ k \end{Bmatrix}^{(r)} = \delta_{k0}$ and $\begin{Bmatrix} n \\ -1 \end{Bmatrix}^{(r)} = 0$.

When $r = 2$, the recurrences $(1.13)/(1.14)$ are

$$ \begin{bmatrix} n \\ k \end{bmatrix}^{(2)} = (n+k-1) \begin{bmatrix} n-1 \\ k-1 \end{bmatrix}^{(2)} + (n+k-1) \begin{bmatrix} n-1 \\ k \end{bmatrix}^{(2)} \qquad (1.15) $$

$$ \begin{Bmatrix} n \\ k \end{Bmatrix}^{(2)} = (n+k-1) \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}^{(2)} + k \begin{Bmatrix} n-1 \\ k \end{Bmatrix}^{(2)} \qquad (1.16) $$

Note that the coefficients here are affine in $n$ and $k$ (this is no longer the case for $r \ge 3$). It is curious that we see here the combination $n+k$, in contrast with the $n-k$ occurring in [14, eqs. (1.2)/(1.4)/(1.5)].

We write $c_{r,n}(x)$ for the row-generating polynomial of the $n$-th row of the matrix $C^{(r)}$; we call them the **r$^{th}$-order Stirling cycle polynomials**. Similarly, we write $s_{r,n}(x)$ for the row-generating polynomial of the $n$-th row of the matrix $S^{(r)}$; we call them the **r$^{th}$-order Stirling subset polynomials**. Thus, we have

$$ c_{r,n}(x) \stackrel{\text{def}}{=} \sum_{k=0}^{n} \begin{bmatrix} n \\ k \end{bmatrix}^{(r)} x^k \qquad (1.17) $$

$$ s_{r,n}(x) \stackrel{\text{def}}{=} \sum_{k=0}^{n} \begin{Bmatrix} n \\ k \end{Bmatrix}^{(r)} x^k \qquad (1.18) $$

Finally, we use $\tilde{C}^{(r)}$ and $\tilde{S}^{(r)}$ to denote the two row-reversed matrices $\tilde{C}^{(r)} \stackrel{\text{def}}{=} (C^{(r)})^{\text{rev}}$ and $\tilde{S}^{(r)} \stackrel{\text{def}}{=} (S^{(r)})^{\text{rev}}$.
## 1.2 Relation with the second-order Eulerian numbers

The second-order ($r = 2$) Stirling cycle and subset numbers are closely related to the second-order Eulerian numbers, as we now explain.

Let $w = w_1 \cdots w_N$ be a word on a totally ordered alphabet $\mathbb{A}$. A pair $(w_i, w_{i+1})$ with $i \in [N-1]$ is called an **ascent** (resp. **descent**, **plateau**) in case $w_i < w_{i+1}$ (resp. $w_i > w_{i+1}$, $w_i = w_{i+1}$).<fnref n="5" /> The word $w$ is said to be a **Stirling word** if, for every letter $a \in \mathbb{A}$, all letters between two successive occurrences of $a$ are larger than $a$. A permutation of a multiset $M$ is said to be a **Stirling permutation** if it is a Stirling word. The second-order Eulerian number $\langle\langle n \rangle\rangle$ is then defined to be the number of Stirling permutations of the multiset $\{1, 1, 2, 2, \dots, n, n\}$ with $k$ ascents (or $k$ descents: they are equidistributed, since reversing the word exchanges ascents with descents).<fnref n="6" /> They satisfy the recurrence [29, eq. (6.41)]

$$ \langle\langle\langle n \rangle\rangle\rangle = (2n - k - 1) \langle\langle\langle n - 1 \rangle\rangle\rangle + (k + 1) \langle\langle\langle n - 1 \rangle\rangle\rangle \quad (1.19) $$

with initial conditions $\langle\langle 0 \rangle\rangle = \delta_{k0}$ and $\langle\langle n \rangle\rangle = 0$.

Now define the **second-order Eulerian triangle** $E^{(2)} = (\langle\langle n \rangle\rangle)_{n,k\ge0}$ and the **shifted-reversed second-order Eulerian triangle** $\tilde{E}^{(2)} = (\langle\langle n \rangle\rangle)_{n,k\ge0}$ [with the modification for $n = 0$ to make the row $(1, 0, 0, \dots)$]. We will prove:

**Proposition 1.2** (Relation of second-order Stirling cycle and subset numbers with second-order Eulerian numbers). Let $B = (\begin{pmatrix} n \\ k \end{pmatrix})_{n,k\ge0}$ be the binomial matrix. Then:

$$ (a) \quad \tilde{C}^{(2)} = E^{(2)} B. $$

$$ (b) \quad \tilde{S}^{(2)} = \tilde{E}^{(2)} B. $$

Part (b) seems to have been known for a long time [40, eq. (6)] [4, eqns. (1a)/(31b)]; and part (a) is implicit in some formulas at [35, A106828/A358622]. We will give several proofs of these equalities: a simple algebraic proof based on the recurrences, which however is not very enlightening; and several (more illuminating) combinatorial proofs based on bijections to other combinatorial objects.

If one defines the **second-order Eulerian polynomials**

$$ E_n^{(2)}(x) \stackrel{\text{def}}{=} \sum_{k=0}^{n} \langle\langle\langle n \rangle\rangle\rangle x^k, \quad (1.20) $$

<footnote n="5">⁵Note that we do not allow $i = N$ as a position for an ascent, descent or plateau. Some authors do allow this, by fixing a “boundary condition” for $w_{N+1}$ (usually defining it to be either < every element of $\mathbb{A}$ or > every element of $\mathbb{A}$). It is important, when comparing formulae, to check carefully which convention the author is using.</footnote>

<footnote n="6">⁶Here we follow the definition of Graham-Knuth-Patashnik [29, p. 270], which entails that, when $n \ge 1$, $\langle\langle n \rangle\rangle$ is nonzero for $0 \le k \le n - 1$. Many other authors [19, 28, 32, 36] use the convention that the final index $N = 2n$ is always the beginning of a descent (e.g. by imposing the boundary condition $w_{N+1} = 0$), so that, when $n \ge 1$, $\langle\langle n \rangle\rangle$ is nonzero for $1 \le k \le n$.</footnote>
then the identities of Proposition 1.2 imply a relation with the second-order Stirling cycle and subset polynomials:

$$x^n c_{2,n}(1/x) = E_n^{(2)}(1+x) \qquad (1.21)$$

$$x^n s_{2,n}(1/x) = (1+x)^{n-1} E_n^{(2)}\left(\frac{1}{1+x}\right) \quad \text{for } n \ge 1 \qquad (1.22)$$

or equivalently<fnref n="7" />

$$c_{2,n}(x) = x^n E_n^{(2)}\left(\frac{1+x}{x}\right) \qquad (1.23)$$

$$s_{2,n}(x) = x(1+x)^{n-1} E_n^{(2)}\left(\frac{x}{1+x}\right) \quad \text{for } n \ge 1 \qquad (1.24)$$

Let us remark that one can define, more generally, the rth-order Eulerian numbers $\langle n \rangle^{(r)}$ as the number of Stirling permutations of the multiset $\{1^r, \dots, n^r\}$ with k ascents. They satisfy the recurrence

$$\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle^{(r)} = [rn - k - (r - 1)] \left\langle \begin{array}{c} n-1 \\ k-1 \end{array} \right\rangle^{(r)} + (k+1) \left\langle \begin{array}{c} n-1 \\ k \end{array} \right\rangle^{(r)}. \qquad (1.25)$$

We analogously define r-th order Eulerian triangle $E^{(r)} = (\langle n \rangle^{(r)})_{n,k \ge 0}$ and shifted-reversed r-th order Eulerian triangle $\tilde{E}^{(r)} = (\langle n \rangle^{(r)})_{n,k \ge 0}$ for $r \ge 1$.

However, as far as we know there is no relation between the rth-order Stirling cycle or subset numbers and the rth-order Eulerian numbers, for $r \ge 3$. Indeed, this lack of relation is to be expected, since the recurrence (1.25) is affine in n and k for all r, while the recurrences (1.13)/(1.14) are not affine in n or k when $r \ge 3$. Instead, the matrices which do seem to be analogous in this context for $r \ge 3$ are $\tilde{C}^{(r)} B^{-1}$ and $\tilde{S}^{(r)} B^{-1}$. We call their entries the **r**th-order **quasi-Eulerian numbers**. We will further look at these matrices in Sections 1.4 and 5: we will state some conjectures related to these numbers in Section 1.4, and we will provide a combinatorial interpretation for the entries of $\tilde{C}^{(r)} B^{-1}$ in Section 5.

## 1.3 Statement of main conjectures and results

Having defined the Stirling cycle and subset numbers of all orders r, we are now ready to state our conjectures, which constitute our first principal contribution in this paper. We will then state which cases are known and which cases we will prove in the present paper.

Our conjecture for the Stirling cycle numbers of all orders is the following:

**Conjecture 1.3** (Conjecture for Stirling cycle numbers of all orders). The following are true:

(a) The triangle $C^{(r)}$ is totally positive for all $r \ge 1$.

<footnote n="7">⁷The identity (1.24) can also be found in [23, eq. (1.15b)]: that paper used a different definition of the second-order Eulerian numbers, so that their $E_n^{[2]}(x)$ equals our $xE_n^{(2)}(x)$ for $n \ge 1$.</footnote>
(b) The triangle $\tilde{C}^{(r)} \stackrel{\text{def}}{=} (C^{(r)})^{\text{rev}}$ formed by reversing the rows of $C^{(r)}$ is totally positive for $r = 1, 2$ and is not totally positive when $r \ge 3$.

(c) The row-generating polynomials $c_{r,n}(x)$ are negative-real-rooted for $r = 1, 2$ and they have non-real complex zeros for $r \ge 3$ and $n \ge 3$. Also, the row sequences of the matrix $C^{(r)}$ are log-concave for $1 \le r \le 5$.

(d) The sequence $(c_{r,n}(x))_{n \ge 0}$ is coefficientwise Hankel-totally positive in the variable $x$ for all $r \ge 1$.

As mentioned earlier, the $r = 1$ cases of Conjecture 1.3 are all known to be true. In this paper we will prove (c) and (d) for $r = 2$.<fnref n="8" />

Our conjecture for the Stirling subset numbers of all orders is the following:

**Conjecture 1.4** (Conjecture for Stirling subset numbers of all orders). The following are true:

(a) The triangle $S^{(r)}$ is totally positive for all $r \ge 1$.

(b) The triangle $\tilde{S}^{(r)} \stackrel{\text{def}}{=} (S^{(r)})^{\text{rev}}$ formed by reversing the rows of $S^{(r)}$ is totally positive for $r = 1, 2$ and is not totally positive when $r \ge 3$.

(c) The row-generating polynomials $s_{r,n}(x)$ are negative-real-rooted for $r = 1, 2$ and they have non-real complex zeros for $r \ge 3$ and $n \ge 3$. Also, the row sequences of the matrix $S^{(r)}$ are log-concave for $1 \le r \le 5$.

(d) The sequence $(s_{r,n}(x))_{n \ge 0}$ is coefficientwise Hankel-totally positive in the variable $x$ for $r = 1, 2$ and is not coefficientwise Hankel-totally positive for $r \ge 3$.

As mentioned earlier, the $r = 1$ cases of Conjecture 1.4 are all known to be true. For $r = 2$, the sequence of polynomials $(s_{2,n}(x))_{n \ge 0}$ was studied by Elvey Price and Sokal [23], who called them the **Ward polynomials**: compare the recurrence (1.16) with [23, eq. (1.6)]. They showed [23, Theorem 1.1] that these polynomials have a Thron-type continued fraction (T-fraction) with coefficients $\alpha_n = nx$ and $\delta_n = n - 1$. It then follows from [38, Theorem 9.9] that this sequence of polynomials is coefficientwise Hankel-totally positive in the variable $x$. Therefore, part (d) of Conjecture 1.4 is known to be true for $r = 2$. In this paper, we will prove part (c) for the case $r = 2$.

Our main result on Hankel-total positivity is therefore the following:

**Theorem 1.5** (Hankel-total positivity of the second-order Stirling cycle polynomials). The sequence of second-order Stirling cycle polynomials $(c_{2,n}(x))_{n \ge 0}$ is coefficientwise Hankel-totally positive in the variable $x$.

<footnote n="8">⁸The log-concavity problems in (c) for $r = 3, 4, 5$ were proposed by the first author at the 30th British Combinatorial Conference: see [12] for the full list of problems.</footnote>
This theorem is, in fact, an immediate consequence of the coefficientwise Hankel-total positivity of the second-order Eulerian polynomials [38, Corollaries 12.35 and 12.36] together with the identity (1.23). So our main work will be to prove Proposition 1.2(a): we will provide an algebraic proof (Section 2) and a combinatorial proof (Section 3). For our combinatorial proof, we need a new combinatorial interpretation for the numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$, using Stirling permutations, due to David Callan [11]; we will do this in Section 3.2.

More specifically, [38, Corollary 12.35] showed that the second-order Eulerian polynomial $E_n^{(2)}(x)$ is equal to a specialization of the multivariate Eulerian polynomial $\mathcal{P}_n^{(2)}(x_0, x_1, x_2)$ introduced in [38, Chapter 12]: namely, $E_n^{(2)}(x) = \mathcal{P}_n^{(2)}(1, x, x)$. (We will recall the precise definitions in Section 3.3.) It then follows immediately from (1.23) that the second-order Stirling cycle polynomial $c_{2,n}(x)$ is also equal to a specialization of the multivariate Eulerian polynomial:

$$c_{2,n}(x) = \mathcal{P}_n^{(2)}(x, 1+x, 1+x). \qquad (1.26)$$

And from this, Theorem 1.5 follows immediately as a consequence of the coefficientwise Hankel-total positivity of the multivariate Eulerian polynomials [38, Corollary 12.3].

An analogous argument using Proposition 1.2(b) and (1.24), instead, provides an alternate proof of the coefficientwise Hankel-total positivity of the second-order Stirling subset polynomials $s_{2,n}(x)$, using 2-branched S-fractions instead of classical T-fractions. This was already observed in [23, Note Added, p. 12]. The important remark here is that (1.24) gives us a way to write the second-order Stirling subset polynomials $s_{2,n}(x)$ as a specialization of the multivariate Eulerian polynomials, namely,

$$s_{2,n}(x) = \mathcal{P}_n^{(2)}(x, x, 1+x). \qquad (1.27)$$

See the Remark at the end of Section 3.3.

Our second main contribution in this paper is to introduce, in Section 4, three further combinatorial interpretations for the numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$; thus, in this paper we provide a total of five combinatorial interpretations for the second-order Stirling cycle numbers. Even though these latter interpretations are not necessary for our proof of Theorem 1.5, and we are unable at present to see how to use them to prove any of our other main conjectures, we think that they are still interesting in their own right and provide interesting consequences; they also suggest new conjectures, as we will explain. We begin, in Section 4.1, by introducing our third combinatorial interpretation for the second-order Stirling cycle numbers, in terms of increasing ternary trees, using a well-known bijection to Stirling permutations. Then, in Section 4.2, we introduce our fourth interpretation in terms of certain families of weighted increasing trees with ordered children, and we provide two different proofs: one bijective and one using generating functions. Both proofs suggest new lines of investigation, and also show that the hypothesis in [37, Theorem 1.1(c)] due to Pétréolle and Sokal, though sufficient, is far from necessary. In Section 4.3 we introduce our fifth and final interpretation in terms of certain leaf-labeled trees. We then show the relation to the multivariate Ward polynomials introduced by Elvey Price and Sokal [23, pp. 9–11], and we show that these multivariate polynomials are a common generalization of both the second-order Stirling cycle polynomials $c_{2,n}(x)$ and the second-order Stirling subset polynomials $s_{2,n}(x)$. This observation leads us very naturally to another triangle
of numbers that also seems to satisfy our four positivity properties; we state this in Conjecture 4.17.

Our main results on real-rootedness are the following:

**Theorem 1.6 (Location of zeros for the second-order Stirling cycle and subset polynomials).** For each $n \ge 1$, the polynomials $c_{2,n}(x)$ and $s_{2,n}(x)$ have 0 as a root. The zeros of the polynomial sequence $(c_{2,n}(x)/x)_{n \ge 1}$, and also of the sequence $(s_{2,n}(x)/x)_{n \ge 1}$, are simple, interlacing, and lie in the interval $(-1, 0)$.

Thus, in Theorem 1.6 we prove not only that the zeros are non-positive, but that in fact they lie in a specific interval.

As mentioned previously, it is known [33, pp. 395, 399] that the Toeplitz-total positivity of the rows of a lower-triangular matrix is equivalent to the negative-real-rootedness of its row-generating polynomials. It therefore follows from Theorem 1.6 that the lower-triangular Toeplitz matrices $([\binom{n}{i-j}]^{(2)})_{i,j \ge 0}$ and $\{\binom{n}{i-j}^{(2)}\}_{i,j \ge 0}$ are totally positive for every $n \ge 0$. In particular, the positivity of the contiguous $2 \times 2$ minors of these Toeplitz matrices implies that the row sequences of the second-order Stirling cycle and subset matrices $C^{(2)}$ and $S^{(2)}$ are log-concave.

One can show that Theorem 1.6 follows very easily from a very general theorem due to Liu and Wang [34]. However, for the convenience of the reader we will provide a direct proof of this theorem in Section 6.

Even though the zeros of the polynomials $c_{r,n}(x)$ and $s_{r,n}(x)$ do not lie on the real line for $r \ge 3$, it might be worthwhile to try to understand how they are distributed in the complex plane. In Section 7, we will provide some plots for the distribution of zeros of the polynomials for orders $r \ge 3$. These plots will suggest that these zeros, when correctly normalised, seem to accumulate around some limiting curves. However, at this moment we are unable to provide any precise conjectures or proofs describing these limiting curves.

## 1.4 Higher-order Eulerian and quasi-Eulerian numbers: Statement of conjectures

A major longstanding open problem in the theory of total positivity is Brenti's conjecture on the total positivity of the triangle of Eulerian numbers [9]. Brenti's conjecture is in fact the first in a family of conjectures concerning the higher-order Eulerian numbers that arose in discussions between us and Alex Dyachenko [18]:

**Conjecture 1.7 (Conjecture for r-th order Eulerian numbers [18]).** For any $r \ge 1$, the following are true:

(a) The r-th order Eulerian triangle $E^{(r)} = (\binom{n}{k}^{(r)})_{n,k \ge 0}$ is totally positive.

(b) The shifted-reversed r-th order Eulerian triangle $\tilde{E}^{(r)} = (\binom{n}{n-k-1}^{(r)})_{n,k \ge 0}$ is totally positive.

We remark that (a) and (b) are equivalent for $r = 1$, by virtue of the symmetry $\binom{n}{k} = \binom{n}{n-k-1}$ for $n \ge 1$; but this is not the case for $r \ge 2$, where the two conjectures need to be considered separately. Conjecture 1.7 is unproven even for $r = 1$, where it is
Brenti's conjecture from 1996 [9]. Dyachenko [18] has verified Conjecture 1.7(a,b) for the leading 512 × 512 submatrix for $r = 1$, and for the leading 256 × 256 submatrix for $2 \le r \le 6$, by computing the bidagonal factorization using Neville elimination [27].

Conjecture 1.7 asks our questions (a) and (b) for the higher-order Eulerian triangles. Questions (c) and (d) for these triangles have already been answered in the affirmative: the negative-real-rootedness of the row-generating polynomials is due to Brenti [7, Theorem 6.6.3(i)], and their coefficientwise Hankel-total positivity was proven by Pétréolle, Sokal and Zhu [38, Corollaries 12.35 and 12.36] using branched continued fractions.

However, as mentioned previously, as far as we know there is no relation between the $r$th-order Stirling cycle or subset numbers and the $r$th-order Eulerian triangles $E^{(r)}$ for $r \ge 3$. Rather, Proposition 1.2 suggests that the matrices that are analogous in this context for $r \ge 3$ are $\tilde{C}^{(r)} B^{-1}$ and $\tilde{S}^{(r)} B^{-1}$. We call these matrices the **$r$th-order quasi-Eulerian cycle triangle** and the **$r$th-order quasi-Eulerian subset triangle**, respectively, and we denote them as

$$Q_C^{(r)} \stackrel{\text{def}}{=} \tilde{C}^{(r)} B^{-1}, \quad Q_S^{(r)} \stackrel{\text{def}}{=} \tilde{S}^{(r)} B^{-1}. \qquad (1.28)$$

We call their entries the **$r$th-order quasi-Eulerian cycle numbers** and the **$r$th-order quasi-Eulerian subset numbers**, respectively:

$$\left\langle\left\langle\left\langle\left\langle n \right\rangle\right\rangle\right\rangle\right\rangle_C^{(r)} \stackrel{\text{def}}{=} (Q_C^{(r)})_{n,k}, \quad \left\langle\left\langle\left\langle\left\langle n \right\rangle\right\rangle\right\rangle\right\rangle_S^{(r)} \stackrel{\text{def}}{=} (Q_S^{(r)})_{n,k}. \qquad (1.29)$$

Thus, when $r = 2$, we have from Proposition 1.2

$$Q_C^{(2)} = E^{(2)}, \quad Q_S^{(2)} = \tilde{E}^{(2)}, \qquad (1.30)$$

so that the two matrices are reversals of each other. But for $r \ne 2$ this is not the case, and the four matrices $Q_C^{(r)}$, $Q_S^{(r)}$, $(Q_C^{(r)})^{\text{rev}}$, $(Q_S^{(r)})^{\text{rev}}$ need to be considered separately.

In Appendices B.1 and B.2, we provide tables of the triangles $Q_C^{(r)}$ and $Q_S^{(r)}$, respectively, for $1 \le r \le 5$ and the first few values of $n$. When $r = 1$, the matrices $Q_C^{(1)}$ and $Q_S^{(1)}$ are not even entrywise positive: some of their entries are negative integers. We therefore restrict our discussion henceforth to $r \ge 2$.

For all $r \ge 2$, we will provide a combinatorial interpretation for the $r$th-order quasi-Eulerian cycle numbers in Section 5 (Proposition 5.2). We leave it as an open problem to construct a combinatorial interpretation for the $r$th-order quasi-Eulerian subset numbers.

For $r = 2$, Conjecture 1.7 asserts that the foregoing four triangles are totally positive. For $r \ge 3$, the triangles $Q_C^{(r)}$ and $Q_S^{(r)}$ are not totally positive: this is an immediate consequence of the definition (1.28) together with the failure of total positivity for the triangles $\tilde{C}^{(r)}$ and $\tilde{S}^{(r)}$ that was noted in Conjectures 1.3(b) and 1.4(b) [see Appendix C]. This fact makes the following conjecture somewhat more surprising:

**Conjecture 1.8** (Conjectures for the reversed higher-order quasi-Eulerian triangles).

(b) The matrix $(Q_C^{(r)})^{\text{rev}}$ is totally positive for all $r \ge 2$.

(b') The matrix $(Q_S^{(r)})^{\text{rev}}$ is totally positive for all $r \ge 2$.

We verified the total positivity of these matrices for $3 \le r \le 10$ for the leading 50 × 50 submatrix.
Next, for $r \ge 2$ we define the $r^{th}$-order quasi-Eulerian cycle polynomials and the $r^{th}$-order quasi-Eulerian subset polynomials to be the generating polynomials

$$Q_{C,n}^{(r)}(x) \stackrel{\text{def}}{=} \sum_{k=0}^{n} \left\langle\left\langle\left\langle n \right\rangle\right\rangle_{C}^{(r)}\right\rangle_{C} x^{k}, \qquad (1.31)$$

$$Q_{S,n}^{(r)}(x) \stackrel{\text{def}}{=} \sum_{k=0}^{n} \left\langle\left\langle\left\langle n \right\rangle\right\rangle_{S}^{(r)}\right\rangle_{S} x^{k}, \qquad (1.32)$$

respectively. Then by definition, we have

$$x^n c_{r,n}(1/x) = Q_{C,n}^{(r)}(1+x), \quad x^n s_{r,n}(1/x) = Q_{S,n}^{(r)}(1+x), \qquad (1.33)$$

which are (1.21) and (1.22), respectively, when $r = 2$.

For $r \ge 3$, these polynomials are not real-rooted: that follows from (1.33) together with the non-real-rootedness of the polynomials $c_{r,n}(x)$ and $s_{r,n}(x)$ that was noted in Conjectures 1.3(c) and 1.4(c) [see Proposition 7.1 and Corollaries 7.2 and 7.3 and the subsequent remarks].

Likewise, it follows from (1.33) and the failure of coefficientwise Hankel-total positivity for $s_{r,n}(x)$ that was noted in Conjecture 1.4(d) that the polynomials $Q_{S,n}^{(r)}(x)$ are not coefficientwise Hankel-totally positive. On the other hand, we do conjecture coefficientwise Hankel-total positivity for the quasi-Eulerian cycle polynomials:

**Conjecture 1.9** (Conjectured Hankel-total positivity of the quasi-Eulerian cycle polynomials). For all $r \ge 3$, the sequence $(Q_{C,n}^{(r)}(x))_{n \ge 0}$ of the $r$th-order quasi-Eulerian cycle polynomials is coefficientwise Hankel-totally positive in the variable $x$.

From (1.33) we see that Conjecture 1.9 strengthens Conjecture 1.3(d). We have tested Conjecture 1.9 up to the $9 \times 9$ Hankel matrix for $3 \le r \le 10$.

## 1.5 Structure of this paper

The plan of this paper is as follows: In Section 2 we give an algebraic proof of Proposition 1.2. In Section 3, we prove the coefficientwise Hankel-total positivity of the second-order Stirling cycle polynomials (Theorem 1.5), based on two combinatorial interprerations of the second-order Stirling cycle numbers. Then, in Section 4, we give our third, fourth and fifth combinatorial interpretations for the second-order Stirling cycle numbers; these lead to some interesting observations and another conjecture. Next, in Section 5, we generalize our second interpretation for the second-order Stirling cycle numbers to higher orders; this gives a second combinatorial interpretation for the $r$th-order Stirling cycle numbers, and also for the $r$th-order quasi-Eulerian cycle numbers, for all $r \ge 2$. After this, in Section 6, we prove Theorem 1.6 on the negative-real-rootedness of the second-order Stirling cycle and subset polynomials. Finally, in Section 7 we provide some plots for the zeros of $r$-th order Stirling cycle and subset polynomials for orders $r \in [3, 10]$.

In Appendix A, we provide tables of the $r$th-order Stirling cycle and subset numbers for $1 \le r \le 4$ and the first few values of $n$; and in Appendix B, we provide tables of the $r$th-order quasi-Eulerian cycle and subset numbers for $2 \le r \le 4$ and
the first few values of $n$. Then in Appendix C, we provide a report on the systematic verification of our conjectures and mention up to which order we have checked our conjectures.

## 2 Algebraic proof of Proposition 1.2

In this section we will prove Proposition 1.2 by using a result from [39] concerning lower-triangular arrays that satisfy a Graham-Knuth-Patashnik (GKP) recurrence.

**Lemma 2.1.** [39, Corollary A.15] Let $A = (A(n, k))_{n,k \ge 0}$ be a lower-triangular array defined by the GKP recurrence

$$A(n, k) = (\alpha n + \beta k + \gamma) A(n-1, k) + (\alpha' n + \beta' k + \gamma') A(n-1, k-1) \quad (2.1)$$

for $n \ge 1$, with initial conditions $A(0, k) = \delta_{k0}$ and $A(n, -1) = 0$. Let $B_{\xi}$ be the weighted binomial matrix with entries

$$(B_{\xi})(n, k) = \binom{n}{k} \xi^{n-k}. \qquad (2.2)$$

Then the matrix product $C = AB_{\xi}$ satisfies the recurrence

$$C(n,k) = [(\alpha + \xi\alpha')n + (\beta + 2\xi\beta')k + \gamma + \xi(\beta' + \gamma')] C(n-1,k) \\ + (\alpha'n + \beta'k + \gamma') C(n-1,k-1) \\ + \xi(\beta + \xi\beta')(k+1) C(n-1,k+1) \qquad (2.3)$$

for $n \ge 1$, with initial conditions $C(0, k) = \delta_{k0}$ and $C(n, -1) = 0$.

In particular, if $\xi = -\beta/\beta'$ we again obtain a recurrence of GKP form.

**PROOF OF PROPOSITION 1.2.** (a) The recurrence (1.19) for the second-order Eulerian numbers is of GKP form with $(\alpha, \beta, \gamma, \alpha', \beta', \gamma') = (0, 1, 1, 2, -1, -1)$. Applying Lemma 2.1 with $\xi = 1$, we deduce that $C = E^{(2)} B_1$ satisfies the GKP recurrence

$$C(n,k) = (2n - k - 1) C(n - 1, k) + (2n - k - 1) C(n - 1, k - 1). \quad (2.4)$$

This is exactly what is obtained from the recurrence (1.15) for the second-order Stirling cycle numbers by replacing $k \to n-k$.

(b) Making the substitution $k \to n-k-1$ in (1.19), we see that the shifted-reversed second-order Eulerian triangle $\tilde{E}^{(2)}$ satisfies a GKP recurrence with $(\alpha, \beta, \gamma, \alpha', \beta', \gamma') = (1, 1, 0, 1, -1, 0)$. Applying Lemma 2.1 with $\xi = 1$, we deduce that $C = \tilde{E}^{(2)} B_1$ satisfies the GKP recurrence

$$C(n,k) = (2n - k - 1) C(n - 1, k) + (n - k) C(n - 1, k - 1). \quad (2.5)$$

This is exactly what is obtained from the recurrence (1.16) for the second-order Stirling subset numbers by replacing $k \to n-k$. $\square$

This proof is straightforward (once one has in hand Lemma 2.1), but it is not terribly illuminating. Much of the rest of this paper is therefore devoted to providing combinatorial interpretations of the second-order Stirling cycle numbers that make the identity of Proposition 1.2(a) transparent.
### 3 Combinatorial proof of Proposition 1.2(a)

In this section we will provide a combinatorial proof of Proposition 1.2(a). We begin by recalling the combinatorial definition of the numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$ (Section 3.1). We then proceed in Section 3.2 to establish our second combinatorial interpretation of $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$: it counts Stirling permutations of the multiset $\{1, 1, 2, 2, \dots, n, n\}$ with optional dots at ascents and containing $n-k$ dots. Finally, in Section 3.3, this interpretation will immediately imply Proposition 1.2(a) as a natural consequence; we obtain Theorem 1.5 as a corollary.

#### 3.1 Interpretation I: Derangements

Let us recall that $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)} = \begin{bmatrix} n+k \\ k \end{bmatrix}_2$ is defined to be the number of permutations of $[n+k]$ containing $k$ cycles, all of which are of size $\ge 2$. In other words, it is the number of derangements of $[n+k]$ containing $k$ cycles. We write $\mathcal{D}_{N,k}$ for the set of derangements of $[N]$ with $k$ cycles. Therefore, $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)} = |\mathcal{D}_{n+k,k}|$. These numbers satisfy the recurrence (1.15).

#### 3.2 Interpretation II: Stirling permutations

We will now provide a second interpretation for the numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$: they count Stirling permutations with optional dots in ascents. This interpretation can be guessed from the entries in [35, A032188], and the proof that follows is due to David Callan [11].

Let us recall that a **Stirling permutation of size $n$** is a permutation of the multiset $\{1, 1, 2, 2, \dots, n, n\}$ with the *Stirling property*: for every $i \in [n]$, all entries between the two occurrences of $i$ exceed $i$. Equivalently, a Stirling permutation of size $n$ is permutation of the multiset $\{1, 1, 2, 2, \dots, n, n\}$ that avoids the pattern 212. We recall [28] that there are $(2n-1)!!$ Stirling permutations of size $n$. An **ascent-marked Stirling permutation of size $n$** is now defined to be a Stirling permutation in which a dot may or may not be inserted in each ascent (we recall that an ascent is a pair $a_i, a_{i+1}$ such that $a_i < a_{i+1}$; the dot, if any, is inserted between $a_i$ and $a_{i+1}$). Let $\mathcal{V}_n$ denote the set of ascent-marked Stirling permutations of size $n$; and let $\mathcal{V}_{n,k}$ denote the set of ascent-marked Stirling permutations of size $n$ with $k$ dots. Thus,

$$ \mathcal{V}_{2,0} = \{1122, 1221, 2211\} \qquad (3.1a) $$

$$ \mathcal{V}_{2,1} = \{11 \cdot 22, 1 \cdot 221\}. \qquad (3.1b) $$

Let $v_{n,k} = |\mathcal{V}_{n,k}|$. We will prove:

**Lemma 3.1.** The numbers $v_{n,k}$ satisfy the recurrence

$$ v_{n,k} = (2n - k - 1) (v_{n-1,k} + v_{n-1,k-1}) \qquad (3.2) $$

with initial conditions $v_{0,k} = \delta_{k0}$ and $v_{n,-1} = 0$. Therefore $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)} = v_{n,n-k}$.

**PROOF** [11]. Let $\sigma \in \mathcal{V}_{n,k}$ be an ascent-marked Stirling permutation of size $n$ with $k$ dots. Deleting the two $n$'s (which are necessarily adjacent) together with the dot
(if any) preceding them gives an element of $\mathcal{V}_{n-1,k}$ if there was no dot before $nn$, and an element of $\mathcal{V}_{n-1,k-1}$ if there was a dot before $nn$.

Conversely, to get an element $\sigma \in \mathcal{V}_{n,k}$ with $nn$ not preceded by a dot from a one-size-smaller ascent-marked Stirling permutation, $nn$ can be inserted into an element of $\mathcal{V}_{n-1,k}$ in any of the $2n-1$ spaces except those occupied by a dot; thus, there are $2n-1-k$ choices. To get a $\sigma \in \mathcal{V}_{n,k}$ with $nn$ preceded by a dot, $\cdot nn$ can be inserted into an element of $\mathcal{V}_{n-1,k-1}$ in any of the $2n-1$ spaces except the first space and those occupied by a dot; again the number of choices is $2n-1-k$. This proves the recurrence (3.2).

From (3.2) it follows that the numbers $u_{n,k} = v_{n,n-k}$ satisfy the recurrence

$$u_{n,k} = (n + k - 1)(u_{n-1,k-1} + u_{n-1,k}), \qquad (3.3)$$

which is the same as the recurrence (1.15) satisfied by the numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$. Since these numbers also satisfy the same initial conditions, we conclude that $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)} = u_{n,k}$. $\square$

## 3.3 Proof of Proposition 1.2(a) and Theorem 1.5

We are now ready to prove Proposition 1.2(a).

**PROOF OF PROPOSITION 1.2(A).** To prove Proposition 1.2(a), we need to show for every $n, k \ge 0$ that

$$\begin{bmatrix} n \\ n-k \end{bmatrix}^{(2)} = \sum_{i=k}^{n} \left\langle\left\langle \begin{matrix} n \\ i \end{matrix} \right\rangle\right\rangle \begin{pmatrix} i \\ k \end{pmatrix} \qquad (3.4)$$

Using Lemma 3.1, we know that the left-hand side is the number of ascent-marked Stirling permutations of size $n$ with $k$ dots. This is clearly equal to the right-hand side because we can pick such an ascent-marked Stirling permutation by first picking a Stirling permutation of size $n$ with $i$ ascents (counted by $\left\langle\left\langle \begin{matrix} n \\ i \end{matrix} \right\rangle\right\rangle$) and then insert dots in $k$ of the $i$ ascents (counted by $\begin{pmatrix} i \\ k \end{pmatrix}$). $\square$

Theorem 1.5 will now be an immediate consequence, but we first recall some definitions and results from [38, Chapter 12]. For a fixed integer $m \ge 1$ and indeterminates $\mathbf{x} = (x_0, x_1, \dots, x_m)$, we let $Q_n^{(m)}(\mathbf{x})$ be the generating polynomial for increasing $(m+1)$-ary trees on the vertex set $[n] \cup \{0\}$ in which each $i$-edge gets a weight $x_i$. They are homogeneous polynomials of degree $n$, and symmetric under permutations of $x_0, \dots, x_m$. We then define $P_n^{(m)}(\mathbf{x})$ by

$$P_0^{(m)}(\mathbf{x}) = 1 \qquad (3.5a)$$

$$P_n^{(m)}(\mathbf{x}) = x_0 Q_{n-1}^{(m)}(\mathbf{x}) \quad \text{for } n \ge 1 \qquad (3.5b)$$

Therefore, $P_n^{(m)}(\mathbf{x})$ is the generating polynomial for increasing $(m+1)$-ary trees on the vertex set $[n] \cup \{0\}$ such that the only edge (if any) emanating from the root 0 is a 0-edge and in which each $i$-edge gets a weight $x_i$. These polynomials were called the multivariate Eulerian polynomials in [38]. They are homogeneous polynomials of degree $n$, and symmetric under permutations of $x_1, \dots, x_m$; but $x_0$ plays a special role.
In [38, Theorem 9.8], Pétréolle, Sokal and Zhu showed that the sequence of m-Stieltjes-Rogers polynomials $S_n^{(m)}(\alpha)$ (see [38, Definition 2.2] for the definition) is coefficientwise Hankel-totally positive in the indeterminates $\alpha = (\alpha_i)_{i \ge m}$. Then in [38, eq. (12.5) and Theorem 12.1(a)] they proved that the multivariate Eulerian polynomials $\mathcal{P}_n^{(m)}(\mathbf{x})$ can be obtained as a specialization of the m-Stieltjes-Rogers polynomials:

$$ \alpha_{m+j+(m+1)k} = (k+1)x_j. \qquad (3.6) $$

Since these coefficients $\alpha_i$ are polynomials (in fact monomials) with nonnegative coefficients in the indeterminates $\mathbf{x}$, it follows that the sequence $(\mathcal{P}_n^{(m)}(\mathbf{x}))_{n \ge 0}$ is coefficientwise Hankel-totally positive in the indeterminates $\mathbf{x}$. We can summarise these results as follows:

**Theorem 3.2** ([38, eq. (12.5) and Theorems 12.1(a) and 9.8]). The polynomials $\mathcal{P}_n^{(m)}(\mathbf{x})$ are equal to the m-Stieltjes-Rogers polynomials $S_n^{(m)}(\alpha)$ where the weights $\alpha = (\alpha_i)_{i \ge m}$ are given by

$$ \alpha_{m+j+(m+1)k} = (k+1)x_j. \qquad (3.7) $$

Thus, the sequence of polynomials $(\mathcal{P}_n^{(m)}(\mathbf{x}))_{n \ge 0}$ is coefficientwise Hankel-totally positive with respect to the variables $x_0, x_1, \dots, x_m$.

**PROOF OF THEOREM 1.5.** The second-order Eulerian polynomial $E_n^{(2)}(x)$ is equal to a specialization of the multivariate Eulerian polynomial: namely, $E_n^{(2)}(x) = \mathcal{P}_n^{(2)}(1, x, x)$. As the polynomials $\mathcal{P}_n^{(2)}$ are homogeneous in all three variables, equation (1.23), which is a consequence of Proposition 1.2(a), gives us equation (1.26). The theorem then follows from Theorem 3.2. $\square$

**Remark.** We can now prove the analogous equation (1.27) for the second-order Stirling subset polynomials. Using (1.24) together with $E_n^{(2)}(x) = \mathcal{P}_n^{(2)}(1, x, x)$ and the homogeneity and symmetry of the multivariate Eulerian polynomials, we have for $n \ge 1$

$$ s_{2,n}(x) = x(1+x)^{n-1} E_n^{(2)}\left(\frac{x}{1+x}\right) \qquad (3.8a) $$

$$ = \frac{x}{1+x} \mathcal{P}_n^{(2)}(1+x, x, x) \qquad (3.8b) $$

$$ = x \mathcal{Q}_{n-1}^{(2)}(1+x, x, x) \qquad (3.8c) $$

$$ = x \mathcal{Q}_{n-1}^{(2)}(x, x, 1+x) \qquad (3.8d) $$

$$ = \mathcal{P}_n^{(2)}(x, x, 1+x) . \qquad (3.8e) $$

And of course for $n = 0$ we have $s_{2,0}(x) = \mathcal{P}_0^{(2)}(x, x, 1+x) = 1$. $\blacksquare$
# 4 Second-order Stirling cycle numbers: Three further combinatorial interpretations

In this section we will provide three more combinatorial interpretations for the second-order Stirling cycle numbers. In Section 4.1 we provide an interpretation using increasing ternary trees. In Section 4.2 we introduce an interpretation involving increasing trees with ordered children. In Section 4.3 we introduce an interpretation involving a class of leaf-labeled trees with cyclically-ordered children.

## 4.1 Interpretation III: Increasing ternary trees

We begin by recalling [44, p. 573] the recursive definition of an *m-ary tree* ($1 \le m < \infty$): it is either empty or else consists of a root together with an ordered list of *m* subtrees ($T_0, \dots, T_{m-1}$), each of which is an *m-ary tree* (which may be empty). We draw an edge from each vertex to the root of each of its nonempty subtrees; an edge from a vertex to the root of its *i*-th subtree ($0 \le i \le m-1$) will be called an *i-edge*. When $m=2$, we refer to a *binary tree* and to its *left* and *right* edges. When $m=3$, we refer to a *ternary tree* and to its *left*, *middle* and *right* edges.

A rooted tree on a totally ordered vertex set is called *increasing* if each vertex is higher-numbered than its parent; equivalently, the labels increase along each path downward from the root. It is well known [44, p. 45, Proposition 1.5.3(a)] that the number of increasing binary trees on the vertex set $[n]$ is $n!$, and more generally that the number of increasing *m*-ary trees on the vertex set $[n]$ is the multifactorial $F_n^{(m-1)}$ [5, p. 30, Example 1], where $F_n^{(r)} \stackrel{\text{def}}{=} \prod_{j=0}^{n-1} (1+jr)$. In particular, the number of increasing ternary trees on the vertex set $[n]$ is $(2n-1)!!$.

We write $\mathcal{T}_n$ for the set of increasing ternary trees on the vertex set $[n]$. (In particular, $\mathcal{T}_0$ has a single element, namely the empty tree.) For $n \ge 1$, we write $\mathcal{T}_{n,k}$ for the set of increasing ternary trees on the vertex set $[n]$ with $k$ left edges.

In what follows we shall also use a variant: We write $\mathcal{T}'_n$ for the set of increasing ternary trees on the vertex set $[n] \cup \{0\}$ for which the only edge (if any) emanating from the root 0 is a left edge. (Thus, $\mathcal{T}'_0$ has a single element, namely the tree with only the root vertex 0; and in all trees $T \in \mathcal{T}'_n$ with $n \ge 1$, the root vertex 0 has a left child 1 and no other children.) We write $\mathcal{T}'_{n,k}$ for the set of increasing ternary trees $T \in \mathcal{T}'_n$ that have $k$ left edges.

For $n \ge 1$, there is an obvious bijection between $\mathcal{T}_n$ and $\mathcal{T}'_n$, which also maps $\mathcal{T}_{n,k}$ to $\mathcal{T}'_{n,k+1}$: namely, given $T \in \mathcal{T}_n$ we define $T' \in \mathcal{T}'_n$ by introducing a new root vertex 0 and making $T$ its left subtree; and given $T' \in \mathcal{T}'_n$, we define $T \in \mathcal{T}_n$ by deleting the root vertex 0 and making the vertex 1 the new root. For $n=0$, we augment this bijection by sending the empty tree $T \in \mathcal{T}_{0,0}$ to the tree $T' \in \mathcal{T}_{0,0}$ that has only the root vertex 0.

Since Stirling permutations of size $n$ and the set of increasing ternary trees $\mathcal{T}_n$ both have cardinality $(2n-1)!!$, there clearly must exist a bijection between these two sets. Indeed, such a bijection is well known [32, 36].<fnref n="9" /> We recall this construction,

<footnote n="9">⁹This bijection was first mentioned by Park in [36], who attributed it to Gessel. The details of this bijection were first explicitly stated by Janson, Kuba and Panholzer in [32].</footnote>
and the properties that we will need, in the following lemma:

**Lemma 4.1.** There is a bijection $\sigma \mapsto T(\sigma)$ where $\sigma$ is a Stirling permutations of size $n$ and $T(\sigma) \in \mathcal{T}_n$ is an increasing ternary tree on the vertex set $[n]$. This bijection has the property that, for each letter $a \in [n]$, the first (resp. second) occurrence of the letter $a$ in $\sigma$ is the beginning of an ascent (i.e. $a = a_i < a_{i+1}$) if and only if the vertex $a$ in $T(\sigma)$ has a middle (resp. right) child.

**PROOF.** We begin by recalling the bijection $\sigma \mapsto T(\sigma)$, following [32]. Let $\sigma = a_1 \cdots a_{2n}$ be any word on the alphabet $\mathbb{Z}_{\ge 1}$ such that

(a) each letter, if it occurs in $\sigma$, occurs exactly twice; and

(b) $\sigma$ has the Stirling property, i.e. all entries in $\sigma$ between the two occurrences of $a$ exceed $a$.

We then recursively define a ternary tree $T(\sigma)$ as follows:

• $T(\sigma)$ is the empty tree if and only if $\sigma$ is the empty word.

• Otherwise, let $a$ be the smallest letter of $\sigma$ and let $\sigma = \sigma_0 a \sigma_1 a \sigma_2$. Then $T(\sigma)$ is the ternary tree rooted at $a$ with $T(\sigma_0)$, $T(\sigma_1)$ and $T(\sigma_2)$ as the left, middle and right subtrees of $a$, respectively.

It is easy to see that $\sigma \mapsto T(\sigma)$ is a bijection from Stirling permutations of size $n$ to the set $\mathcal{T}_n$ of increasing ternary trees on $[n]$.

From the description of this bijection, it is clear that the first occurrence of the letter $a$ in $\sigma$ is the first element of an ascent pair (i.e. $a = a_i < a_{i+1}$) if and only if $\sigma_1$ is not the empty word, which is true if and only if the vertex labeled $a$ has a middle child in the ternary tree $T(\sigma)$. Similarly, the second $a$ in $\sigma$ is the first element of an ascent pair if and only if $\sigma_2$ is not the empty word, which is true if and only if the vertex labeled $a$ has a right child in the ternary tree $T(\sigma)$. $\square$

Thus, the ascents in $\sigma$ are in correspondence with the middle and right edges of $T(\sigma)$.

Now define an **edge-marked increasing ternary tree** to be an increasing ternary tree in which each middle or right edge may be marked or unmarked. (Left edges are always unmarked.) Lemma 4.1 immediately implies:

**Corollary 4.2.** There is a bijection $\tau \mapsto T(\tau)$ where $\tau \in \mathcal{V}_n$ is an ascent-marked Stirling permutation of size $n$ and $T(\tau)$ is an edge-marked increasing ternary tree on the vertex set $[n]$, such that, for each letter $a \in [n]$, the first (resp. second) occurrence of the letter $a$ in $\tau$ is followed by a dot if and only if the vertex $a$ in $T(\tau)$ has a middle (resp. right) child connected by a marked edge.

Putting together Lemma 3.1 and Corollary 4.2, we conclude:

**Proposition 4.3.** The number of edge-marked increasing ternary trees on the vertex set $[n]$ with $n-k$ marked edges (hence $k-1$ unmarked edges) is the second-order Stirling cycle number $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$.
Now we use the bijection $\mathcal{T}_n \mapsto \mathcal{T}'_n$ and to write out a different version of Proposition 4.3. First, we let $\hat{\mathcal{T}}_n$ denote the trees $T \in \mathcal{T}'_n$ along with optional edge markings in which each middle or right edge may be marked or unmarked. (Left edges are always unmarked.) Let $\hat{\mathcal{T}}_{n,k} \subseteq \hat{\mathcal{T}}_n$ denote the subset of these trees on the vertex set $[n] \cup \{0\}$ which have $k$ unmarked edges. We then have the following rewriting of Proposition 4.3:

**Proposition 4.4.** *The number of edge-marked increasing ternary trees on the vertex set $[n] \cup \{0\}$ with $k$ marked edges — that is, $|\hat{\mathcal{T}}_{n,k}|$ — is the second-order Stirling cycle number $[n]^{(2)}$.*

## 4.2 Interpretation IV: Increasing ordered trees

An *ordered tree* is a rooted tree in which the children of each vertex are linearly ordered. An *increasing ordered tree* is an ordered tree on a totally ordered vertex set (usually some set of integers) such that each vertex is higher-numbered than its parent; equivalently, the labels increase along each path downward from the root. It is well known [5, Corollary 1(iv)] [31] that the number of increasing ordered trees on $n+1$ vertices is $(2n-1)!!$.

A vertex in a rooted tree is called a **leaf** if it has no children; it is called an **internal vertex** (or a **non-leaf**) if it has at least one child.

Recall that $\mathcal{T}'_n$ denotes the set of increasing ternary trees on the vertex set $[n] \cup \{0\}$ such that the only edge (if any) emanating from the root 0 is a left edge; and $\mathcal{T}'_{n,k}$ denotes the set of trees in $\mathcal{T}'_n$ with $k$ left edges. Now let $\mathcal{I}_n$ denote the set of increasing ordered trees on the vertex set $[n] \cup \{0\}$, and let $\mathcal{I}_{n,k}$ denote the set of trees in $\mathcal{I}_n$ with $k$ internal vertices.<fnref n="10" /> We have already seen that $|\mathcal{T}'_n| = |\mathcal{I}_n| = (2n-1)!!$. We will refine this equality as follows:

**Proposition 4.5.** *The numbers $|\mathcal{I}_{n,k}|$ are given by*

$$ |\mathcal{I}_{n,k}| = |\mathcal{T}'_{n,k}| = \left\langle\left\langle\begin{array}{c} n \\ n-k \end{array}\right\rangle\right\rangle. \qquad (4.1) $$

The second equality is a direct consequence of Lemma 4.1. For the first equality, we will give two proofs: a bijective proof in Section 4.2.1, and a proof using generating functions in Section 4.2.2. Having established Proposition 4.5, we will finally be able to introduce *vertex-marked increasing ordered trees* in Section 4.2.3, which will be our fourth combinatorial interpretation for the numbers $[n]^{(2)}$.

### 4.2.1 Bijective proof of Proposition 4.5

For $n=0$ the claim of Proposition 4.5 is trivial, since $\mathcal{T}'_0 = \mathcal{T}'_{0,0} = \mathcal{I}_0 = \mathcal{I}_{0,0}$ has a unique element, namely the tree consisting only of the root vertex 0. So from now on we fix $n \ge 1$.

We will prove Proposition 4.5 by constructing a bijection $\Phi_n: \mathcal{T}'_n \to \mathcal{I}_n$ that maps $\mathcal{T}'_{n,k}$ onto $\mathcal{I}_{n,k}$. We will first construct the map $\Phi_n: \mathcal{T}'_n \to \mathcal{I}_n$; we will then construct

<footnote n="10">¹⁰Note that when $n=0$, the unique element of $\mathcal{I}_0$, namely the tree with only the root vertex 0, belongs to $\mathcal{I}_{0,0}$, because in this case the root is a leaf.</footnote>
another map $\Psi_n : \mathcal{I}_n \to \mathcal{T}'_n$; finally, we will show that the maps $\Phi_n$ and $\Psi_n$ are inverses of each other. Before doing all this, we first introduce some terminology concerning trees $T \in \mathcal{T}'_n$ and $S \in \mathcal{I}_n$.

Let $T \in \mathcal{T}'_n$ and let $j \in [n] \cup \{0\}$ be a vertex of $T$. Consider the subtree of $T$ rooted at the vertex $j$ that uses all the middle and right edges but no left edge. We call this tree the **middle-right subtree of j in T**.

Now let $i$ be a vertex of $T$. If $i$ has a left child $j$, we define $\textbf{left}_T(i)$ to be the middle-right subtree of $j$ in $T$; if $i$ has no left child, we define $\textbf{left}_T(i)$ to be the empty tree. For example, in Figure 1(a), the tree $\textbf{left}_T(1)$ is the subtree consisting of the vertex 3, the tree $\textbf{left}_T(2)$ is the subtree induced by the vertices 4, 8 and 9, and the tree $\textbf{left}_T(4)$ is the empty tree.

Now let $j$ be any vertex of $T$ other than the root, and consider the unique path in $T$ from $j$ to the root 0. Clearly this path must contain at least one left edge, since the root has only a left edge. Let $\text{lanc}(j)$ be the first vertex on this path that is reached via a left edge; we refer to $\text{lanc}(j)$ as the **left ancestor** of $j$. Since the tree $T$ is increasing, we have $0 \le \text{lanc}(j) < j$. For example, in Figure 1(a), $\text{lanc}(1) = 0$, $\text{lanc}(2) = 0$ and $\text{lanc}(3) = 1$.

The following lemma is a direct consequence of the definitions of $\text{left}_T(i)$ and $\text{lanc}(j)$ and we state it without proof:

**Lemma 4.6.** Let $T \in \mathcal{T}'_n$ and let $j$ be a vertex of $T$ different from the root 0. Then $j$ is a vertex of $\text{left}_T(\text{lanc}(j))$ and for every $i \ne \text{lanc}(j)$, $j$ is not a vertex of $\text{left}_T(i)$.

Next, let $S \in \mathcal{I}_n$ and let $i \in [n] \cup \{0\}$ be a vertex of $S$. Then we define the **child word of i**, denoted by $\text{ch}_S(i)$, to be the word whose $j$-th letter is the $j$-th child of $i$. Thus, $\text{ch}_S(i)$ is the empty word when $i$ is a leaf. For example, in Figure 1(b), we have $\text{ch}_S(1) = 3$, $\text{ch}_S(2) = 849$, and $\text{ch}_S(4) = \emptyset$.

We need one more ingredient before describing the map $\Phi_n$. This is the well-known correspondence between increasing binary trees on a totally-ordered finite vertex set $A$, and words $w$ on the alphabet $A$ with no repeated letters: see e.g. [44, pp. 44–45]. However, in our version, instead of using binary trees with left and right edges, we will use ternary trees with middle and right edges but no left edges; the two formulations are of course isomorphic. The correspondence therefore goes as follows:

If the word $w = \emptyset$, then $\text{Tree}(w) = \emptyset$. Otherwise, write $w = u \cdot i \cdot v$ where $i$ is the smallest letter of $w$; we then recursively define $\text{Tree}(w)$ to be the ternary tree with root $i$ whose middle subtree is $\text{Tree}(u)$ and right subtree is $\text{Tree}(v)$.

On the other hand, given an increasing ternary tree $T$ on the vertex set $A$ made up solely of middle and right edges, we define $\text{Word}(T)$ as follows: If $T = \emptyset$, then $\text{Word}(T) = \emptyset$. Otherwise, if $T$ has root $i$ with middle subtree $T'$ and right subtree $T''$ (either or both of which may be empty), we define $\text{Word}(T) = \text{Word}(T') \cdot i \cdot \text{Word}(T'')$.

From the construction of the maps $w \mapsto \text{Tree}(w)$ and $T \mapsto \text{Word}(T)$, we clearly have:

**Lemma 4.7.**

(a) Let $w$ be a word on the alphabet $A$ with no repeated letters. Then $w = \text{Word}(\text{Tree}(w))$.

(b) Let $T$ be an increasing ternary tree on the vertex set $A$, made up solely of middle and right edges. Then $T = \text{Tree}(\text{Word}(T))$.
<figure><img src="image_3.png" /><figcaption>Figure 1: (a) This tree $T \in \mathcal{T}'_{10}$ is given edge weights $x, y, y$ for the left, middle and right edges, respectively.</figcaption></figure>

(b) This tree $S \in \mathcal{I}_{10}$ has $\phi_0 = 1$ and $\phi_i = xy^{i-1}$ for every $i \ge 1$, where $\phi_i$ is the weight of a vertex with $i$ children. The leaves get weight $\phi_0 = 1$.

We have $S = \Phi_{10}(T)$. Both trees have weight $x^4 y^6$.

### Construction of the map $\Phi_n : \mathcal{T}'_n \to \mathcal{I}_n$.

Given a tree $T \in \mathcal{T}'_n$, we will now construct a tree $\Phi_n(T) \in \mathcal{I}_n$. To do this, we begin with a tree containing only the root vertex 0. We then iterate $j$ from 0 through $n$ and insert the children of $j$ in $\Phi_n(T)$ as follows: We consider the subtree $\text{left}_T(j)$ in $T$; it consists solely of middle and right edges. The children of $j$ in $\Phi_n(T)$ are then defined to be the letters of Word($\text{left}_T(j)$), which are inserted in order from left to right. That is,

$$ \mathrm{ch}_{\Phi_n(T)}(j) = \mathrm{Word}(\mathrm{left}_T(j)). \qquad (4.2) $$

This defines an ordered tree $\Phi_n(T)$ on the vertex set $[n] \cup \{0\}$. See Figure 1 for an example of a tree $T \in \mathcal{T}'_{10}$ and $\Phi_{10}(T) \in \mathcal{I}_{10}$.

To show that $\Phi_n(T) \in \mathcal{I}_n$, we need to show that the tree $\Phi_n(T)$ is increasing, i.e. that every vertex $j \in [1, n]$ has a parent in $\Phi_n(T)$ with label strictly smaller than $j$. We do this by identifying the parent as follows:

**Lemma 4.8.** Let $j \in [1, n]$ be a non-root vertex in $T$, and let $\mathrm{lanc}(j)$ be its left ancestor. Then $\mathrm{lanc}(j)$ is the parent of $j$ in $\Phi_n(T)$.

**PROOF.** Let $i$ be the parent of $j$ in $\Phi_n(T)$. Then, $j$ is a letter in the child word $\mathrm{ch}_{\Phi_n(T)}(i)$. From (4.2), $j$ must be a vertex of $\mathrm{left}_T(i)$. Thus, from Lemma 4.6 it follows that $i = \mathrm{lanc}(j)$. $\square$

Since $\mathrm{lanc}(j) < j$, we have shown:

**Corollary 4.9.** For $T \in \mathcal{T}'_n$, we have $\Phi_n(T) \in \mathcal{I}_n$.
**Construction of the map** $\Psi_n : \mathcal{I}_n \to \mathcal{T}_n'$.

Given a tree $S \in \mathcal{I}_n$, we will now construct a tree $\Psi_n(S) \in \mathcal{T}_n'$ as follows: We start with a tree rooted at 0. We then iterate through $i \in [n] \cup \{0\}$ and look at $\text{ch}_S(i)$, the child word of $i$ in $S$. If $\text{ch}_S(i) = \emptyset$, then $i$ will have no left child in $\Psi_n(S)$. Otherwise, we create a left edge emanating from $i$ in $\Psi_n(S)$ and attach to it the ternary tree $\text{Tree}(\text{ch}_S(i))$ consisting solely of middle and right edges. Thus, we have

$$ \text{left}_{\Psi_n(S)}(i) = \text{Tree}(\text{ch}_S(i)). \qquad (4.3) $$

When $n = 0$, we clearly have $\Psi_0(S) \in \mathcal{T}_0'$. For $n \ge 1$, we will now show that $\Psi_n(S) \in \mathcal{T}_n'$. In the construction of $\Psi_n(S)$, a vertex $i$ gets a left child $j$ only when $\text{ch}_S(i) \neq \emptyset$ and when $j$ is the root of $\text{Tree}(\text{ch}_S(i))$, or in other words $j$ is the smallest letter in $\text{ch}_S(i)$ which is the same as saying that $j$ is the smallest-numbered child of the vertex $i$ in $S$. Thus, it is clear that every vertex $i$ in $\Psi_n(S)$ can contain at most one left child $j$ and that $j > i$. Next, notice that a vertex $i$ in $\Psi_n(S)$ gets a middle (resp. right) child $j$ only if $i$ and $j$ are both letters of the child word $\text{ch}_S(i^b)$, for some vertex $i^b$ in $T$, and $j$ is the middle (resp. right) child of $i$ in $\text{Tree}(\text{ch}_S(i^b))$. Thus, it is clear that every vertex $i$ in $\Psi_n(S)$ can contain at most one middle child $j$ and at most one right child $j$; furthermore, $j > i$ since $\text{Tree}(\text{ch}_S(i^b))$ is an increasing tree. Also, 0 cannot have any middle or right children in $\Psi_n(S)$ as it does not have any siblings in $S$. This shows that:

**Lemma 4.10.** Given $S \in \mathcal{I}_n$, we have $\Psi_n(T) \in \mathcal{T}_n'$.

We are now ready to prove Proposition 4.5.

**PROOF OF PROPOSITION 4.5 USING BIJECTION.** We will first show that the maps $\Phi_n$ and $\Psi_n$ are inverses of each other. Then we will argue that the number of left edges of a tree $T \in \mathcal{T}_n'$ equals the number of internal vertices of the tree $\Phi_n(T) \in \mathcal{I}_n$.

From equations (4.2) and (4.3) and Lemma 4.7, we observe the following:

(a) For a tree $T \in \mathcal{T}_n'$ and a vertex $j \in [n] \cup \{0\}$ of $T$, we have

$$ \text{left}_{\Psi_n(\Phi_n(T))}(j) = \text{Tree}(\text{ch}_{\Phi_n(T)}(j)) \qquad (4.4a) $$

$$ = \text{Tree}(\text{Word}(\text{left}_T(j))) \qquad (4.4b) $$

$$ = \text{left}_T(j). \qquad (4.4c) $$

Thus, for the trees $T, \Psi_n(\Phi_n(T))$ every vertex $j \in [n] \cup \{0\}$ satisfies $\text{left}_{\Psi_n(\Phi_n(T))}(j) = \text{left}_T(j)$. We now need the following lemma:

**Lemma 4.11.** Let $T_1, T_2 \in \mathcal{T}_n'$. If $\text{left}_{T_1}(j) = \text{left}_{T_2}(j)$ for all $j \in [n] \cup \{0\}$, then $T_1 = T_2$.

**PROOF.** From Lemma 4.6, recall that every vertex $i \neq 0$ belongs to exactly one of the subtrees $\text{left}_{T_1}(j)$ (resp. $\text{left}_{T_2}(j)$) in tree $T_1$ (resp. $T_2$). Since $\text{left}_{T_1}(j) = \text{left}_{T_2}(j)$, a vertex $i$ is the middle (resp. right) child of a vertex $i^b$ in tree $T_1$ if and only if $i$ is the middle (resp. right) child of $i^b$ in tree $T_2$. Also, a vertex $i$ is the left child of a vertex $i^b$ in tree $T_1$ (resp. $T_2$) if and only if it is the root of the tree $\text{left}_{T_1}(i^b)$ (resp. $\text{left}_{T_2}(i^b)$). Thus, we also get that $i$ is the left child of $i^b$ in tree $T_1$ if and only if $i$ is the left child of $i^b$ in tree $T_2$. Thus, $T_1 = T_2$. $\square$

Lemma 4.11 and equation (4.4) together imply $\Psi_n(\Phi_n(T)) = T$.
(b) For a tree $S \in \mathcal{I}_n$ and a vertex $i \in [n] \cup \{0\}$ of $S$, we have

$$ \mathrm{ch}_{\Phi_n(\Psi_n(S))}(i) = \mathrm{Word}(\mathrm{left}_{\Psi_n(S)}(i)) \quad (4.5a) $$

$$ = \mathrm{Word}(\mathrm{Tree}(\mathrm{ch}_S(i))) \quad (4.5b) $$

$$ = \mathrm{ch}_S(i) \quad (4.5c) $$

Equation (4.5) gives us $\Phi_n(\Psi_n(S)) = S$.

Thus, $\Phi_n$ and $\Psi_n$ are inverses of each other.

Finally, notice that a vertex $j$ has a left edge in $T \in \mathcal{T}'_n$ if and only if $j$ has a non-empty child word in the tree $\Phi_n(T)$, which is true if and only if $i$ is an internal vertex of $\Phi_n(T)$. Thus, we have $|\mathcal{T}'_{n,k}| = |\mathcal{I}_{n,k}|$. $\square$

**Remark.** A different bijection between increasing ternary trees and increasing ordered trees was given by Janson, Kuba and Panholzer [32]. Our bijection is new and is different from theirs. We thank Markus Kuba for his comments on this. $\blacksquare$

### 4.2.2 Generating-function proof of Proposition 4.5

We will now use generating functions to provide an alternate proof of Proposition 4.5; this approach also situates it as a special case of a more general result, to be enunciated in Proposition 4.12. We begin by introducing a framework for enumerating increasing ordered trees with very general vertex weights, which was first introduced by Bergeron, Flajolet and Salvy [5] and was further applied in [37].

Let $\phi = (\phi_i)_{i \ge 0}$ be indeterminates, and consider increasing ordered trees on $n$ vertices (here we will use the labels $0, \dots, n-1$) in which each vertex with $i$ children gets a weight $\phi_i$; the weight of the tree, denoted $\mathrm{wt}(T)$, is the product of the weights of its vertices. Let $F(t; \phi)$ be the weighted exponential generating function of such trees, not including the empty tree:

$$ F(t; \phi) \stackrel{\mathrm{def}}{=} \sum_{n=1}^{\infty} \left( \sum_{S \in \mathcal{I}_{n-1}} \mathrm{wt}(S) \right) \frac{t^n}{n!}. \quad (4.6) $$

Also let $\Phi(u)$ be the ordinary generating function of $\phi$:

$$ \Phi(u) \stackrel{\mathrm{def}}{=} \sum_{n=0}^{\infty} \phi_i u^i . \quad (4.7) $$

We call $\Phi(u)$ the **degree function**. It is not difficult to show, by classifying trees according to the degree of the root, that $F(t; \phi)$ satisfies the differential equation [5, eq. (8)]

$$ \frac{d}{dt} F(t; \phi) = \Phi(F(t; \phi)). \quad (4.8) $$

Notice that even though we defined the generating function $F(t; \phi)$ using increasing *ordered* trees, this set-up is very general and we can use different degree functions to enumerate different families of weighted trees. For example, if we substitute $\phi_i = \tilde{\phi}_i/i!$, we may think of $F(t; \phi)$ as the exponential generating function
enumerating increasing unordered trees where each vertex with $i$ children gets weight $\tilde{\phi}_i$.

It turns out that the connection between increasing ternary trees and increasing ordered trees that is asserted in Proposition 4.5 is a special case of a more general connection between increasing trees with degree functions $\Phi$ and $\Psi$ that are related in a particular way, as follows:

**Proposition 4.12.** Let $\hat{\Phi}(u)$ be a formal power series with zero constant term, and let $\mathcal{X}(s)$ be a formal power series satisfying

$$ \hat{\Phi}'(u) = \mathcal{X}(\hat{\Phi}(u)). \qquad (4.9) $$

Now define

$$ \Phi(u) \stackrel{\text{def}}{=} 1 + x \hat{\Phi}(u) \qquad (4.10a) $$

$$ \Psi(u) \stackrel{\text{def}}{=} (1 + xu) \mathcal{X}(u) \qquad (4.10b) $$

Let $\mathcal{A}(t) \stackrel{\text{def}}{=} F(t; \phi)$ with degree function $\Phi(u)$, and let $\mathcal{B}(t) \stackrel{\text{def}}{=} F(t; \psi)$ with degree function $\Psi(u)$. Then the following identities hold:

$$ \mathcal{B}(t) = \hat{\Phi}(\mathcal{A}(t)) \qquad (4.11a) $$

$$ \mathcal{A}'(t) = 1 + x\mathcal{B}(t) \qquad (4.11b) $$

**PROOF.** The definition $\mathcal{B}(t) = F(t; \psi)$ implies the differential equation

$$ \mathcal{B}'(t) = \Psi(\mathcal{B}(t)) = (1 + x\mathcal{B}(t)) \mathcal{X}(\mathcal{B}(t)) \qquad (4.12) $$

by (4.8) and (4.10b). On the other hand, the definition $\mathcal{A}(t) = F(t; \phi)$ implies the differential equation

$$ \frac{d}{dt}\hat{\Phi}(\mathcal{A}(t)) = \hat{\Phi}'(\mathcal{A}(t))\mathcal{A}'(t) \qquad (4.13a) $$

$$ = \mathcal{X}(\hat{\Phi}(\mathcal{A}(t))) \Phi(\mathcal{A}(t)) \qquad (4.13b) $$

$$ = \mathcal{X}(\hat{\Phi}(\mathcal{A}(t))) [1 + x\hat{\Phi}(\mathcal{A}(t))] \qquad (4.13c) $$

by the chain rule, (4.9), (4.8) and (4.10a). So $\mathcal{B}(t)$ and $\hat{\Phi}(\mathcal{A}(t))$ satisfy the same differential equation with the same initial condition (namely, they vanish at $t = 0$), hence they are equal. This proves (4.11a).

Then

$$ \mathcal{A}'(t) = \Phi(\mathcal{A}(t)) = 1 + x\hat{\Phi}(\mathcal{A}(t)) = 1 + x\mathcal{B}(t) \qquad (4.14) $$

by (4.8), (4.10a) and (4.11a). This proves (4.11b). $\square$

**PROOF OF PROPOSITION 4.5 USING GENERATING FUNCTIONS.** We will now prove Proposition 4.5 by using Proposition 4.12. First, consider the exponential generating function $\mathcal{A}(t) \stackrel{\text{def}}{=} F(t; (\delta_{i0} + (1 - \delta_{i0})xy^{i-1}))_{i \ge 0}$: thus, $\mathcal{A}(t)$ is the exponential generating function for increasing ordered trees on $n$ labeled vertices where each leaf is
given weight $\phi_0 = 1$ and each vertex with $i \ge 1$ children is given weight $\phi_i = xy^{i-1}$. Therefore, the degree function is

$$ \Phi(u) = 1 + \frac{xu}{1 - yu} \qquad (4.15) $$

and $\mathcal{A}(t)$ satisfies the differential equation

$$ \mathcal{A}' = 1 + \frac{x\mathcal{A}}{1 - y\mathcal{A}}. \qquad (4.16) $$

In the weight $\phi_i = (x/y)y^i$ for internal vertices, we can transfer a weight $y$ to each of the $i$ children; since every vertex other than the root is a child, we end up with a weight $y$ for leaves and $x$ for internal vertices, with an overall factor $1/y$ because the root is not a child. Therefore, from (4.6) we have

$$ \mathcal{A}(t) = \sum_{n=1}^{\infty} \left( \sum_{S \in \mathcal{I}_{n-1}} x^{\text{intvertex}(S)} y^{\text{leaf}(S)-1} \right) \frac{t^n}{n!} \qquad (4.17) $$

where intvertex(S) and leaf(S) denote the number of internal vertices and leaves of the tree $S \in \mathcal{I}_{n-1}$, respectively.

We use the notation from Proposition 4.12 to obtain

$$ \hat{\Phi}(u) = \frac{u}{1 - yu} \qquad (4.18a) $$

$$ \mathcal{X}(s) = (1 + ys)^2 \qquad (4.18b) $$

$$ \Psi(u) = (1 + xu)(1 + yu)^2 \qquad (4.18c) $$

We then define $\mathcal{B}(t) \stackrel{\text{def}}{=} F(t; \psi)$ with degree function $\Psi(u) = (1 + xu)(1 + yu)^2$. We can interpret $\mathcal{B}(t)$ as the exponential generating function for increasing ternary trees on the vertex set $[n]$, where each left edge gets a weight $x$ and each middle or right edge gets a weight $y$, and the weight of a tree is the product of the weights of its edges. Passing to trees on the vertex set $[n] \cup \{0\}$ in which the only edge (if any) emanating from the root is a left edge, we get an exponential generating function

$$ 1 + x \mathcal{B}(t) = \sum_{n=0}^{\infty} \left( \sum_{T \in \mathcal{T}_n'} x^{l(T)} y^{m(T)+r(T)} \right) \frac{t^n}{n!} \qquad (4.19) $$

where $l(T), m(T), r(T)$ denote the number of left, middle and right edges of a tree $T \in \mathcal{T}_n$, respectively. Finally, we use Proposition 4.12 to obtain

$$ \mathcal{A}'(t) = 1 + x \mathcal{B}(t) \qquad (4.20) $$

Combining equations (4.17), (4.19) and (4.20) finishes the proof. $\square$

We end this section with a few remarks concerning some interesting special cases of Proposition 4.12:
**Remarks.** 1. If we take $\mathcal{X}(s) = 1+ys$ and solve (4.9), we get $\hat{\Phi}(u) = (e^{yu}-1)/y$ and hence

$$ \Phi(u) = 1 + \frac{x}{y}(e^{yu} - 1), \qquad (4.21) $$

so that $\phi_0 = 1$ and $\phi_i = xy^{i-1}/i!$ for $i \ge 1$. It follows that $\mathcal{A}(t)$ is the exponential generating function for increasing unordered trees on the vertex set $[n-1]\cup\{0\}$, with a weight 1 for each leaf and a weight $xy^{i-1}$ for each vertex with $i \ge 1$ children; or equivalently (as we saw in the foregoing proof), with a weight $y$ for leaves and $x$ for internal vertices and an overall factor $1/y$. On the other hand,

$$ \Psi(u) = (1+xu)(1+yu), \qquad (4.22) $$

so that $\mathcal{B}(t)$ is the exponential generating function for increasing binary trees on the vertex set $[n]$, with a weight $x$ for each left edge and $y$ for each right edge. Specializing to $x = y = 1$, this shows

$$ \mathcal{B}(t)|_{x=y=1} = \exp(\mathcal{A}(t)|_{x=y=1}) - 1 = \mathcal{A}'(t)|_{x=y=1} - 1, \qquad (4.23) $$

i.e., unordered increasing trees on $n+1$ vertices are equinumerous with increasing binary trees on $n$ vertices, a fact that is well known and can be proven bijectively [44, pp. 44–46]. Furthermore, this also tells us that the left edges in the binary trees are in correspondence with the internal vertices in the corresponding unordered increasing tree.

2. If we take $\mathcal{X}(s) = (1+ys)^k$ with $k \neq 1$ and solve (4.9), we obtain

$$ \hat{\Phi}(u) = \frac{[1 - (k-1)yu]^{-1/(k-1)} - 1}{y}. \qquad (4.24) $$

In particular, for integer $k \ge 2$, the degree function $\Phi(u) = 1 + x\hat{\Phi}(u)$ obtained from (4.24) describes increasing ordered trees in which each leaf gets a weight $\phi_0 = 1$ and each vertex with $i \ge 1$ children gets a weight $\phi_i = \frac{1}{i!}xy^{i-1}\prod_{j=1}^{i-1}[1 + j(k-1)]$ (in particular, $\phi_1 = x$). When $k = 2$ this reduces to the situation addressed in Proposition 4.5 [cf. (4.18)]. Such trees on $n+1$ vertices are in bijection with $(k+1)$-ary trees on $n+1$ vertices in which the root can have only a first child.

3. If we take $\mathcal{X}(s) = e^{ys}$ and solve (4.9), we obtain

$$ \hat{\Phi}(u) = -\frac{1}{y}\log(1 - yu) \qquad (4.25) $$

and hence

$$ \Phi(u) = 1 - \frac{x}{y}\log(1 - yu), \qquad (4.26) $$

so that $\phi_0 = 1$ and $\phi_i = xy^{i-1}/i$ for $i \ge 1$. It follows that $\mathcal{A}(t)$ is the exponential generating function for increasing cyclically-ordered trees on the vertex set $\{0\}\cup[n-1]$, with a weight 1 for each leaf and a weight $xy^{i-1}$ for each vertex with $i \ge 1$ children; or equivalently, with a weight $y$ for leaves and $x$ for internal vertices and an overall factor $1/y$. On the other hand,

$$ \Psi(u) = (1 + xu)e^{yu}, \qquad (4.27) $$
so that $\mathcal{B}(t)$ is the exponential generating function for increasing trees on vertex set $[n]$ in which every vertex has zero or one left child (with weight $x$) and an arbitrary number of unordered right children (with weight $y$). Therefore, $1 + x\mathcal{B}(t)$ is the exponential generating function for increasing trees of the same type on vertex set $\{0\} \cup [n]$, but in which the root 0 can only have a left child. It follows that these trees are in bijection with cyclically-ordered trees on the vertex set $\{0\} \cup [n]$.

**Problem 4.13.** Find bijections that explain Remarks 2 and 3.

4. On specializing to $y = 1 + x$ in the degree function (4.15), we obtain the weights $\phi_0 = 1$ and $\phi_i = x(1+x)^{i-1}$ for $i \ge 1$. This sequence is not coefficientwise Toeplitz-totally positive in the variable $x$ — or even Toeplitz-totally positive for any fixed real number $x > 0$ — since its generating function

$$ \Phi(u) = 1 + \sum_{i=1}^{\infty} x(1+x)^{i-1}u^i = \frac{1-u}{1-(1+x)u} \quad (4.28) $$

has a zero on the positive real axis at $u = 1$, which cannot happen for a Toeplitz-totally positive sequence [33, p. 412, Theorem 5.3]. However, by combining Proposition 4.5 with equation (1.26), we deduce that the generating polynomials of increasing ordered trees in $\mathcal{I}_n$ with the weights $\phi$ are the second-order Stirling cycle polynomials $c_{2,n}(x)$; and from Theorem 1.5 we see that the sequence $c_{2,n}(x)$ is coefficientwise Hankel-totally positive in the variable $x$.

This example has an important consequence for the understanding of [37, Theorem 1.1] concerning the Hankel-total positivity of the generic Lah polynomials. We see that, although this sequence $\phi$ is not Toeplitz-totally positive, the resulting sequence of generating polynomials in [37, Theorem 1.1(c)] is still coefficientwise Hankel-totally positive. Thus, the condition of $\phi$ being Toeplitz-totally positive is only a sufficient condition and is far from necessary for the conclusion of [37, Theorem 1.1(c)] to hold. In [17], we take $\Phi(u)$ is to be a polynomial in $u$ of degree 3 or 4, and we study the exact necessary and sufficient conditions under which the conclusion of [37, Theorem 1.1(c)] holds true. ■

### 4.2.3 Vertex-marked increasing ordered trees

Having established Proposition 4.5, we are now ready to state our fourth interpretation for the second-order Stirling cycle numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$.

We define a *vertex-marked increasing ordered tree* to be an increasing ordered tree in which each leaf can be marked or unmarked; the internal vertices are always unmarked. For $n = 0$, we declare that the vertex 0 is always marked. We write $\tilde{\mathcal{I}}_{n,k}$ for the set of vertex-marked increasing ordered trees on the vertex set $[n] \cup \{0\}$ with $k$ unmarked vertices. In this section we will show that the cardinality of the set $\tilde{\mathcal{I}}_{n,k}$ is $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$.

Recall also from Section 4.1 that $\tilde{\mathcal{T}}_{n,k}$ denotes the set of trees in $T \in \mathcal{T}'_n$ along with optional edge markings in which each edge can be either marked or unmarked such that left edges are always unmarked, and which contain $k$ unmarked edges.

Before providing the proofs, let us observe that using the bijection and the correspondence between left edges and internal vertices in Proposition 4.5, and we get the following corollary:
**Corollary 4.14.** The sets $\hat{T}_{n,k}$ and $\hat{\mathcal{I}}_{n,k}$ are in bijective correspondence. Thus, the cardinality of $\hat{\mathcal{I}}_{n,k}$ is given by

$$ |\hat{\mathcal{I}}_{n,k}| = \begin{bmatrix} n \\ k \end{bmatrix}^{(2)}. \qquad (4.29) $$

**PROOF.** First notice that for $n = 0$, we have $|\hat{T}_{0,0}| = |\hat{\mathcal{I}}_{0,0}| = 1$. Henceforth, we assume $n \ge 1$. For a tree $S \in \mathcal{I}_n$, let invertex($S$) denote the number of internal vertices of $S$ and let leaf($S$) denote the number of leaves of $S$. Also, for a tree $T \in \mathcal{T}'_n$, let $l(T)$, $m(T)$, $r(T)$ denote the number of left, middle and right edges of $T$, respectively. Then we clearly obtain the following

$$ \sum_{k=0}^{n} |\hat{\mathcal{I}}_{n,k}| x^k = \sum_{S \in \mathcal{I}_n} x^{\text{invertex}(S)} (1+x)^{\text{leaf}(S)} \qquad (4.30a) $$

$$ = \sum_{T \in \mathcal{T}'_n} x^{l(T)} (1+x)^{m(T)} (1+x)^{r(T)} \qquad (4.30b) $$

$$ = \sum_{k=0}^{n} |\hat{T}_{n,k}| x^k \qquad (4.30c) $$

where (4.30a) follows from the definition of the sets $\mathcal{I}_n, \hat{\mathcal{I}}_{n,k}$, (4.30b) follows from Proposition 4.5, and (4.30c) follows from the definition of the sets $\mathcal{T}'_n, \hat{T}_{n,k}$. This completes the proof. $\square$

We thus have our fourth combinatorial interpretation for the numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$.

## 4.3 Interpretation V: Cyclically-ordered phylogenetic trees

Here we introduce our fifth and final combinatorial interpretation of the second-order Stirling cycle numbers. This interpretation will lead us to a common generalization of the second-order Stirling numbers of both kinds and also lead us to another conjecture similar to Conjectures 1.3 and 1.4.

A **phylogenetic tree** is a leaf-labeled rooted tree (i.e. the leaves are labeled and the non-leaf vertices are unlabeled) in which all non-leaf vertices have at least two children. We refer to them as an **unordered phylogenetic tree**, an **ordered phylogenetic tree**, or a **cyclically-ordered phylogenetic tree** according to whether the children at each vertex are unordered, linearly ordered or cyclically ordered. Cyclically-ordered phylogenetic trees have also been called **series-reduced mobiles** [35, A032188] [1]. Let $M_{n,k}$ denote the set of all cyclically-ordered phylogenetic trees with $n+1$ leaves and $k$ internal (i.e. non-leaf) vertices.

We will now establish the following proposition:

**Proposition 4.15.** The cardinality of the set $M_{n,k}$ of cyclically-ordered phylogenetic trees with $n+1$ leaves and $k$ internal vertices is given by

$$ |M_{n,k}| = \begin{bmatrix} n \\ k \end{bmatrix}^{(2)}. \qquad (4.31) $$
We will provide two different proofs of Proposition 4.15. Our first proof will show that the numbers $|\mathcal{M}_{n,k}|$ satisfy the recurrence relation (1.15). Our second proof will use generating functions for the multivariate Ward polynomials introduced by Elvey Price and Sokal in [23].

PROOF OF PROPOSITION 4.15 USING RECURRENCE RELATIONS. We will show that the numbers $|\mathcal{M}_{n,k}|$ satisfy

$$|\mathcal{M}_{n,k}| = (n+k-1)|\mathcal{M}_{n-1,k-1}| + (n+k-1)|\mathcal{M}_{n-1,k}|. \quad (4.32)$$

To do this, we will consider two cases whether or not the leaf labeled $n+1$ has exactly one sibling.

If $n+1$ has at least two siblings, we can remove it, and the resulting tree belongs to $\mathcal{M}_{n-1,k}$. Conversely, to insert $n+1$ into a tree belonging to $\mathcal{M}_{n-1,k}$, it suffices to choose the vertex that would be its immediately preceding (in the cyclic order) sibling in the resulting tree. There are $n+k-1$ such choices. This contributes the term $(n+k-1)|\mathcal{M}_{n-1,k}|$.

If $n+1$ has exactly one sibling, then the tree obtained by removing it is no longer a phylogenetic tree, as the parent of $n+1$ would now have only one child. Instead, we proceed as follows:

* If the parent of $n+1$ is not the root, we contract the edge between the parent and grandparent of $n+1$ and then remove $n+1$ from the resulting tree; this gives us a tree in $\mathcal{M}_{n-1,k-1}$. Conversely, to insert $n+1$ back into this tree, we need to select an edge, and elongate it by adding an extra internal vertex and then insert $n+1$ as the other child of this new internal vertex. As there are $n+k-2$ edges, we get a contribution of $(n+k-2)|\mathcal{M}_{n-1,k-1}|$.

* If the parent of $n+1$ is the root, we remove the root and the vertex $n+1$ to obtain a tree rooted at the sibling of $n+1$. Conversely, we can re-obtain the original tree by creating a new root whose children are the old root and vertex $n+1$. This contributes $|\mathcal{M}_{n-1,k-1}|$.

Putting these two contributions together gives $(n+k-1)|\mathcal{M}_{n-1,k-1}|$. $\square$

For our second proof of Proposition 4.15, we require the multivariate Ward polynomials introduced in [23, pp. 9–11]. As mentioned in Section 1.3, our second-order Stirling subset polynomials $s_{2,n}(x)$ are usually referred to as the Ward polynomials, and the numbers $\binom{n}{k}^{(2)}$ are the Ward numbers. It is known [23, p. 5] that the Ward number $\binom{n}{k}^{(2)}$ counts the number of phylogenetic trees (with unordered children) on $n+1$ leaves and $k$ internal vertices. Thus, the polynomial $s_{2,n}(x)$ is the generating polynomial of phylogenetic trees on $n+1$ leaves in which each internal vertex gets a weight $x$. Now let $\mathbf{x} = (x_i)_{i \ge 1}$ be an infinite collection of indeterminates. The multivariate Ward polynomials $\mathbf{W}_n(\mathbf{x}) = \mathbf{W}_n(x_1, \dots, x_n)$ are a multivariate generalization of the polynomials $s_{2,n}(x)$: they are the generating polynomial for phylogenetic trees on $n+1$ labeled leaves in which each internal vertex with $i$ ($\ge 2$) children gets a weight $x_{i-1}$. Thus $s_{2,n}(x) = \mathbf{W}_n(x, \dots, x)$. The polynomial $\mathbf{W}_n(\mathbf{x})$ is quasi-homogeneous of degree $n$ when $x_i$ is given weight $i$. The first few $\mathbf{W}_n$
are [35, A134685]

$$ \mathbf{W}_0 = 1 \qquad (4.33a) $$

$$ \mathbf{W}_1 = x_1 \qquad (4.33b) $$

$$ \mathbf{W}_2 = 3x_1^2 + x_2 \qquad (4.33c) $$

$$ \mathbf{W}_3 = 15x_1^3 + 10x_1x_2 + x_3 \qquad (4.33d) $$

$$ \mathbf{W}_4 = 105x_1^4 + 105x_1^2x_2 + 15x_1x_3 + 10x_2^2 + x_4 \qquad (4.33e) $$

It is not difficult to show that the exponential generating function

$$ W(t; \mathbf{x}) \stackrel{\text{def}}{=} \sum_{n=0}^{\infty} \mathbf{W}_n(\mathbf{x}) \frac{t^{n+1}}{(n+1)!} = t + \sum_{n=2}^{\infty} \mathbf{W}_{n-1}(\mathbf{x}) \frac{t^n}{n!} \qquad (4.34) $$

satisfies the functional equation [23, eq. (1.18)]

$$ W(t; \mathbf{x}) = t + \sum_{j=2}^{\infty} x_{j-1} \frac{W(t; \mathbf{x})^j}{j!}, \qquad (4.35) $$

where the term $j$ in the sum corresponds to the case in which the root has $j$ children.

**PROOF OF PROPOSITION 4.15 USING GENERATING FUNCTIONS.** With the specialization $x_i = i! x$, the polynomials $\mathbf{W}_n(x, 2x, \dots, n! x)$ are the generating polynomials of cyclically-ordered phylogenetic trees with weight $x$ given to each internal vertex and a weight 1 to each leaf. We therefore want to show that $\mathbf{W}_n(x, 2x, \dots, n! x) = c_{2,n}(x)$. We call these polynomials $W_n(x) \stackrel{\text{def}}{=} \mathbf{W}_n(x, 2x, \dots, n! x)$, and we denote the corresponding exponential generating function by $W(t; x)$. Thus, the functional equation (4.35) is now

$$ W(t; x) = t + \sum_{j=2}^{\infty} W(t; x)^j \frac{x^j}{j}. \qquad (4.36) $$

This can be rewritten as

$$ W(t; x) = t - x \log[1 - W(t; x)] - x W(t; x). \qquad (4.37) $$

Differentiating both sides with respect to $t$ and solving for $W'$, we obtain

$$ W' = \frac{1}{1 - x \frac{W}{1 - W}} = 1 + \frac{x W}{1 - (1 + x) W}. \qquad (4.38) $$

However, this is exactly the same as the differential equation (4.16) with $y = 1 + x$ which is satisfied by the exponential generating function for increasing ordered trees on $[n] \cup \{0\}$ where each leaf is given a weight 1 and each vertex with $i \ge 1$ children is given a weight $x(1+x)^{i-1}$. Thus, the result follows by combining Proposition 4.5 and equation (1.26). $\square$

**Final remark and conjecture.** As mentioned earlier, it was noticed in [23] that the number of phylogenetic trees with unordered children having $n+1$ leaves and $k$ internal vertices is the second-order Stirling subset number $\binom{n}{k}^{(2)}$. In Proposition 4.15
we established that the number of phylogenetic trees with cyclically-ordered children having $n + 1$ leaves and $k$ internal vertices is the second-order Stirling cycle number $\begin{bmatrix} n \\ k \end{bmatrix}^{(2)}$. The generating polynomials in both cases can be obtained as specializations of the multivariate Ward polynomials: the former by setting $x_i = x$, the latter by setting $x_i = i!x$. After these two observations, it is very natural to inquire about the number of phylogenetic trees with linearly-ordered children having $n + 1$ leaves and $k$ internal vertices. Let us denote this number by $\begin{Bmatrix} n \\ k \end{Bmatrix}$. Their generating polynomials are obtained by setting $x_i = (i + 1)!x$ in the multivariate Ward polynomials. The first few of these numbers are

<table><thead><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>Row sums</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>0</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td>2</td></tr><tr><td>2</td><td>0</td><td>6</td><td>12</td><td></td><td></td><td></td><td></td><td>18</td></tr><tr><td>3</td><td>0</td><td>24</td><td>120</td><td>120</td><td></td><td></td><td></td><td>264</td></tr><tr><td>4</td><td>0</td><td>120</td><td>1080</td><td>2520</td><td>1680</td><td></td><td></td><td>5400</td></tr><tr><td>5</td><td>0</td><td>720</td><td>10080</td><td>40320</td><td>60480</td><td>30240</td><td></td><td>141840</td></tr><tr><td>6</td><td>0</td><td>5040</td><td>100800</td><td>604800</td><td>1512000</td><td>1663200</td><td>665280</td><td>4551120</td></tr></tbody></table>

and they seem to match [35, A357367], namely<fnref n="11" />

$$ \begin{Bmatrix} n \\ k \end{Bmatrix} = \frac{(n+k)!}{k!} \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}. \qquad (4.39) $$

This is, in fact, true:

**Proposition 4.16.** The cardinality of the set of all phylogenetic trees with linearly ordered children having $n + 1$ leaves and $k$ internal vertices is given by (4.39).

PROOF. We show that the numbers $\begin{Bmatrix} n \\ k \end{Bmatrix}$ satisfy the recurrence

$$ \begin{Bmatrix} n \\ k \end{Bmatrix} = (2n + 2k - 2) \begin{Bmatrix} n - 1 \\ k - 1 \end{Bmatrix} + (n + 2k - 1) \begin{Bmatrix} n - 1 \\ k \end{Bmatrix}. \qquad (4.40) $$

Our argument is a modification of the proof of Proposition 4.15 using recurrence relations, and we leave the details to the reader. Equation (4.39) then follows, as it is easy to see that the numbers $[(n + k)!/k!](n-1)_{k-1}$ also satisfy the same recurrence. □

Let $d_n(x)$ denote the generating polynomials

$$ d_n(x) \stackrel{\text{def}}{=} \sum_{k=0}^{n} \begin{Bmatrix} n \\ k \end{Bmatrix} x^k, \qquad (4.41) $$

and let $D$ be the lower-triangular matrix $D = \begin{Bmatrix} n \\ k \end{Bmatrix}_{n,k \ge 0}$.

Similar to Conjectures 1.3 and 1.4, we have the following conjecture:

<footnote n="11">¹¹This explicit formula is not yet shown at [35, A357367].</footnote>
**Conjecture 4.17** (Conjecture for ordered phylogenetic trees). The following are true:

(a) *The triangle D is totally positive.*

(b) *The triangle $D^{\text{rev}}$ formed by reversing the rows of $D$ is totally positive.*

(c) *The sequence $(d_n(x))_{n \ge 0}$ is coefficientwise Hankel-totally positive in the variable $x$.*

The polynomials $d_n(x)$ are also negative-real-rooted, and in this case we are able
to prove it:

**Theorem 4.18.** For every $n \ge 1$, the polynomials $d_n(x)$ have 0 as a root; and the zeros of the polynomial sequence $(d_n(x)/x)_{n \ge 1}$ are simple, interlacing, and lie in the interval $(-1, 0)$.

The proof of Theorem 4.18 is similar to that of Theorem 1.6 (which we will see in
Section 6) and we omit it. $\blacksquare$

We leave the further study of the multivariate Ward polynomials as an open
problem. In particular, it would be interesting to find sufficient conditions for Hankel-
total positivity, analogous to [37, Theorem 1.1].

## 4.4 A final remark

The diagonal entries of the second-order Stirling cycle matrix $C^{(2)}$ are $(2n-1)!!$ [cf. (1.12)], and the reader will observe that the first four of our combinatorial interpretations of the second-order Stirling cycle numbers are based on taking well-known [10] objects of cardinality $(2n-1)!!$ and then “augmenting” them:

• Perfect matchings of $[2n] \to$ Derangements of $[n+k]$ containing $k$ cycles

• Stirling permutations of $\{1, 1, 2, 2, \dots, n, n\} \to$ Ascent-marked Stirling permutations of $\{1, 1, 2, 2, \dots, n, n\}$

• Increasing ternary trees on $[n] \to$ Edge-marked increasing ternary trees on $[n]$

• Increasing ordered trees on $[n] \cup \{0\} \to$ Edge-marked increasing ordered trees on $[n] \cup \{0\}$

In fact, also the second-order Stirling subset matrix $S^{(2)}$ has diagonal entries $(2n-1)!!$ [cf. again (1.12)], and the construction of Elvey Price and Sokal [23] was also based on a similar “augmentation”:

• Perfect matchings of $[2n] \to$ Augmented and super-augmented perfect matchings of $[2n]$

We wonder whether the $r$-th order Stirling cycle and subset polynomials for $r \ge 3$ can be handled by a similar approach: namely, find a class of combinatorial objects enumerated by the numbers (1.10) or (1.11), and then “augment” them to handle the matrix elements with $k < n$. We will use this approach to construct an analogue of Stirling permutations for $r \ge 3$ in Section 5; this will give us a new interpretation for the $r$-th order Stirling cycle numbers.
## 5 Interpretation for r-th order Stirling cycle numbers

We will now provide an interpretation for the r-th order Stirling cycle numbers that generalizes the interpretation given for $r = 2$ in Section 3.2. We will also provide an interpretation for the r-th-order quasi-Eulerian cycle numbers $\langle\langle n \rangle\rangle_C^{(r)}$.

To begin, let us first provide an interpretation for the numbers $\langle\langle n \rangle\rangle_C^{(r)} = (rn)!/(r^n n!)$ for $r \ge 2$. To do this, let us first consider the multiset

$$ M_n^{(r)} \stackrel{\text{def}}{=} \{1^{a_1}, 2^{a_2}, \dots, (r-1)n^{a_{(r-1)n}}\} \qquad (5.1) $$

where $a_i$ is the multiplicity of the letter $i$ and it is defined by

$$ a_i = \begin{cases} 2 & \text{if } i \equiv 0 \pmod{r-1} \\ 1 & \text{otherwise} \end{cases} \qquad (5.2) $$

Thus, for $r = 2$ we have $M_n^{(2)} = \{1, 1, 2, 2, 3, 3, \dots, n, n\}$ and for $r = 3$ we have $M_n^{(3)} = \{1, 2, 2, 3, 4, 4, \dots, 2n-1, 2n, 2n\}$. Let $\mathfrak{S}_n^{(r)}$ denote the set of Stirling permutations of the multiset $M_n^{(r)}$. It immediately follows from [32, eq. (1)] that

$$ \begin{bmatrix} n \\ n \end{bmatrix}^{(r)} = |\mathfrak{S}_n^{(r)}|. \qquad (5.3) $$

The set $\mathfrak{S}_n^{(r)}$ is our first ingredient. Notice that each $\sigma \in \mathfrak{S}_n^{(r)}$ is a string of length $rn$ consisting of $(r-1)n$ distinct letters.

Our next ingredient is a new combinatorial statistic on Stirling permutations in $\mathfrak{S}_n^{(r)}$. Given $\sigma \in \mathfrak{S}_n^{(r)}$, we say that $i \in [n]$ is a **consecutive ascent** in $\sigma$ if the following two conditions hold:

* if the following $r-1$ letters: $(r-1)i+1, (r-1)i+2, \dots, (r-1)i+(r-2)$ and the first occurrence of $(r-1)(i+1)$, occur consecutively in $\sigma$.

* the letter $(r-1)i+1$ is preceded by a lower-numbered letter in $\sigma$.

An alternate way of saying this is that the string $a_1a_2\dots a_{r-1}$ where $a_j = (r-1)i+j$ occurs as a substring in $\sigma$ and $a_1$ is preceded by a lower-numbered letter. Thus, if $i \in [n]$ is a consecutive ascent in $\mathfrak{S}_n^{(r)}$, then the $r-1$ letters, $(r-1)i+1, (r-1)i+2, \dots, (r-1)i+(r-2)$ and the first occurrence of $(r-1)(i+1)$, are the ends of ascents (i.e. $a$ in $\sigma_i < \sigma_{i+1} = a$). Let $CAsc(\sigma) \subseteq [n]$ denote the set of consecutive ascents in $\sigma$. We then define $\mathfrak{S}_{n,k}^{(r)}$ to be the set of Stirling permutations in $\mathfrak{S}_n^{(r)}$ with $k$ consecutive ascents:

$$ \mathfrak{S}_{n,k}^{(r)} \stackrel{\text{def}}{=} \{\sigma \in \mathfrak{S}_n^{(r)} : \text{CAsc}(\sigma) = k\}. \qquad (5.4) $$

Notice that when $r = 2$, consecutive ascents are the same as ascents in Stirling permutations, so $|\mathfrak{S}_{n,k}^{(2)}| = \langle\langle n \rangle\rangle$.

A **consecutive-ascent-marked Stirling permutation of order $r$ and size $n$ with $k$ dots** is defined to be a pair $(\sigma, D)$ where $\sigma \in \mathfrak{S}_n^{(r)}$ and $D \subseteq CAsc(\sigma) \subseteq$
$[n]$ and $|D| = k$. We let $\mathcal{V}_{n,k}^{(r)}$ denote the set of consecutive-ascent-marked Stirling permutation of order $r$ and size $n$ with $k$ dots. Thus, when $r = 2$ we have the interpretation in Section 3.2. For $r = 3$, we have $\mathcal{V}_{2,0}^{(3)}$ is equivalent to $\mathfrak{S}_2^{(3)}$ (as we always have $D = \emptyset$) which has cardinality 40 and hence we refrain from listing out. For $k = 1$, we have

$$ \mathcal{V}_{2,1}^{(3)} = \{122 \cdot 3 \cdot 44, 12 \cdot 3 \cdot 442, 1 \cdot 3 \cdot 4422\}. \qquad (5.5) $$

Here we have inserted dots to the $r-1 = 2$ ascents corresponding to each of the $i \in D$.

Let $v_{n,k}^{(r)} = |\mathcal{V}_{n,k}^{(r)}|$ and $b_{n,k}^{(r)} = |\mathfrak{S}_{n,k}^{(r)}|$; then

$$ v_{n,k}^{(r)} = \sum_{i=k}^{n} b_{n,i}^{(r)} \binom{i}{k} . \qquad (5.6) $$

Notice that for $r = 2$, the identity $a_{n,k}^{(2)} = \langle\langle n \rangle\rangle$ together with Proposition 1.2(a), which gives us (3.4), implies $v_{n,k}^{(2)} = \binom{n}{n-k}^{(2)}$.

We will now establish the following lemma, which generalises Lemma 3.1:

**Lemma 5.1.** The numbers $v_{n,k}^{(r)}$ satisfy the recurrence

$$ v_{n,k}^{(r)} = (r-1)! \binom{r(n-1) - (r-1)(k-1)}{r-1} v_{n-1,k}^{(r)} + [r(n-1) - (r-1)(k-1)] v_{n-1,k-1}^{(r)} \qquad (5.7) $$

with initial conditions $v_{0,k}^r = \delta_{k0}$ and $v_{n,-1}^r = 0$.

**PROOF.** Let $(\sigma, D) \in \mathcal{V}_{n,k}^{(r)}$ be a consecutive-ascent-marked Stirling permutation of order $r$ and size $n$ with $k$ dots. Throughout this proof, we set $a_j = (r-1)(n-1)+j$ where $1 \le j \le r-1$ and $a_r = (r-1)n$.

First, notice that on deleting the $r-2$ letters $a_1, \dots, a_{r-2}$ along with the two letters $a_{r-1}, a_r$ in $\sigma$ together with $n \in D$, if it exists, gives an element of $\mathcal{V}_{n-1,k}^{(r)}$ if $n \notin D$, and an element of $\mathcal{V}_{n-1,k}^{(r)}$ if $n \in D$.

Conversely, to get an element $(\sigma, D) \in \mathcal{V}_{n,k}^{(r)}$ with $n \notin D$ from a one-size-smaller ascent-marked Stirling permutation, we insert the $r$ letters $a_1, \dots, a_{r-2}, a_{r-1}, a_r$. For convenience, let $l = r(n-1) - (r-1)k$. Notice that there are $l+1$ choices to insert the letter $a_1$ (these consist of any of the $r(n-1)+1$ spaces except for the $(r-1)k$ corresponding to dots), $l+2$ to insert the letter $a_2$, and so on until we finally get $l+(r-1)$ choices for inserting $a_{r-1}a_r$. Thus, there are a total of $(r-1)!(\binom{l+r-1}{r-1})$ choices.

In the other case, if $(\sigma, D) \in \mathcal{V}_{n,k}^{(r)}$ with $n \in D$, then the string $a_1a_2\dots a_{r-1}$ is a substring of $\sigma$. To get such a pair $(\sigma, D)$, the string $a_1a_2\dots a_{r-1}a_r$ can be inserted into an element of $\mathcal{V}_{n-1,k-1}^{(r)}$ in any of the $r(n-1)+1$ spaces except the first space and those corresponding to a dot; thus, the number of choices is $r(n-1)-(r-1)(k-1)$.

This proves the recurrence (5.7). $\square$

Finally, we use Lemma 5.1 to obtain our combinatorial interpretation for the $r$th-order Stirling cycle numbers and for the $r$th-order quasi-Eulerian cycle numbers; we state this in the following proposition:
**Proposition 5.2.** The entries of the matrix $Q_C^{(r)} = \tilde{C}^{(r)}B^{-1}$ of rth-order quasi-Eulerian cycle numbers have the combinatorial interpretation

$$ \left\langle\left\langle\left\langle\left\langle n \right|\right|\right|\right\rangle\right\rangle_C^{(r)} = |\mathfrak{S}_{n,k}^{(r)}|. \qquad (5.8) $$

Also, the rth-order Stirling cycle number $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)}$ counts the number of consecutive-ascent-marked Stirling permutations of order r and size n with n-k dots, i.e., $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)} = |\mathcal{V}_{n,n-k}^{(r)}|$.

**PROOF.** We now need to show that $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)} = v_{n,n-k}^{(r)}$ and $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)} = b_{n,k}^{(r)}$.

From (5.7) it follows that the numbers $u_{n,k}^{(r)} = v_{n,n-k}^{(r)}$ satisfies the recurrence (1.13) which is satisfied by the numbers $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)}$. Since these numbers also satisfy the same initial conditions, we infer that $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)} = u_{n,k}^{(r)}$. Finally, from the definition of $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)}$ and (5.6), it follows that $\begin{bmatrix} n \\ k \end{bmatrix}^{(r)} = b_{n,k}^{(r)}$. $\square$

# 6 Location of zeros for the second-order Stirling cycle and subset polynomials

We will now prove Theorem 1.6 in this section.

For $r, n \ge 1$, it is clear from $(1.17)/(1.18)$ that $c_{r,n}(0) = s_{r,n}(0) = 0$. Therefore, for $n \ge 0$ and $r = 2$ we define the polynomials $\hat{c}_n(x)$ and $\hat{s}_n(x)$ by

$$ \hat{c}_n(x) \stackrel{\text{def}}{=} \frac{c_{2,n+1}(x)}{x} \qquad (6.1) $$

$$ \hat{s}_n(x) \stackrel{\text{def}}{=} \frac{s_{2,n+1}(x)}{x} \qquad (6.2) $$

We will show that the polynomials $\hat{c}_n(x)$ and $\hat{s}_n(x)$ have simple and interlacing zeros in the interval $(-1, 0)$. To prove this, we will first obtain recurrences for the polynomials $\hat{c}_n(x)$ and $\hat{s}_n(x)$ and then evaluate them at $x = 0$ and at $x = -1$.

**Lemma 6.1.**

(a) The polynomials $\hat{c}_n(x)$ satisfy the recurrence relation

$$ \hat{c}_n(x) = [(n+2)x + n + 1] \hat{c}_{n-1}(x) + x(x+1) \hat{c}'_{n-1}(x) \qquad (6.3) $$

(b) The polynomials $\hat{s}_n(x)$ satisfy the recurrence relation

$$ \hat{s}_n(x) = [(n+2)x + 1] \hat{s}_{n-1}(x) + x(x+1) \hat{s}'_{n-1}(x) \qquad (6.4) $$

**PROOF.** As a consequence of the recurrences $(1.15)/(1.16)$, the polynomials $c_{2,n}(x)$ and $s_{2,n}(x)$ satisfy the recurrences

$$ c_{2,n}(x) = [nx + (n-1)] c_{2,n-1}(x) + x(x+1) c'_{2,n-1}(x) \qquad (6.5) $$

$$ s_{2,n}(x) = nx s_{2,n-1}(x) + x(x+1) s'_{2,n-1}(x) \qquad (6.6) $$

from which the recurrences $(6.3)/(6.4)$ follow. $\square$
**Lemma 6.2.** For all $n \ge 1$, the polynomials $\hat{c}_n(x)$ and $\hat{s}_n(x)$ have the following values at $x = 0$ and at $x = -1$:

$$ \hat{c}_n(0) = (n+1)! \qquad (6.7a) $$

$$ \hat{s}_n(0) = 1 \qquad (6.7b) $$

$$ \hat{c}_n(-1) = (-1)^n \qquad (6.7c) $$

$$ \hat{s}_n(-1) = (-1)^n (n+1)! \qquad (6.7d) $$

**PROOF.** These follow by substituting $x = 0$ and $x = -1$ in the recurrences (6.3) and (6.4) and then using induction. $\square$

We are now ready to prove Theorem 1.6.

**PROOF OF THEOREM 1.6.** We prove it for the polynomial sequence $\hat{c}_{2,n}(x)$. The proof for the polynomial sequence $\hat{s}_{2,n}(x)$ is mostly the same and is left to the reader. We first rewrite equation (6.3) as

$$ \hat{c}_n(x) = x \left( (n+2)\hat{c}_{n-1}(x) + (x+1)\hat{c}'_{n-1}(x) \right) + (n+1)\hat{c}_{n-1}(x) \qquad (6.8) $$

Now, we use induction on $n$. For the case $n = 0$, the polynomial $p_0(x) = 1$ has no roots and hence the theorem is vacuously true. The case $n = 1$ can be checked to be true as well. Let us assume that the zeros of $\hat{c}_{n-1}(x)$ are distinct and are contained in the interval $(-1, 0).

Now let $p_n(x) \stackrel{\text{def}}{=} \text{GCD}(\hat{c}_{n-1}(x), (x+1)\hat{c}'_{n-1}(x))$. By Rolle's theorem, the zeros of $\hat{c}'_{n-1}(x)$ interlace those of $\hat{c}_{n-1}(x)$ and thus, lie in the interval $(-1, 0)$ and are simple. Thus we get $p_n(x) = 1$. Thus, there are no common zeros between $\hat{c}_{n-1}(x)$, $\hat{c}'_{n-1}(x)$ and $\hat{c}_n(x)$.

Now let $-1 < \lambda_{n-1}^{(n-1)} < \dots < \lambda_1^{(n-1)} < 0$ be the zeros of $\hat{c}_{n-1}(x)$. We then have $\hat{c}'_{n-1}(\lambda_j^{(n-1)}) > 0$ if $j$ is odd, and $\hat{c}'_{n-1}(\lambda_j^{(n-1)}) < 0$ if $j$ is even. Hence,

$$ \operatorname{sgn}(\hat{c}_n(\lambda_j^{(n-1)})) = (-1)^j. \qquad (6.9) $$

Furthermore, using Lemma 6.2, we also have $\hat{c}_n(-1) = (-1)^n$ and $\hat{c}_n(0) = (n+1)!$. Thus, the proof of this theorem follows by using the intermediate value theorem. $\square$

Let us finally conclude this section by mentioning that even though we have included a proof of Theorem 1.6 for the sake of completeness, one can obtain this result as an immediate consequence of a seminal result due to Liu and Wang [34].

# 7 Location of zeros for order $r \ge 3$

In this section we study the zeros of the $r$th-order Stirling cycle and subset polynomials for $r \ge 3$.
## 7.1 Existence of nonreal roots for $r \ge 3$

Conjectures 1.3(c) and 1.4(c) assert that, for $r \ge 3$, the $r$th-order Stirling cycle and subset polynomials are not negative-real-rooted. In this subsection we will prove this conjecture for the cycle case for all $r \ge 3$, and for the subset case for all $r \ge 4$. The subset case with $r = 3$ remains open.

We already know that $c_{r,n}(0) = s_{r,n}(0) = 0$ for $n \ge 1$. One sufficient condition to show that a polynomial $p(x)$ has non-real complex zeros is to show that the polynomial $\frac{d^m}{dx^m}p(x)$ for some $m \le \deg(p)$ has non-real complex zeros. In this section, we will show that the polynomials $\frac{d^{n-3}}{dx^{n-3}}(c_{r,n}(x)/x)$ and $\frac{d^{n-3}}{dx^{n-3}}(s_{r,n}(x)/x)$, which are quadratic polynomials, have a negative discriminant when $r, n \ge 3$ in the cycle case and $r \ge 4$, $n \ge 3$ in the subset case. This will prove that in these cases the polynomials $c_{r,n}(x)$ and $s_{r,n}(x)$ must have some complex non-real zeros. We will then provide plots for the distribution of these zeros which suggest that these zeros accumulate around some mysterious limiting curves.

We first notice that

$$ \frac{d^{n-3}}{dx^{n-3}}(c_{r,n}(x)/x) = \frac{(n-1)!}{2} \begin{bmatrix} n \end{bmatrix}^{(r)} x^2 + (n-2)! \begin{bmatrix} n-1 \end{bmatrix}^{(r)} x + (n-3)! \begin{bmatrix} n-2 \end{bmatrix} \quad (7.1) $$

We have already seen in (1.10) that $\begin{bmatrix} n \end{bmatrix}^{(r)} = (rn)/(r^nn!)$. We now obtain the following exact expressions either by using the combinatorial descriptions or by the recurrences (1.13):

$$ \begin{bmatrix} n \\ n-1 \end{bmatrix}^{(r)} = \frac{(r(n-1)+1)!}{(r+1)r^{n-2}(n-2)!} \quad (7.2a) $$

$$ \begin{bmatrix} n \\ n-2 \end{bmatrix}^{(r)} = \frac{(r(n-2)+2)!(r(r+2)(n-1)+2)}{2(r+1)^2(r+2)r^{n-3}(n-3)!} \quad (7.2b) $$

With this information, we prove the following proposition:

**Proposition 7.1.** Let $D_r(n)$ be the discriminant of the quadratic polynomial $\frac{d^{n-3}}{dx^{n-3}}(c_{r,n}(x)/x)$. For all $r, n \ge 3$, we have $D_r(n) < 0$.
PROOF. From (7.1), we write out the exact expression for $D_r(n)$, which is

$$ D_n(r) = \left( (n-2)! \begin{bmatrix} n \\ n-1 \end{bmatrix}^{(r)} \right)^2 - 2(n-1)!(n-3)! \begin{bmatrix} n \\ n \end{bmatrix}^{(r)} \begin{bmatrix} n \\ n-2 \end{bmatrix}^{(r)} \quad (7.3a) \\ = \frac{(r(n-1)+1)!^2}{(r+1)^2 r^{2n-4}} \quad (7.3b) $$

$$ - \frac{(rn)!(r(n-2)+2)!(r+2)r(n-1)+2)}{n(r+2)(r+1)^2 r^{2n-3}} \quad (7.3b) $$

$$ = \frac{(r(n-1)+1)!(r(n-2)+2)!}{(r+1)^2 r^{2n-4}} \cdot \left( \frac{(r(n-1)+1)!}{(r(n-2)+2)!} - \frac{((r+2)r(n-1)+2)}{n(r+2)r} \cdot \frac{(rn)!}{(r(n-1)+1)!} \right) \quad (7.3c) $$

$$ = \frac{(r(n-1)+1)!(r(n-2)+2)!}{(r+1)^2 r^{2n-4}} \cdot \left( \begin{aligned} & (rn - (r-1))(rn - (r-1) - 1) \cdots (rn - 2(r-1) + 1) \\ & - \frac{((r+2)r(n-1)+2)}{n(r+2)r} \cdot (rn)(rn-1) \cdots (rn - (r-1) + 1) \end{aligned} \right) \quad (7.3d) $$

Notice that when $r, n \ge 3$, we have

$$ \begin{aligned} & (rn - (r-1))(rn - (r-1) - 1) - \frac{((r+2)r(n-1)+2)}{n(r+2)r} \cdot (rn)(rn-1) \\ & = \frac{-n(r^3 - 2r) + (r^3 - 4r + 2)}{r+2} < 0. \quad (7.4a) \end{aligned} $$

It is easy to compare the remaining terms and it follows that $D_r(n) < 0$ for $r, n \ge 3$. $\square$

**Corollary 7.2.** For $r, n \ge 3$, the polynomial $c_{r,n}(x)$ has some nonreal zeros.

One can use a similar argument to show that the discriminant of the quadratic polynomial $\frac{d^{n-3}}{dx^{n-3}}(s_{r,n}(x)/x)$ is negative when $r \ge 4$ and $n \ge 3$; we leave the details to the reader. This implies:

**Corollary 7.3.** For $r \ge 4$ and $n \ge 3$, the polynomial $s_{r,n}(x)$ has some nonreal zeros.

For $r = 3$, computational evidence suggests that the zeros of $\frac{d^{n-3}}{dx^{n-3}}(s_{3,n}(x)/x)$ are real, but that the polynomials $s_{3,n}(x)$ nevertheless have some non-real complex zeros for $n \ge 4$.

Let us first establish some notation before we provide the plots for the zeros of the polynomials $c_{r,n}(x)$ and $s_{r,n}(x)$. Let $\mathcal{A} \subset \mathbb{C}$ be a subset of complex numbers, let $\alpha \in \mathbb{R}$ be a real number. We then define the set $\alpha\mathcal{A}$ as follows:

$$ \alpha \mathcal{A} \stackrel{\text{def}}{=} \{ \alpha x : x \in \mathcal{A} \}. \quad (7.5) $$
For a fixed $r \ge 1$, we let $\mathcal{RC}_{r,n}$ and $\mathcal{RS}_{r,n}$ denote the set of zeros of the $r$th-order Stirling cycle polynomial $c_{r,n}(x)$, and of the $r$th-order Stirling subset polynomial $s_{r,n}(x)$, respectively:

$$ \mathcal{RC}_{r,n} \stackrel{\text{def}}{=} \{z \in \mathbb{C} : c_{r,n}(z) = 0\} \qquad (7.6a) $$

$$ \mathcal{RS}_{r,n} \stackrel{\text{def}}{=} \{z \in \mathbb{C} : s_{r,n}(z) = 0\}. \qquad (7.6b) $$

In Sections 7.2 and 7.3, we provide normalised plots of $\mathcal{RC}_{r,n}$ and $\mathcal{RS}_{r,n}$, respectively, for $3 \le r \le 10$. These plots will immediately suggest some problems and conjectures which we mention.

## 7.2 Stirling cycle polynomials of order $r \ge 3$

We fix $r$ and plot the set $n^{r-2}\mathcal{RC}_{r,n}$ for $n = 50, 100, 150, 200$ using the different colors red, green, blue and black, respectively. The overlapping plots suggest that the zeros have some asymptotic distribution supported on some limiting curves. We plot the cases $r = 3, 4, 5, 6$ in Figure 2 and $r = 7, 8, 9, 10$ in Figure 3.

Our plots suggest the following problem:

**Problem 7.4.** For a fixed $r \ge 1$, study the asymptotic distribution of the set of normalised zeros $n^{r-2}\mathcal{RC}_{r,n}$. Do they accumulate on a curve? If so, what curve?

In the case $r = 1$, we clearly get that the normalised zeros accumulate uniformly on the unit interval $[-1, 0]$.

When $r = 3$, we conjecture the following:

**Conjecture 7.5.** The zeros of the third-order Stirling cycle polynomials $c_{3,n}(x)$ lie on the left-half plane.
<figure><img src="image_4.png" /><figcaption>(a) $r = 3$-rd order Stirling cycle</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) $r = 4$-th order Stirling cycle</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(c) $r = 5$-th order Stirling cycle</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(d) $r = 6$-th order Stirling cycle</figcaption></figure>

Figure 2: We plot $n^{r-2}\mathcal{RC}_{r,n}$ with $r = 3, 4, 5, 6$ in subfigures (a), (b), (c) and (d), respectively, and with $n = 50, 100, 150, 200$ using the different colors red, green, blue and black, respectively.
<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /><figcaption>Figure 3: We plot $n^{r-2}RC_{r,n}$ with $r = 7, 8, 9, 10$ in subfigures (a), (b), (c) and (d), respectively, and with $n = 50, 100, 150, 200$ using the different colors red, green, blue and black, respectively.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>(a) $r$ = 3-rd order Stirling subset</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(c) $r$ = 5-th order Stirling subset</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(d) $r$ = 6-th order Stirling subset</figcaption></figure>

Figure 4: We plot $n^{r-2}\mathcal{RS}_{r,n}$ with $r = 3, 4, 5, 6$ in subfigures (a), (b), (c) and (d), respectively, and with $n = 50, 100, 150, 200$ using the different colors red, green, blue and black, respectively.

## 7.3 Stirling subset polynomials of order $r \ge 3$

We fix $r$ and plot the set $n^{r-2}\mathcal{RS}_{r,n}$ for $n = 50, 100, 150, 200$ using the different colors red, green, blue and black, respectively. The overlapping plots suggest that the zeros have some asymptotic distribution supported on some limiting curves. We plot the cases $r = 3, 4, 5, 6$ in Figure 4 and $r = 7, 8, 9, 10$ in Figure 5.

Our plots suggest the following problem:

**Problem 7.6.** For a fixed $r \ge 1$, study the asymptotic distribution of the set of normalised zeros $n^{r-2}\mathcal{RS}_{r,n}$. Do they accumulate on a curve? If so, what curve?

In the case $r = 1$, the asymptotic distribution of the normalised zeros of the Bell
<figure><img src="image_15.png" /><figcaption>Figure 5: We plot $n^{r-2}RS_{r,n}$ with $r = 7, 8, 9, 10$ in subfigures (a), (b), (c) and (d), respectively, and with $n = 50, 100, 150, 200$ using the different colors red, green, blue and black, respectively.</figcaption></figure>

polynomials — which lie on the negative real axis — was studied by Elbert [21, 22]. When $r=3$, we conjecture the following:

**Conjecture 7.7.** The zeros of the third-order Stirling subset polynomials $s_{3,n}(x)$ lie on the left-half plane.

## Acknowledgements

We thank David Callan, Alex Dyachenko and Markus Kuba for helpful correspondence. The content in Section 3.2 is due to David Callan. Alex Dyachenko carried out the numerical tests of Conjecture 1.7.

The first author was supported by DIMERS project ANR-18-CE40-0033 funded by Agence Nationale de la Recherche (ANR, France). He is currently supported by the Tsinghua University Shuimu scholarship.
# A Tables of higher-order Stirling cycle and subset numbers

In this Appendix we provide tables of the *r*th-order Stirling cycle and subset numbers for $1 \le r \le 4$ and the first few values of *n*.

## A.1 Higher-order Stirling cycle numbers

<table><thead><tr><th colspan="9">r = 1 (ordinary Stirling cycle numbers)</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>2</th><td>0</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>2</td></tr><tr><th>3</th><td>0</td><td>2</td><td>3</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td>6</td></tr><tr><th>4</th><td>0</td><td>6</td><td>11</td><td>6</td><td>1</td><td></td><td></td><td></td><td></td><td>24</td></tr><tr><th>5</th><td>0</td><td>24</td><td>50</td><td>35</td><td>10</td><td>1</td><td></td><td></td><td></td><td>120</td></tr><tr><th>6</th><td>0</td><td>120</td><td>274</td><td>225</td><td>85</td><td>15</td><td>1</td><td></td><td></td><td>720</td></tr><tr><th>7</th><td>0</td><td>720</td><td>1764</td><td>1624</td><td>735</td><td>175</td><td>21</td><td>1</td><td></td><td>5040</td></tr><tr><th>8</th><td>0</td><td>5040</td><td>13068</td><td>13132</td><td>6769</td><td>1960</td><td>322</td><td>28</td><td>1</td><td>40320</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 2</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>2</th><td>0</td><td>2</td><td>3</td><td></td><td></td><td></td><td></td><td></td><td></td><td>5</td></tr><tr><th>3</th><td>0</td><td>6</td><td>20</td><td>15</td><td></td><td></td><td></td><td></td><td></td><td>41</td></tr><tr><th>4</th><td>0</td><td>24</td><td>130</td><td>210</td><td>105</td><td></td><td></td><td></td><td></td><td>469</td></tr><tr><th>5</th><td>0</td><td>120</td><td>924</td><td>2380</td><td>2520</td><td>945</td><td></td><td></td><td></td><td>6889</td></tr><tr><th>6</th><td>0</td><td>720</td><td>7308</td><td>26432</td><td>44100</td><td>34650</td><td>10395</td><td></td><td></td><td>123605</td></tr><tr><th>7</th><td>0</td><td>5040</td><td>64224</td><td>303660</td><td>705320</td><td>866250</td><td>540540</td><td>135135</td><td></td><td>2620169</td></tr><tr><th>8</th><td>0</td><td>40320</td><td>623376</td><td>3678840</td><td>11098780</td><td>18858840</td><td>18288270</td><td>9459450</td><td>2027025</td><td>64074901</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 3</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td>2</td></tr><tr><th>2</th><td>0</td><td>6</td><td>40</td><td></td><td></td><td></td><td></td><td></td><td>46</td></tr><tr><th>3</th><td>0</td><td>24</td><td>420</td><td>2240</td><td></td><td></td><td></td><td></td><td>2684</td></tr><tr><th>4</th><td>0</td><td>120</td><td>3948</td><td>50400</td><td>246400</td><td></td><td></td><td></td><td>300868</td></tr><tr><th>5</th><td>0</td><td>720</td><td>38304</td><td>859320</td><td>9609600</td><td>44844800</td><td></td><td></td><td>55352744</td></tr><tr><th>6</th><td>0</td><td>5040</td><td>396576</td><td>13665960</td><td>258978720</td><td>2690688000</td><td>12197785600</td><td></td><td>15161519896</td></tr><tr><th>7</th><td>0</td><td>40320</td><td>4419360</td><td>216339552</td><td>6112906800</td><td>105205900800</td><td>1042910668800</td><td>4635158528000</td><td>5789608803632</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 4</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>6</td><td></td><td></td><td></td><td></td><td></td><td>6</td></tr><tr><th>2</th><td>0</td><td>24</td><td>1260</td><td></td><td></td><td></td><td></td><td>1284</td></tr><tr><th>3</th><td>0</td><td>120</td><td>18144</td><td>1247400</td><td></td><td></td><td></td><td>1265664</td></tr><tr><th>4</th><td>0</td><td>720</td><td>223776</td><td>38918880</td><td>3405402000</td><td></td><td></td><td>3444545376</td></tr><tr><th>5</th><td>0</td><td>5040</td><td>2756160</td><td>889945056</td><td>185253868800</td><td>19799007228000</td><td></td><td>19985153803056</td></tr><tr><th>6</th><td>0</td><td>40320</td><td>35307360</td><td>18478684224</td><td>6780291598080</td><td>1663116607152000</td><td>210384250804728000</td><td>212054166217509984</td></tr></tbody></table>
## A.2 Higher-order Stirling subset numbers

<table><thead><tr><th colspan="9">r = 1 (ordinary Stirling subset numbers)</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>2</th><td>0</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>2</td></tr><tr><th>3</th><td>0</td><td>1</td><td>3</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td>5</td></tr><tr><th>4</th><td>0</td><td>1</td><td>7</td><td>6</td><td>1</td><td></td><td></td><td></td><td></td><td>15</td></tr><tr><th>5</th><td>0</td><td>1</td><td>15</td><td>25</td><td>10</td><td>1</td><td></td><td></td><td></td><td>52</td></tr><tr><th>6</th><td>0</td><td>1</td><td>31</td><td>90</td><td>65</td><td>15</td><td>1</td><td></td><td></td><td>203</td></tr><tr><th>7</th><td>0</td><td>1</td><td>63</td><td>301</td><td>350</td><td>140</td><td>21</td><td>1</td><td></td><td>877</td></tr><tr><th>8</th><td>0</td><td>1</td><td>127</td><td>966</td><td>1701</td><td>1050</td><td>266</td><td>28</td><td>1</td><td>4140</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 2 (Ward numbers)</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>2</th><td>0</td><td>1</td><td>3</td><td></td><td></td><td></td><td></td><td></td><td></td><td>4</td></tr><tr><th>3</th><td>0</td><td>1</td><td>10</td><td>15</td><td></td><td></td><td></td><td></td><td></td><td>26</td></tr><tr><th>4</th><td>0</td><td>1</td><td>25</td><td>105</td><td>105</td><td></td><td></td><td></td><td></td><td>236</td></tr><tr><th>5</th><td>0</td><td>1</td><td>56</td><td>490</td><td>1260</td><td>945</td><td></td><td></td><td></td><td>2752</td></tr><tr><th>6</th><td>0</td><td>1</td><td>119</td><td>1918</td><td>9450</td><td>17325</td><td>10395</td><td></td><td></td><td>39208</td></tr><tr><th>7</th><td>0</td><td>1</td><td>246</td><td>6825</td><td>56980</td><td>190575</td><td>270270</td><td>135135</td><td></td><td>660032</td></tr><tr><th>8</th><td>0</td><td>1</td><td>501</td><td>22935</td><td>302995</td><td>1636635</td><td>4099095</td><td>4729725</td><td>2027025</td><td>12818912</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 3</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>2</th><td>0</td><td>1</td><td>10</td><td></td><td></td><td></td><td></td><td></td><td></td><td>11</td></tr><tr><th>3</th><td>0</td><td>1</td><td>35</td><td>280</td><td></td><td></td><td></td><td></td><td></td><td>316</td></tr><tr><th>4</th><td>0</td><td>1</td><td>91</td><td>2100</td><td>15400</td><td></td><td></td><td></td><td></td><td>17592</td></tr><tr><th>5</th><td>0</td><td>1</td><td>210</td><td>10395</td><td>200200</td><td>1401400</td><td></td><td></td><td></td><td>1612206</td></tr><tr><th>6</th><td>0</td><td>1</td><td>456</td><td>42735</td><td>1611610</td><td>28028000</td><td>190590400</td><td></td><td></td><td>220273202</td></tr><tr><th>7</th><td>0</td><td>1</td><td>957</td><td>158301</td><td>10335325</td><td>333533200</td><td>5431826400</td><td>36212176000</td><td></td><td>41988030184</td></tr><tr><th>8</th><td>0</td><td>1</td><td>1969</td><td>549549</td><td>57962905</td><td>3073270200</td><td>89625135600</td><td>1394168776000</td><td>9161680528000</td><td>10648606224224</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 4</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>Row sums</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>1</th><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><th>2</th><td>0</td><td>1</td><td>35</td><td></td><td></td><td></td><td></td><td></td><td>36</td></tr><tr><th>3</th><td>0</td><td>1</td><td>126</td><td>5775</td><td></td><td></td><td></td><td></td><td>5902</td></tr><tr><th>4</th><td>0</td><td>1</td><td>336</td><td>45045</td><td>2627625</td><td></td><td></td><td></td><td>2673007</td></tr><tr><th>5</th><td>0</td><td>1</td><td>792</td><td>231231</td><td>35735700</td><td>2546168625</td><td></td><td></td><td>2582136349</td></tr><tr><th>6</th><td>0</td><td>1</td><td>1749</td><td>981981</td><td>300179880</td><td>53469541125</td><td>4509264634875</td><td></td><td>4563035339611</td></tr><tr><th>7</th><td>0</td><td>1</td><td>3718</td><td>3741738</td><td>2002016016</td><td>666586946025</td><td>135277939046250</td><td>13189599057009375</td><td>13325545588763123</td></tr></tbody></table>
# B Tables of higher-order quasi-Eulerian cycle and subset numbers

In this Appendix we provide tables of the *r*th-order quasi-Eulerian cycle and subset numbers for $1 \le r \le 5$ and the first few values of *n*.

## B.1 Higher-order quasi-Eulerian cycle numbers

<table><thead><tr><th rowspan="2">n \ k</th><th colspan="9">r = 1</th><th rowspan="2">Row sums</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>1</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>2</td><td>0</td><td>1</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>3</td><td>0</td><td>-1</td><td>2</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>4</td><td>0</td><td>2</td><td>-7</td><td>6</td><td>0</td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>5</td><td>0</td><td>-6</td><td>29</td><td>-46</td><td>24</td><td>0</td><td></td><td></td><td></td><td>1</td></tr><tr><td>6</td><td>0</td><td>24</td><td>-146</td><td>329</td><td>-326</td><td>120</td><td>0</td><td></td><td></td><td>1</td></tr><tr><td>7</td><td>0</td><td>-120</td><td>874</td><td>-2521</td><td>3604</td><td>-2556</td><td>720</td><td>0</td><td></td><td>1</td></tr><tr><td>8</td><td>0</td><td>720</td><td>-6084</td><td>21244</td><td>-39271</td><td>40564</td><td>-22212</td><td>5040</td><td>0</td><td>1</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">n \ k</th><th colspan="9">r = 2 (second-order Eulerian numbers)</th><th rowspan="2">Row sums</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>2</td><td>1</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>3</td></tr><tr><td>3</td><td>1</td><td>8</td><td>6</td><td></td><td></td><td></td><td></td><td></td><td></td><td>15</td></tr><tr><td>4</td><td>1</td><td>22</td><td>58</td><td>24</td><td></td><td></td><td></td><td></td><td></td><td>105</td></tr><tr><td>5</td><td>1</td><td>52</td><td>328</td><td>444</td><td>120</td><td></td><td></td><td></td><td></td><td>945</td></tr><tr><td>6</td><td>1</td><td>114</td><td>1452</td><td>4400</td><td>3708</td><td>720</td><td></td><td></td><td></td><td>10395</td></tr><tr><td>7</td><td>1</td><td>240</td><td>5610</td><td>32120</td><td>58140</td><td>33984</td><td>5040</td><td></td><td></td><td>135135</td></tr><tr><td>8</td><td>1</td><td>494</td><td>19950</td><td>195800</td><td>644020</td><td>785304</td><td>341136</td><td>40320</td><td></td><td>2027025</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">n \ k</th><th colspan="8">r = 3</th><th rowspan="2">Row sums</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>2</td></tr><tr><td>2</td><td>34</td><td>6</td><td></td><td></td><td></td><td></td><td></td><td></td><td>40</td></tr><tr><td>3</td><td>1844</td><td>372</td><td>24</td><td></td><td></td><td></td><td></td><td></td><td>2240</td></tr><tr><td>4</td><td>199828</td><td>42864</td><td>3588</td><td>120</td><td></td><td></td><td></td><td></td><td>246400</td></tr><tr><td>5</td><td>36056936</td><td>8002992</td><td>748728</td><td>35424</td><td>720</td><td></td><td></td><td></td><td>44844800</td></tr><tr><td>6</td><td>9752801896</td><td>2212167336</td><td>220309896</td><td>12130056</td><td>371376</td><td>5040</td><td></td><td></td><td>12197785600</td></tr><tr><td>7</td><td>3691552813712</td><td>849994084272</td><td>88121628912</td><td>5290935792</td><td>194847552</td><td>4177440</td><td>40320</td><td></td><td>4635158528000</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">n \ k</th><th colspan="7">r = 4</th><th rowspan="2">Row sums</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>6</td><td></td><td></td><td></td><td></td><td></td><td></td><td>6</td></tr><tr><td>2</td><td>1236</td><td>24</td><td></td><td></td><td></td><td></td><td></td><td>1260</td></tr><tr><td>3</td><td>1229376</td><td>17904</td><td>120</td><td></td><td></td><td></td><td></td><td>1247400</td></tr><tr><td>4</td><td>3366706176</td><td>38473488</td><td>221616</td><td>720</td><td></td><td></td><td></td><td>3405402000</td></tr><tr><td>5</td><td>19614640553136</td><td>183482227008</td><td>881706816</td><td>2736000</td><td>5040</td><td></td><td></td><td>19799007228000</td></tr><tr><td>6</td><td>208727896045756896</td><td>1649611318980672</td><td>6725066986368</td><td>18337857984</td><td>35105760</td><td>40320</td><td></td><td>210384250804728000</td></tr></tbody></table>
<table><thead><tr><th colspan="7">r = 5</th><th rowspan="2">Row sums</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>24</td><td></td><td></td><td></td><td></td><td></td><td>24</td></tr><tr><td>2</td><td>72456</td><td>120</td><td></td><td></td><td></td><td></td><td>72576</td></tr><tr><td>3</td><td>1742235984</td><td>1329120</td><td>720</td><td></td><td></td><td></td><td>1743565824</td></tr><tr><td>4</td><td>162123744912336</td><td>69701970960</td><td>20323440</td><td>5040</td><td></td><td></td><td>162193467211776</td></tr><tr><td>5</td><td>41351875243477668864</td><td>11349535075620480</td><td>2003358856320</td><td>303776640</td><td>40320</td><td></td><td>41363226782215962624</td></tr></tbody></table>

## B.2 Higher-order quasi-Eulerian subset numbers

<table><thead><tr><th colspan="9">r = 1</th><th rowspan="2">Row sums</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>1</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>2</td><td>0</td><td>1</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>3</td><td>-1</td><td>1</td><td>1</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>4</td><td>1</td><td>-5</td><td>4</td><td>1</td><td>0</td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>5</td><td>2</td><td>1</td><td>-14</td><td>11</td><td>1</td><td>0</td><td></td><td></td><td></td><td>1</td></tr><tr><td>6</td><td>-9</td><td>36</td><td>-29</td><td>-24</td><td>26</td><td>1</td><td>0</td><td></td><td></td><td>1</td></tr><tr><td>7</td><td>9</td><td>-104</td><td>281</td><td>-244</td><td>1</td><td>57</td><td>1</td><td>0</td><td></td><td>1</td></tr><tr><td>8</td><td>50</td><td>-83</td><td>-454</td><td>1401</td><td>-1259</td><td>225</td><td>120</td><td>1</td><td>0</td><td>1</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 2 (reversed second-order Eulerian numbers)</th><th rowspan="2">Row sums</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>2</td><td>2</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>3</td></tr><tr><td>3</td><td>6</td><td>8</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>15</td></tr><tr><td>4</td><td>24</td><td>58</td><td>22</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td>105</td></tr><tr><td>5</td><td>120</td><td>444</td><td>328</td><td>52</td><td>1</td><td></td><td></td><td></td><td></td><td>945</td></tr><tr><td>6</td><td>720</td><td>3708</td><td>4400</td><td>1452</td><td>114</td><td>1</td><td></td><td></td><td></td><td>10395</td></tr><tr><td>7</td><td>5040</td><td>33984</td><td>58140</td><td>32120</td><td>5610</td><td>240</td><td>1</td><td></td><td></td><td>135135</td></tr><tr><td>8</td><td>40320</td><td>341136</td><td>785304</td><td>644020</td><td>195800</td><td>19950</td><td>494</td><td>1</td><td></td><td>2027025</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 3</th><th rowspan="2">Row sums</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>2</td><td>9</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>10</td></tr><tr><td>3</td><td>246</td><td>33</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>280</td></tr><tr><td>4</td><td>13390</td><td>1921</td><td>88</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td>15400</td></tr><tr><td>5</td><td>1211386</td><td>180036</td><td>9771</td><td>206</td><td>1</td><td></td><td></td><td></td><td></td><td>1401400</td></tr><tr><td>6</td><td>164131730</td><td>24931166</td><td>1486131</td><td>40921</td><td>451</td><td>1</td><td></td><td></td><td></td><td>190590400</td></tr><tr><td>7</td><td>31103704820</td><td>4795137550</td><td>303467476</td><td>9711671</td><td>153531</td><td>951</td><td>1</td><td></td><td></td><td>36212176000</td></tr><tr><td>8</td><td>7854121032724</td><td>1223909199718</td><td>80747636454</td><td>2846874725</td><td>55244660</td><td>537756</td><td>1962</td><td>1</td><td></td><td>9161680528000</td></tr></tbody></table>

<table><thead><tr><th colspan="9">r = 4</th><th rowspan="2">Row sums</th></tr><tr><th>n \ k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td></tr><tr><td>2</td><td>34</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>35</td></tr><tr><td>3</td><td>5650</td><td>124</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td>5775</td></tr><tr><td>4</td><td>2582915</td><td>44376</td><td>333</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td>2627625</td></tr><tr><td>5</td><td>2510663365</td><td>35275610</td><td>228861</td><td>788</td><td>1</td><td></td><td></td><td></td><td></td><td>2546168625</td></tr><tr><td>6</td><td>4456094293397</td><td>52872120317</td><td>297244421</td><td>974995</td><td>1744</td><td>1</td><td></td><td></td><td></td><td>4509264634875</td></tr><tr><td>7</td><td>13054985706631155</td><td>133950756253880</td><td>660603311240</td><td>1987086224</td><td>3723163</td><td>3712</td><td>1</td><td></td><td></td><td>13189599057009375</td></tr></tbody></table>
<table><thead><tr><th rowspan="2">n \ k</th><th colspan="7">r = 5</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>0</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>125</td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>125665</td><td>460</td><td>1</td><td></td><td></td><td></td><td></td></tr><tr><th>4</th><td>487856621</td><td>1006503</td><td>1251</td><td>1</td><td></td><td></td><td></td></tr><tr><th>5</th><td>5187834064414</td><td>6833491661</td><td>5300301</td><td>2999</td><td>1</td><td></td><td></td></tr><tr><th>6</th><td>123266182967274060</td><td>112433009305765</td><td>59083404656</td><td>23048178</td><td>6716</td><td>1</td><td></td></tr></tbody><tfoot><tr><td colspan="8">Row sums</td></tr></tfoot></table>

# C Report on systematic verification of conjectures

We will now report the results of our systematic experiments, i.e., we will write out up to which order we have verified each of our conjectures.

Our total positivity tests were performed by using the following methods:

* For a finite matrix $A$ with real entries, an efficient method to test total positivity is by computing the bidiagonal factorization using Neville elimination [27]. We used this technique to test the total positivity of lower-triangular matrices.

* For checking negative-real-rootedness of polynomials, we used MATHEMATICA's built-in NSolve command to list out approximate values of the zeros. This method is very efficient.

* For checking coefficientwise Hankel-total positivity of a sequence of polynomials, we unfortunately have to compute and check all minors of the Hankel matrix. No other efficient method is known. Compared to the other two types of tests, this method is very slow and we can check this only for matrices of small sizes.

We now present the reports for Conjectures 1.3, 1.4, 1.8, 1.9, and 4.17.

## Conjecture 1.3:

The order up to which the various conjectures in Conjecture 1.3 have been verified is recorded in Table 1. We have checked that $\tilde{C}^{(r)}$ is not totally positive for $r \ge 3$. For $r = 3$, the $6 \times 6$ top left submatrix fails to be totally positive. For $r \ge 4$, we in fact have a $2 \times 2$ minor which is negative; it is

$$ \begin{bmatrix} 2 \\ 2 \end{bmatrix}^{(r)} \begin{bmatrix} 3 \\ 2 \end{bmatrix}^{(r)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix}^{(r)} \begin{bmatrix} 3 \\ 3 \end{bmatrix}^{(r)} . \qquad (C.1) $$

## Conjecture 1.4:

The order up to which the various conjectures in Conjecture 1.4 have been verified is recorded in Table 2. We have checked that $\tilde{S}^{(r)}$ is not totally positive for $r \ge 3$. For $r = 3$, the $13 \times 13$ top left submatrix fails to be totally positive. For $r \ge 4$, we in fact have a $2 \times 2$ minor which is negative; it is

$$ \left\{ \begin{smallmatrix} 2 \\ 2 \end{smallmatrix} \right\}^{(r)} \left\{ \begin{smallmatrix} 3 \\ 2 \end{smallmatrix} \right\}^{(r)} - \left\{ \begin{smallmatrix} 2 \\ 1 \end{smallmatrix} \right\}^{(r)} \left\{ \begin{smallmatrix} 3 \\ 3 \end{smallmatrix} \right\}^{(r)} . \qquad (C.2) $$

For $r \ge 3$, the Hankel matrices $(s_{r,n+k}(x))_{n,k \ge 0}$ fail to be coefficientwise totally positive. In fact, it seems that for $r \ge 3$, the $3 \times 3$ minor $|(s_{r,n+k}(x))_{1 \le n \le 3, 0 \le k \le 2}|$ is has some negative coefficients.
<table><caption>Table 1: Systematic report for verification of Conjecture 1.3.</caption><thead><tr><th>Conjecture</th><th>r</th><th>Order up to which verified</th></tr></thead><tbody><tr><td>(a) Total positivity of C<sup>(r)</sup></td><td>r = 2, ..., 10</td><td>70 × 70</td></tr><tr><td>(b) Total positivity of C̃<sup>(r)</sup></td><td>r = 2</td><td>90 × 90</td></tr><tr><td>(c) Log-concavity of coefficients of c<sub>r,n</sub>(x)</td><td>r = 3, 4, 5</td><td>1000</td></tr><tr><td>(d) Coefficientwise Hankel-total positivity of (c<sub>r,n</sub>(x))<sub>n≥0</sub></td><td>r = 3, ..., 7<br>r = 8, 9, 10</td><td>11 × 11<br>10 × 10</td></tr></tbody></table>

<table><caption>Table 2: Systematic report for verification of Conjecture 1.4.</caption><thead><tr><th>Conjecture</th><th>r</th><th>Order up to which verified</th></tr></thead><tbody><tr><td>(a) Total positivity of S<sup>(r)</sup></td><td>r = 2, ..., 10</td><td>70 × 70</td></tr><tr><td>(b) Total positivity of S̃<sup>(r)</sup></td><td>r = 2</td><td>70 × 70</td></tr><tr><td>(c) Log-concavity of coefficients of s<sub>r,n</sub>(x)</td><td>r = 3, 4, 5</td><td>1000</td></tr></tbody></table>

<table><caption>Table 3: Systematic report for verification of Conjecture 4.17.</caption><thead><tr><th>Conjecture</th><th>Order up to which verified</th></tr></thead><tbody><tr><td>(a) Total positivity of D</td><td>100 × 100</td></tr><tr><td>(b) Total positivity of D<sup>rev</sup></td><td>80 × 80</td></tr><tr><td>(c) Coefficientwise Hankel-total positivity of (d<sub>n</sub>(x))<sub>n≥0</sub></td><td>10 × 10</td></tr></tbody></table>

**Conjectures 1.8 and 1.9:**

Conjectures 1.8(b) and (b') have been tested for $r = 2, ..., 10$ for the $50 \times 50$ leading principal submatrix. Conjecture 1.9 has been tested for $r = 3, ..., 10$ for the $9 \times 9$ leading principal submatrix.

**Conjecture 4.17:**

The order up to which the various conjectures in Conjecture 4.17 have been verified is recorded in Table 3.

**References**

[1] F.T. Adams-Watters, [seqfan] Re: Definitions of “circular rooted trees,” “series-reduced mobiles,” “cycle rooted trees,” “asymmetric mobiles”, The Sequence Fanatics Archives, 18 September 2011, http://list.seqfan.eu/pipermail/seqfan/2011-September/059758.html

[2] M. Aigner and G.M. Ziegler, *Proofs from THE BOOK*, 6th ed. (Springer-Verlag, Berlin–Heidelberg, 2018).
[3] M. Aissen, I. J. Schoenberg, and A. M. Whitney, On the generating functions of totally positive sequences I, J. d'Analyse Math. **2** 93–103 (1952).

[4] J.F. Barbero G., J. Salas and E.J.S. Villaseñor, Generalized Stirling permutations and forests: higher-order Eulerian and Ward numbers, Electron. J. Combin. **22**, no. 3, paper 3.37 (2015).

[5] F. Bergeron, P. Flajolet and B. Salvy, Varieties of increasing trees, in *CAAP '92*, edited by J.-C. Raoult, Lecture Notes in Computer Science #581 (Springer-Verlag, Berlin, 1992), pp. 24–48.

[6] M. Bóna, Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley, SIAM J. Discrete Math. **23**, 401–406 (2009).

[7] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. **81**, no. 413 (1989).

[8] F. Brenti, Combinatorics and total positivity, J. Combin. Theory A **71**, 175–218 (1995).

[9] F. Brenti, The applications of total positivity to combinatorics, and conversely, in *Total Positivity and its Applications*, edited by M. Gasca and C.A. Micchelli (Kluwer, Dordrecht, 1996), pp. 451–473.

[10] D. Callan, A combinatorial survey of identities for the double factorial, preprint (2009), arXiv:0906.1317 [math.CO] at arXiv.org.

[11] D. Callan, private communication (November 2019).

[12] P. Cameron, Problems from BCC30, preprint (2024), arxiv:2409.07216 [math.CO] at arXiv.org.

[13] L. Carlitz, Note on the numbers of Jordan and Ward, Duke Math. J. **38**, 783–790 (1971).

[14] X. Chen, B. Deb, A. Dyachenko, T. Gilmore and A.D. Sokal, Coefficient-wise total positivity of some matrices defined by linear recurrences, Séminaire Lotharingien de Combinatoire **85B**, article #30 (2021).

[15] L. Clark, Asymptotic normality of the Ward numbers, Discrete Math. **203**, 41–48 (1999).

[16] L. Comtet, *Advanced Combinatorics: The Art of Finite and Infinite Expansions*, translated from the French by J.W. Nienhuys (Reidel, Dordrecht-Boston, 1974). [French original: *Analyse Combinatoire*, tomes I et II, Presses Universitaires de France, Paris, 1970.]

[17] B. Deb, A. Dyachenko and A.D. Sokal, Total positivity beyond production matrices: Experiments on the generic Lah polynomials, in preparation.

[18] A. Dyachenko, private communication.
[19] A. Dzhumadil’daev and D. Yeliussizov, Stirling permutations on multisets, European J. Combin. **36**, 377–392 (2014).

[20] A. Edrei, On the generating functions of totally positive sequences II, J. d'Analyse Math. **2**, 104–109 (1952).

[21] C. Elbert, Strong asymptotics of the generating polynomials of the Stirling numbers of the second kind, J. Approx. Theory **109**, 198–217 (2001).

[22] C. Elbert, Weak asymptotics for the generating polynomials of the Stirling numbers of the second kind, J. Approx. Theory **109**, 218–228 (2001).

[23] A. Elvey Price and A.D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, Electron. J. Comb. **27**, P4.6 (2020).

[24] L. Euler, De seriebus divergentibus, Novi Commentarii Academiae Scientiarum Petropolitanae **5**, 205–237 (1760); reprinted in *Opera Omnia*, ser. 1, vol. 14, pp. 585–617. [Latin original and English and German translations available at http://eulerarchive.maa.org/pages/E247.html]

[25] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. **32**, 125–161 (1980).

[26] G. Frobenius, Über die Bernoullischen Zahlen und die Eulerschen Polynome, Sitzungsber. Preuss. Akad. Wiss., 809–847 (1910).

[27] M. Gasca and J.M. Peña, Total positivity and Neville elimination, Linear Algebra Appl. **165**, 25–44 (1992).

[28] I. Gessel and R.P. Stanley, Stirling polynomials, J. Combin. Theory A **24**, 24–33 (1978).

[29] R.L. Graham, D.E. Knuth and O. Patashnik, *Concrete Mathematics: A Foundation for Computer Science*, 2nd ed. (Addison-Wesley, Reading, Mass., 1994).

[30] L.H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. **38**, 410–414 (1967).

[31] S. Janson, Plane recursive trees, Stirling permutations and an urn model, Fifth Colloquium on Mathematics and Computer Science, Discrete Math. Theor. Comput. Sci. Proc., AI (2008), pp. 541–547.

[32] S. Janson, M. Kuba and A. Panholzer, Generalized Stirling permutations, families of increasing trees and urn models, J. Combin. Theory A **118**, 94–114 (2011).

[33] S. Karlin, *Total Positivity* (Stanford University Press, Stanford CA, 1968).

[34] L.L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, Add. App. Math., **38**, 542–560 (2007).
[35] The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org

[36] S.-K. Park, The r-multipermutations, J. Combin. Theory A 67, 44-71 (1994).

[37] M. Pétréolle and A.D. Sokal, Lattice paths and branched continued fractions, II: Multivariate Lah polynomials and Lah symmetric functions, European J. Combin. 92, 103235 (2021).

[38] M. Pétréolle, A.D. Sokal and B.-X. Zhu, Lattice paths and branched continued fractions: An infinite sequence of generalizations of the Stieltjes-Rogers and Thron-Rogers polynomials, with coefficientwise Hankel-total positivity, Mem. Amer. Math. Soc. 291, no. 1450 (2023).

[39] J. Salas and A.D. Sokal, The Graham-Knuth-Patashnik recurrence: Symmetries and continued fractions, Electron. J. Combin. 28(2), #P2.18 (2021).

[40] L.M. Smiley, Completion of a rational function sequence of Carlitz, arXiv:math/0006106 [math.CO].

[41] A.D. Sokal, Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials, talk at the Séminaire de Combinatoire Philippe Flajolet, Institut Henri Poincaré, Paris, 5 June 2014; transparency available at http://semflajolet.math.cnrs.fr/index.php/Main/2013-2014

[42] A.D. Sokal, A simple algorithm for expanding a power series as a continued fraction, Expositiones Math. 41, 245-287 (2023).

[43] A.D. Sokal and J. Zeng, Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions, Adv. Appl. Math. 138, 102341 (2022).

[44] R.P. Stanley, *Enumerative Combinatorics*, vol. 1, 2nd ed. (Cambridge University Press, Cambridge-New York, 2012).

[45] T.J. Stieltjes, Recherches sur les fractions continues, Ann. Fac. Sci. Toulouse 8, J1-J122 (1894) and 9, A1-A47 (1895). [Reprinted, together with an English translation, in T.J. Stieltjes, *Œuvres Complètes/Collected Papers* (Springer-Verlag, Berlin, 1993), vol. II, pp. 401-566 and 609-745.]

[46] G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Notes de conférences données à l'Université du Québec à Montréal, septembre-octobre 1983. Available on-line at http://www.xavierviennot.org/xavier/polynomes_orthogonaux.html

[47] M. Ward, The representation of Stirling's numbers and Stirling's polynomials as sums of factorials, Amer. J. Math. 56, 87-95 (1934).