Boolean–Eulerian numbers
Miklós Bóna, and, Vincent Vatter · 2026
Read Boolean–Eulerian numbers by Miklós Bóna, and, Vincent Vatter (2026) 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-2605-15415.txt.
Introduction
Miklós Bóna and Vincent Vatter study decreasing binary trees where two-child vertices are colored red or blue. One bijection, to ordered set partitions into odd-sized blocks arranged as alternating permutations, gives an exponential generating function. It equals one over one minus tangent. A second bijection, to nonplane decreasing 1-2 trees with binary labels, proves the count equals two to the n minus one times the nth Euler number. Refining by right edges yields Boolean-Eulerian polynomials, with gamma-positivity and real-rootedness carried over from Eulerian polynomials.
Catalog record
| CREATOR | Miklós Bóna, and, Vincent Vatter |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30735 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.15415
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Boolean–Eulerian numbers Miklós Bóna, and, Vincent Vatter Abstract We study decreasing binary trees in which every vertex with two children is colored red or blue. We construct two bijections. The first, to ordered set partitions into odd-sized blocks each arranged as an alternating permutation, shows that the exponential generating function of these trees is 1 / ( 1 − tan z ) 1/(1-\tan z) . The second, to nonplane decreasing 1 1 - 2 2 trees paired with a binary label on each non-root vertex, proves combinatorially that the count equals 2 n − 1 2^{n-1} times the n n th Euler number. Refining by the number of right edges yields the Boolean–Eulerian polynomials, which are an explicit algebraic transform of the classical Eulerian polynomials. The Foata–Strehl orbit decomposition, recast in the decreasing-binary-tree model, gives a direct combinatorial proof of gamma-positivity, and the algebraic transform carries real-rootedness and interlacing of zeros from the Eulerian polynomials to the Boolean–Eulerian polynomials. \newpagestyle main[ ] \headrule \sethead [ \usepage ][][] Boolean–Eulerian numbers \usepage 1. Introduction We write [n] for the set \{1,2,\ldots,n\} and S_{n} for the set of permutations of [n] . A descent of a permutation p=p_{1}\cdots p_{n} is an index i with 1\leq i\leq n-1 and p_{i}>p_{i+1} ; a peak is an index i with 2\leq i\leq n-1 and p_{i-1}<p_{i}>p_{i+1} . We write \des(p) and \pk(p) for the number of descents and peaks of p . Euler has numbers attached to both of these statistics, and both appear in this paper, so we take a moment to distinguish them. The Eulerian numbers count permutations of [n] by their number of descents, and arise as the coefficients of the Eulerian polynomial A_{n}(x)=\sum_{p\in S_{n}}x^{\des(p)} . The Euler number E_{n} , by contrast, counts alternating permutations, meaning permutations p=p_{1}\cdots p_{n} with p_{1}<p_{2}>p_{3}<\cdots ; equivalently, permutations of [n] in which every even index is a peak. A decreasing binary tree on [n] is a rooted tree on the vertex set [n] in which every vertex has a larger label than its children, every vertex has at most two children, and every child is designated left or right even when it is an only child. These trees are in bijection with permutations of [n] : send p=p_{1}\cdots p_{n} to the tree T(p) whose root is labeled n , with the entries to the left and right of n in p forming the left and right subtrees recursively, and recover p by reading T(p) in-order. Under this bijection, right edges of T(p) correspond to descents of p , and vertices with two children correspond to peaks. See Figure 1 for an example. {forest} Figure 1: The permutation p=1653724 and its decreasing binary tree T(p) . The peaks of p are at positions 2 and 5 , with values 6 and 7 ; these correspond to the shaded vertices of T(p) , namely the vertices with two children. The descents of p are at positions 2,3,5 , corresponding to the right edges of T(p) . Binary plane trees on n unlabeled vertices are counted by the Catalan numbers, and refining by the number of right edges gives the Narayana numbers. In [ 2 , 1 ] , the first author studied binary plane trees in which every vertex with two children receives an additional label from \{0,1\} , calling these 0 - 1 -trees , and refined the count by the number of right edges. The resulting Boolean–Catalan and Boolean–Narayana numbers share many nice enumerative properties with the Catalan and Narayana numbers: symmetry, unimodality, log-concavity, real-rootedness, and interlacing. In this paper, we carry out the labeled analogue of this investigation. A bicolored decreasing binary tree on [n] is a decreasing binary tree on [n] in which every vertex with two children is additionally colored red or blue. If a permutation p has m peaks, then T(p) has m vertices with two children, each of which can be colored in two ways, so the total number of bicolored decreasing binary trees on [n] is H_{n}=\sum_{p\in S_{n}}2^{\pk(p)}. Refining by right edges, we define the Boolean–Eulerian number \mathrm{BoEl}(n,k) to be the number of bicolored decreasing binary trees on [n] with precisely k-1 right edges, and we write B_{n}(u)=\sum_{k=1}^{n}\mathrm{BoEl}(n,k)\,u^{k-1}=\sum_{p\in S_{n}}2^{\pk(p)}\,u^{\des(p)} for the Boolean–Eulerian polynomial . Our first results concern the total count H_{n} . In Section 2 , we show that the exponential generating function of H_{n} is 1/(1-\tan z) , and we construct a bijection between bicolored decreasing binary trees on [n] and ordered set partitions of [n] into blocks of odd size, each block arranged as an alternating permutation. In Section 3 , we construct a second bijection, to pairs consisting of a nonplane decreasing 1 - 2 tree on [n] and a binary label on each non-root vertex. Since nonplane decreasing 1 - 2 trees on [n] are counted by the Euler number E_{n} , this proves combinatorially that H_{n}=2^{n-1}E_{n} for n\geq 1 , and hence that \frac{1}{1-\tan z}=\frac{1+\sec 2z+\tan 2z}{2}. The remaining sections concern the Boolean–Eulerian polynomials. In Section 4 , we derive a bivariate differential equation for their exponential generating function. The key structural result, in Section 5 , is that B_{n}(u) is an explicit algebraic transform of the classical Eulerian polynomial A_{n}(u) : specifically, B_{n}(u)=g(u)^{n-1}\,A_{n}(q(u)) for explicit algebraic functions g and q , where q restricts to an increasing bijection from (-\infty,0) to itself. The known properties of the Eulerian polynomials therefore transfer to the Boolean–Eulerian polynomials; in particular, we show that B_{n}(u) is gamma-positive, real-rooted, and that the family \{B_{n}(u)\}_{n\geq 2} has interlacing zeros. For gamma-positivity we give a combinatorial proof, via a tree version of the Foata–Strehl orbit decomposition. Finally, in Section 6 , we give a combinatorial proof of unimodality by importing an injection from [ 1 ] that extends without modification to the labeled setting. 2. Total enumeration Write H_{n} for the number of bicolored decreasing binary trees on [n] , with H_{0}=1 , and let H(z)=\sum_{n\geq 0}H_{n}z^{n}/n! be the associated exponential generating function. Proposition 2.1 . The generating function H(z) satisfies H^{\prime}(z)=H(z)^{2}+(H(z)-1)^{2} , and therefore H(z)=1/(1-\tan z) . Proof. The coefficient of z^{n}/n! in H^{\prime}(z) is H_{n+1} . A bicolored decreasing binary tree on [n+1] is determined by its root (labeled n+1 ), an ordered pair of bicolored decreasing binary trees on complementary subsets of [n] forming its left and right subtrees, and (if both subtrees are nonempty) a choice of red or blue for the root. Ordered pairs of bicolored decreasing binary trees are counted by H(z)^{2} , and pairs with both subtrees nonempty are counted by (H(z)-1)^{2} , so H^{\prime}(z)=H(z)^{2}+(H(z)-1)^{2} . The differential equation together with the initial condition H(0)=1 determine the coefficients of H(z) recursively, and one checks that 1/(1-\tan z) satisfies both. ∎ The generating function for the Euler numbers of odd index is \sum_{n\text{ odd}}E_{n}z^{n}/n!=\tan z , so the expansion 1/(1-\tan z)=\sum_{m\geq 0}(\tan z)^{m} expresses H(z) as the EGF for sequences of structures each counted by \tan z . The labeled sequence construction then gives the following combinatorial interpretation. Corollary 2.2 . The number H_{n} counts ordered set partitions of [n] into blocks of odd size, each block arranged as an alternating permutation. We call these objects alternating block sequences on [n] , written C_{1}\mid