Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness
Bishal Deb and Alan D. Sokal, [5mm] 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[4mm] [email protected] , [email protected] · 2025
Read Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness by Bishal Deb and Alan D. Sokal, [5mm] 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[4mm] [email protected] , [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-18959.txt.
Introduction
Bishal Deb and Alan Sokal study two new families of number triangles that generalize the classic Stirling cycle and subset triangles. Each family is indexed by a positive integer order. The paper asks four total positivity questions about these arrays, covering the triangle itself, its row reversal, and generating polynomials.
Positivity questions of this kind connect to continued fractions and whether polynomials have only real roots. The authors state several conjectures arising from the four questions across both families. They then prove some of those conjectures for the second-order case. The work sits in enumerative combinatorics, where such triangles often encode counting sequences with hidden structure.
Catalog record
| CREATOR | Bishal Deb and Alan D. Sokal, [5mm] 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[4mm] [email protected] , [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 128 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-18959
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness Bishal Deb and Alan D. Sokal, [5mm] 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[4mm] [email protected] , [email protected] 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 ≥ 1 r\geq 1 ; we call these the r 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 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). 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\geq 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^{\rm rev}\stackrel{{\scriptstyle\rm def}}{{=}}(a_{n,n-k})_{n,k\geq 0} , obtained by reversing the rows of A , totally positive? (Here a_{n,n-k}\stackrel{{\scriptstyle\rm 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? 1 1 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. This is equivalent [ 33 , pp. 395, 399] to asking if the Toeplitz matrix of the n -th row sequence (a_{n,k})_{k\geq 0} — that is, the matrix (a_{n,i-j})_{i,j\geq 0} with a_{n,k}\stackrel{{\scriptstyle\rm def}}{{=}}0 for k<0 — is totally positive. In this situation we say that the n -th row sequence (a_{n,k})_{k\geq 0} is Toeplitz-totally positive . 2 2 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] . (d) Is the Hankel matrix of the polynomial sequence (A_{n}(x))_{n\geq 0} — that is, the matrix (A_{i+j}(x))_{i,j\geq 0} — coefficientwise totally positive in the variable x ? In this situation we say that the sequence (A_{n}(x))_{n\geq 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 . 3 3 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] . 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=\left(\binom{n}{k}\right)_{n,k\geq 0} is the matrix of binomial coefficients. The binomial matrix A is well known to be totally positive, and there are many proofs of this fact: see e.g. [ 2 , pp. 232–233] for a proof using the Lindström–Gessel–Viennot lemma. Here A^{\rm 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 \big((1+x)^{n}\big)_{n\geq 0} is coefficientwise Hankel-totally positive in the variable x : this can easily be seen directly, or it follows from the continued fraction \sum\limits_{n=0}^{\infty}(1+x)^{n}\,t^{n}=1/[1-(1+x)t] . (b) When A=\left(\genfrac{[}{]}{0.0pt}{}{n}{k}\right)_{n,k\geq 0} is the matrix of Stirling cycle numbers, which count the permutations of [n]\stackrel{{\scriptstyle\rm def}}{{=}}\{1,\ldots,n\} with k cycles. The total positivity of the matrix A and its reversal A^{\rm rev} are due to Brenti [ 8 ] in 1995: they hold because the entries \genfrac{[}{]}{0.0pt}{}{n}{k} 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 \big(A_{n}(x)\big)_{n\geq 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=\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)_{n,k\geq 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 \genfrac{}{}{0.0pt}{}{n}{k} satisfy a binomial-like recurrence with nonnegative k -dependent coefficients. However, the total positivity of the reversal A^{\rm 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 \big(A_{n}(x)\big)_{n\geq 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=\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)_{n,k\geq 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 \big(A_{n}(x)\big)_{n\geq 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. 4 4 4 Dyachenko [ 18 ] has verified this conjecture for the leading 512\times 512 submatrix of the matrix \left(\genfrac{}{}{0.0pt}{}{n+1}{k}\right)_{n,k\geq 0} , by computing the bidiagonal factorization using Neville elimination [ 27 ] . Here the rows of A are almost-palindromic in the sense