Higher-Order Stirling Triangles: the Log-Concavity Breakthrough

Higher-Order Stirling Triangles: the Log-Concavity Breakthrough
arXiv based on https://arxiv.org/abs/2610.09362

Introduction

If you’ve ever stared at those famous combinatorics “triangles” (binomial, Stirling, Eulerian) and wondered why they so often behave nicely—like being log-concave or even real-rooted—you’re in good company. New work by William Y. C. Chen and Elena L. Wang digs into a higher-order family of these arrays: the higher-order Stirling triangles, specifically the cycle and subset versions that Deb and Sokal introduced, then left unfinished.

This research (from Chen & Wang) settles two big gaps. First, it gives missing combinatorial interpretations for the subset case by inventing a new object called Stirling subset permutations and a statistic called consecutive descents. Second, it proves Deb–Sokal conjectures about row log-concavity for orders up to 5 (and extends to order 6 for sufficiently large rows).

So what’s the “main event”? The paper shows that for every row of both higher-order Stirling cycle and subset triangles, the sequence of entries in that row is log-concave for orders 1 ≤ r ≤ 5, and for the subset triangle with r = 6 it becomes log-concave starting at n ≥ 23. That’s a surprisingly strong stability phenomenon—one that matters far beyond pure aesthetics.

Why This Matters

This kind of result feels abstract, but it’s not just math-for-math’s-sake. Log-concavity is one of those “hidden order” properties that keeps showing up whenever a combinatorial model has a probabilistic interpretation. If a row is log-concave, the distribution you get from that row tends to have behavior consistent with single-peakedness and “no wild oscillations.” That’s the same kind of behavior engineers and data scientists hope to see when they approximate distributions or analyze random structures.

A concrete scenario where this could matter today: suppose you’re using combinatorial counting polynomials as surrogates for probabilities in an algorithm—maybe counting structured permutations, partitions, or constrained objects in a Monte Carlo or dynamic programming pipeline. If the coefficients come from a triangle like this, log-concavity gives you a strong “shape guarantee” without needing full distribution sampling. In other words: you can get reliable qualitative behavior from the coefficient structure alone.

And there’s another reason the timing is relevant: recent AI-assisted discovery (including tools like ChatGPT) has started speeding up the generation of candidate inequalities and the search for proof strategies. This paper explicitly reports using AI in the hunt for “strengthened log-concavity inequalities,” then proving them rigorously. That’s basically a modern workflow: compute patterns → conjecture a sharper inequality → prove it using known criteria (like Sagan’s and Dey’s). It’s exactly the kind of loop that increasingly drives progress in combinatorics and discrete math.

Stirling Triangles, But Higher: What Deb–Sokal Really Built

The classical Stirling cycle and subset triangles count permutations with certain structural features (cycles, blocks). Deb and Sokal then “lifted columns” to define higher-order versions.

The lifted higher-order definitions

For r ≥ 1, they define the higher-order Stirling cycle and subset numbers by
[
\left[!\begin{matrix} n \ k \end{matrix}!\right]^{(r)}=\left[!\begin{matrix} n+(r-1)k \ k \end{matrix}!\right]r,
\quad
\left{!\begin{matrix} n \ k \end{matrix}!\right}^{(r)}=\left{!\begin{matrix} n+(r-1)k \ k \end{matrix}!\right}r
]
and then form triangles C(r) (cycle) and S(r) (subset) from these entries. Their row generating polynomials are
- c_{r,n}(x) = Σ_k [n choose k]^{(r)} x^k
- s_{r,n}(x) = Σ_k {n choose k}^{(r)} x^k

Quasi-Eulerian triangles: what “neighboring structure” means

Deb and Sokal also define associated quasi-Eulerian triangles via binomial transforms. Intuitively, these capture a second layer of statistics—how the permutations/partitions “rise and fall” in a controlled way.

For r = 2, things match known objects: the cycle quasi-Eulerian triangle becomes the second-order Eulerian triangle, and the subset quasi-Eulerian triangle becomes a shifted reversal. For larger r, nonnegativity and combinatorial meaning were trickier—especially in the subset case.

This is where Chen and Wang step in, and it’s not just a cosmetic fix: they supply a full combinatorial interpretation that makes the subset constructions feel as natural as the cycle ones. (If you want to see the big picture of what they’re resolving, the introduction and Section 2 of the paper are the quickest path.)

The Missing Subset Story: Stirling Subset Permutations and Consecutive Descents

Deb–Sokal had a gorgeous combinatorial interpretation for the cycle case using Stirling permutations with a consecutive-ascent statistic. For the subset case, they had left open questions: you can tell there’s a structured combinatorics hiding there, but what is it exactly?

Chen–Wang’s solution is to define a new kind of object: Stirling subset permutations, plus a statistic called consecutive descents.

Step 1: Split the multiset into blocks

They start with a multiset M^{(r)}_n:
[
M^{(r)}n={1^{a1},2^{a2},\dots,((r-1)n)^{a{(r-1)n}}}
]
where the multiplicity a_i is:
- a_i = 2 if i ≡ 0 (mod r−1)
- a_i = 1 otherwise

Then they partition this multiset into n “chunks”:
- M^{(r)}_{n, i} is the block of consecutive integers from (r−1)(i−1)+1 to (r−1)i.

So you can picture M^{(r)}_n as n blocks laid end-to-end.

Step 2: Define Stirling subset permutations

A Stirling subset permutation is a Stirling permutation of M^{(r)}_n with the extra rule:

Within each block M^{(r)}_{n,i}, the elements must appear in non-increasing order from left to right.

So every block is forced to “face downward” stylistically.

That restriction is what makes the subset triangle different from the cycle triangle: it’s not just about how numbers repeat and nest; it’s also about the internal monotonic ordering inside each block.

Step 3: Count consecutive descents

The paper then defines a consecutive descent as a special pattern of length r that occurs in the permutation. It’s not any descent—it’s a descent tied to the structure of a block and to the Stirling-permutation constraints. Each descent is indexed by the block label i, and importantly:

• different consecutive descents correspond to different indices
• the statistic cdes(σ) counts how many consecutive descents a permutation has

How this counts the triangle entries

Now the punchline: for r ≥ 2, the (n,k)-entry of the subset triangle S(r) is a weighted count of these permutations.

At the core:
- The number of subset permutations with exactly k consecutive descents corresponds to \left\{\!\begin{matrix} n \\ k \end{matrix}\!\right\}^{(r)}.
- The quasi-Eulerian subset triangle counts them without the weighting, just by the number of descents.

So the subset triangle finally gets a combinatorial meaning parallel to the cycle case. This also explains why the higher-order quasi-Eulerian subset triangle entries become nonnegative for r ≥ 2: you’re literally counting (or weighted counting) permutations with a well-defined statistic.

And if you compare with the r=2 case: this construction collapses to well-known Stirling permutation interpretations of the Ward numbers. That’s a comforting consistency check.

Log-Concavity: The “Row-by-Row Stability” Property They Proved

The second half of the paper is about a different—but equally important—property: row log-concavity.

What “row log-concave” means here

Take any row of C(r) or S(r):
[
(T{n,0}, T{n,1}, \dots, T{n,n})
]
A row is log-concave if for all relevant k:
[
T{n,k}^2 \ge T{n,k-1}\,T{n,k+1}
]
This is like saying the sequence has a robust “curved peak” shape rather than alternating up/down.

The key tools: Sagan’s criterion and Dey’s extension

To prove log-concavity, the authors use criteria that let you verify inequalities via a recurrence-friendly setup.

• Sagan’s criterion: if you know a sequence is log-concave already and certain derived inequalities are nonnegative, then a new sequence formed from it is log-concave too.
• Dey’s extension: relaxes the situation, allowing a mixed inequality term to be negative as long as it’s not “too negative” (captured by a quadratic bound involving other differences).

This matters because higher-order Stirling triangles satisfy clean recurrence relations. Once you rewrite the recurrence in the right “Sagan/Dey framework,” proving log-concavity becomes an inequality verification problem.

The main theorem they prove

Here are the results from the paper (Theorem 3.1), stated plainly:

That’s a very strong “uniformity” statement for orders up to 5, and a threshold phenomenon at order 6.

How the Proof Works Across Orders: Why the Cases Split

One of the more interesting “human” aspects of the paper is that the log-concavity story changes by order. It’s not one universal inequality that works forever; the authors have to treat different r with different strategies.

Orders r=3,4: Sagan works in some cases

For r=3,4, the cycle cases and subset cases can be handled using Sagan’s criterion (or its extension) because the derived inequality terms Γ_k(c,d) land in the right sign ranges for most k.

Order r=5: the cycle case needs a stronger inequality

For the fifth-order cycle triangle (C(5)), the direct Sagan/Dey inequalities don’t cooperate smoothly. The authors instead prove a stronger log-concavity inequality by induction.

Here’s the vibe: rather than only proving C_{n,k}^2 ≥ C_{n,k-1}C_{n,k+1}, they aim for an inequality that gives them extra slack so the induction closes cleanly. The paper notes that this strengthened inequality was discovered with the assistance of ChatGPT 5.6, then justified rigorously.

Order r=6: subset case eventually becomes log-concave for large n

For S(6), the authors show log-concavity holds once n is large enough (n ≥ 23). Again, the proof uses a stronger inductive inequality, but the threshold is significant: the paper reduces it to a technical inequality valid for n ≥ 80 and then completes remaining cases (23 ≤ n ≤ 79) by computation.

So the “story arc” looks like this:

1. Use recurrence relations.
2. Convert log-concavity into inequalities between coefficients.
3. Apply Sagan/Dey where sign conditions allow.
4. For stubborn orders, strengthen the inequality (with AI assistance for the right form).
5. For r=6, prove it generically for large n, then verify the remaining finite band.

Real-Rootedness Doesn’t Save You Forever: What Fails at Higher Order

A quick but important complement: the paper also revisits a theme from Deb–Sokal—real-rootedness of row-generating polynomials.

In many classical cases, real-rootedness implies strong coefficient behavior (including log-concavity). But for higher orders, real-rootedness fails.

They confirm that for the subset triangle at order r=3, the polynomials s_{3,n}(x) are not real-rooted for n ≥ 4. The proof uses a necessary condition from Holtz–Tyaglov (via a lemma about coefficients of a monic polynomial), showing a key expression becomes negative.

This is one of those “don’t assume too much” lessons: log-concavity can still hold even when real-rootedness fails, and that’s exactly what’s happening here.

Key Takeaways

Key Takeaways

• New combinatorial object: The paper defines Stirling subset permutations on the multiset M^{(r)}_n, with a statistic of consecutive descents.
• Subset case is solved: It provides the previously missing combinatorial interpretations for higher-order Stirling subset triangles and their associated quasi-Eulerian subset triangles—paralleling the cycle-case interpretation.
• Log-concavity is robust up to r=5:
  • Every row of C(r) and S(r) is log-concave for 1 ≤ r ≤ 5.
• Order r=6 subset triangle has a threshold: For S(6), log-concavity holds for n ≥ 23.
• Real-rootedness fails at r=3 for subsets: The row polynomials s_{3,n}(x) are not real-rooted for n ≥ 4, showing log-concavity does not rely on real-rootedness in this setting.
• Modern proof workflow: The paper uses known log-concavity criteria (Sagan and Dey), plus strengthened inequalities (with AI-assisted discovery) and induction—illustrating a practical “compute → conjecture → prove” pipeline.

If you want, I can also write a follow-up that turns the consecutive-ascent vs consecutive-descent definitions into small worked examples for r=3 so you can “see” why the weighting and triangle entries come out the way they do.