Boolean-Narayana numbers

Imagine you are building a family tree, but with a few special rules. This paper introduces a new way to count these trees and discovers some beautiful mathematical patterns hidden inside them.

Here is the story of the paper, broken down into simple concepts:

1. The Characters: The "0-1" Trees

First, let's meet the main characters: 0-1 trees.

The Base: Imagine a standard family tree where every person (node) can have one or two children. If they have two, one is the "left" child and one is the "right" child. Mathematicians already know how to count these standard trees; they are called Catalan numbers.
The Twist: In this paper, the author adds a special rule. If a person in the tree has two children, they must wear a badge that says either "0" or "1". If they only have one child, they wear no badge.
The Count: The total number of these special trees is called a Boolean-Catalan number. Think of it as a "super-count" because for every tree with two children, you have two choices (0 or 1), making the numbers grow faster than the standard ones.

2. The New Metric: Counting "Right Turns"

The author wants to look at these trees in more detail. Instead of just counting the total trees, they want to sort them based on how many right edges (connections to the right child) they have.

This creates a new set of numbers called Boolean-Narayana numbers.
Analogy: Imagine you have a pile of 100 different family trees. You want to sort them into bins. Bin 1 holds trees with 0 right turns, Bin 2 holds trees with 1 right turn, Bin 3 holds trees with 2 right turns, and so on. The number of trees in each bin is a Boolean-Narayana number.

3. The "Stack Sorting" Connection

The paper also connects these trees to a game involving permutations (shuffling a deck of cards).

There is a specific way to sort a shuffled deck of cards using a "stack" (like a stack of plates where you can only add or remove from the top).
The author shows that if you look at all the ways you can shuffle a deck of cards such that a specific sorting algorithm works perfectly, you get a group of shuffles.
The Magic Link: The number of these special shuffles that have a certain number of "drops" (where a card is lower than the one before it) matches exactly the number of 0-1 trees with a certain number of right turns. It's like two different languages describing the exact same pattern.

4. The Shape of the Numbers: The "Mountain"

The author investigates the shape of the numbers in the bins (the sequence of Boolean-Narayana numbers).

Unimodality (The Mountain): They prove that if you list the number of trees for 0 right turns, 1 right turn, 2 right turns, etc., the numbers go up, reach a peak in the middle, and then go down. It looks like a mountain.
The Proof: They built a clever "injection" (a one-way door). They showed that for any tree with fewer right turns, you can transform it into a tree with one more right turn without losing any trees. This proves there are always at least as many trees in the next bin as the current one, until you hit the middle of the mountain.

5. The "Real Roots" Secret

The author then turned these numbers into a polynomial equation (a math formula with variables).

The Discovery: They proved that all the "roots" (the solutions that make the equation equal zero) of this formula are real numbers.
Why it matters: In the world of math, if a sequence of numbers comes from a formula with only real roots, it guarantees two things:
1. The sequence is log-concave (a fancy way of saying the numbers don't wiggle up and down randomly; they rise smoothly and fall smoothly).
2. The "mountain" shape is very stable and predictable.

6. The "Family Recipe" (Recurrence)

Finally, the author found a "recipe" to calculate these numbers.

Instead of building every tree from scratch, you can take the numbers from the previous step and the step before that, mix them together with a specific formula, and get the new numbers.
This is like a family recipe where the taste of the new dish depends on the two dishes made before it. This recipe confirms the "interlacing" property, meaning the peaks and valleys of the number sequences for different tree sizes fit together perfectly, like the teeth of two combs sliding into each other.

Summary

In short, this paper introduces a new way to count special family trees with "0" and "1" badges. It proves that these numbers form a perfect, smooth mountain shape, connects them to card-shuffling games, and shows that the math behind them is incredibly stable and orderly. The author essentially found a new, more complex version of a famous mathematical pattern (the Narayana numbers) and showed that it behaves just as beautifully as the original.

Technical Summary of "Boolean-Narayana Numbers" by Miklós Bóna

Problem Statement and Context
The paper introduces a refinement of the Boolean-Catalan numbers, termed Boolean-Narayana numbers, denoted as $BoNa(n, k)$. These numbers count a specific class of combinatorial objects: 0-1 trees. A 0-1 tree is defined as a binary plane tree on $n$ unlabeled vertices where every vertex with two children is labeled either 0 or 1. The parameter $k$ corresponds to the number of right edges in the tree (specifically, $BoNa(n, k)$ counts trees with $k-1$ right edges).

The author positions this work as an extension of the relationship between binary plane trees and Catalan numbers. While standard binary plane trees are counted by Catalan numbers $C_n$ , and 0-1 trees are counted by Boolean-Catalan numbers $B(n)$ , this paper seeks to apply the refinement logic of Narayana numbers (which count binary trees by right edges) to the 0-1 tree setting. The explicit formula for standard Narayana numbers is well-known and compact; the paper notes that the resulting formula for Boolean-Narayana numbers is less compact, yet the sequence shares the same desirable analytic properties.

Methodology
The paper employs a combination of combinatorial constructions, generating function analysis, and algebraic techniques:

Combinatorial Interpretations: The author establishes bijections between 0-1 trees and specific sets of permutations related to stack sorting. Specifically, $BoNa(n, k)$ is shown to count permutations in the preimage of the stack-sorting map $s^{-1}$ that avoid the patterns $\{231, 312\}$ (or $\{132, 312\}$ ) and possess exactly $k-1$ descents. This relies on recursive decompositions of permutations and trees.
Lagrange Inversion Formula: To derive an explicit formula, the author constructs a bivariate generating function $T(z, u)$ for the 0-1 trees. By setting up a functional equation $T = z(1 + uT + T + 2uT^2)$ , the paper applies the Lagrange Inversion Formula to extract coefficients, yielding a summation formula for $BoNa(n, k)$.
Combinatorial Injection for Unimodality: To prove unimodality, the author constructs an explicit injection $z: BoNa(n, k) \to BoNa(n, k+1)$ for $k \le (n-1)/2$ . This map utilizes an involution $f$ that swaps left and right subtrees for vertices with a single child, applied to a specific subforest determined by a total ordering of nodes.
Real-Roots and Recurrence Analysis: The generating polynomials $BoNan(u) = \sum BoNa(n, k)u^k$ are analyzed using their relationship to standard Narayana polynomials $N_n(q)$ . By expressing $BoNan(u)$ in terms of $N_n(q(u))$ where $q(u)$ is a specific rational function, the author leverages known properties of Narayana polynomials (real roots, interlacing) to deduce properties of the Boolean-Narayana polynomials. Additionally, a three-term recurrence relation is derived by transforming the known recurrence for Narayana polynomials.

Key Contributions and Results

Explicit Formula: The paper provides the following explicit formula for $BoNa(n, k)$ (assuming $k \le (n+1)/2$ due to symmetry):
$BoNa(n, k) = \frac{1}{n} \binom{n}{k-1} \sum_{j=0}^{k-1} 2^j \binom{k-1}{j} \binom{n-k+1}{j+1}$
Unimodality: It is proven that for a fixed $n$ , the sequence $BoNa(n, 1), \dots, BoNa(n, n)$ is unimodal. This is established via the combinatorial injection described above.
Log-Concavity and Real Roots: The generating polynomials $BoNan(u)$ are proven to have real roots only. Consequently, the sequence of coefficients is log-concave (referred to as "horizontally log-concave").
Interlacing Property: The nonzero roots of $BoNan(u)$ and $BoNan-1(u)$ are shown to weakly interlace. This is proven both via the transformation to Narayana polynomials and alternatively via a three-term recurrence relation combined with a theorem by Liu and Wang regarding polynomial sequences.
Vertical Log-Concavity: For a fixed $k$ , the infinite sequence $BoNa(n, k)$ (where $n \ge k+1$ ) is proven to be log-concave ("vertically log-concave"). This is achieved by rewriting the explicit formula as a binomial transform of a log-concave sequence and applying a known lemma on binomial transforms.
Recurrence Relation: A three-term recurrence for the polynomials $BoNan(u)$ is derived:
$(n+1) BoNan(u) = (2n-1)(1+u) BoNan-1(u) - (n-2)(u^2 - 6u + 1) BoNan-2(u)$

Significance and Claims
The paper claims that the Boolean-Narayana numbers share the "best-known properties" of the classical Narayana numbers, specifically unimodality, log-concavity, and the real-root property of their generating polynomials.

The author notes that while the explicit formula for Boolean-Narayana numbers is not as compact as the classical Narayana formula $N(n, k) = \frac{1}{n}\binom{n}{k-1}\binom{n}{k}$ , the structural similarities are significant. The work bridges the gap between the enumeration of standard binary trees (Catalan) and 0-1 trees (Boolean-Catalan) by introducing a parameter (right edges) that behaves analogously to the standard Narayana refinement.

The paper concludes by suggesting future directions, specifically the search for other natural classes of trees that bijectively correspond to permutations such that the number of right edges in the tree corresponds to the number of descents in the permutation, thereby extending the current framework. The author acknowledges Per Alexandersson for pointing out the three-term recurrence relation used in the proof.