Average number of distinguished leaves in a binary tree

Question

By a binary tree, I mean in this question a full rooted binary tree in which left and right child are labeled. A leaf of such a tree is a vertex of degree at most 1 (most references would probably consider that a leaf is a vertex of degree exactly 1) and an internal vertex is a vertex of degree at least 2. With these conventions, there are $C_n=\frac{1}{n+1}$${2n}\choose {n}$ binary trees with $n\in\mathbb N$ internal vertices (and $n+1$ leaves). We say that a leaf $x$ of a binary tree $T$ is distinguished if $\sigma(x)$ is equal to $x$ for all graph automorphism $\sigma\in\operatorname{Aut}(T)$.

For instance, the unique binary trees with 0 internal vertex has 1 distinguished leaf, the unique binary tree with 1 internal vertex has no distinguished leaves, the 2 binary trees with 2 internal vertices have each 1 distinguished leaf, the 5 binary trees with 3 internal vertices have on average $2/5$ distinguished leaves and the 14 binary trees with 4 internal vertices have on average $15/7$ distinguished leaves. Among these 14 binary trees, 8 have 3 distinguished leaves and 6 have a unique distinguished leaf.

Is there a known formula or an asymptotic expansion of the number of distinguished leaves as $n$ goes to $+\infty$? Is there a way to estimate the proportion of binary trees with $n+1$ leaves having at most (or equivalently, at least) $d$ distinguished leaves?

The motivation behind this question, and its perhaps surprising tags, comes from syntax. A possible formalization of the syntax of natural languages (commonly associated with the names of N.Chomsky and R.Kayne) is to assume that sentences are built by recursive applications of a binary operation operating on a set containing (but not limited to) lexical items. The process yields a binary tree as output with some leaves attached to lexical items which is then believed to be transformed into a linear string of morphemes. It is believed that in order for such a tree to be linearized, it has to satisfy a condition which is close (though actually not equivalent) to the condition of having lexical items only at distinguished leaves. One of the aims of the question is to get an idea of the relative size of the hypothesized underlying binary tree compared to the size of the sentence measured in the usual way.

Answer 1

A generating function approach gives an exact formula (extracting asymptotics is slightly more tedious): Let $d_{n,k}$ denote the number of binary trees with $n$ interior leaves and $k$ distinguished vertices. We consider the polynomials $D_n=\sum_{k=0}^{n+1}d_{n,k}t^k\in\mathbb N[t]$. We have $D_0=t$ and the recursion formula $$D_{n+1}(t)=\sum_{k=0}^n D_k(t)D_{n-k}(t)+\mod(n,2)\left((D_{n/2}(1))-(D_{n/2}(t^2))\right)$$ where $\mod(n,2)\in\{0,1\}$ is $1$ for even $n$ and $0$ otherwise. (Explanation: The left and right subtree above the root are either non-isomorphic and their distinguished leaves remain distinguished or they are isomorphic and all their leaves become non-distinguished. The last case happens only for an odd number $2n+1$ of interior leaves and this case is handled by the $\mod(n,2)$ correction.)

The polynomials $D_n$ are odd for $n$ even and even for $n$ odd and have seemingly all zeroes on the imaginary axis.

We have of course $D_n(1)={2n\choose n}/(n+1)$ and $E_n=\frac{D_n'(1)}{D_n(1)}$ gives the mean number of distinguished leaves. The quotients $E_n/n$ converges to $\sim .495$. Asymptotically, slightly less than half the leaves are distinguished in a large binary random tree.

Here a (not completely rigorous) proof of convergency for $E_n/n$: The main contribution to $E_n$ comes from fairly unbalanced trees having relatively few vertices on one of the two subtrees (issued from the root-vertex). This is due to the asymptotics $c_n=\lambda 4^n/n^{3/2}$. This has a smoothing effect on the behaviour of $E_n/n$ (the logarithmically small relative contribution of the more irregular small subtree is asymptotically identical and is thus also regularized). The correction can be neglected since it gets exponentially small.

Answer 2

Start with the corrected version of Roland's formula. (Actually, I now think both he and I had correct formulas, it is just that my $n$ is the number of leaves and his is the number of internal vertices. But I worked this out with mine, so I'm not rewriting it.)

$$D_n(t) = \sum_{k=1}^{n-1} D_k(t) D_{n-k}(t) + [ n \equiv 0 \bmod 2 ] (D_{n/2}(1) - D_{n/2}(t^2)) \quad D_1=t.$$ The selection of $D_0$ is arbitrary as it never enters the recursion.

Put $$F(x,t) = \sum_{n=1}^{\infty} D_n(t) x^n.$$ Then $$F(x,t) = t x + F(x,t)^2 + F(x^2,1) - F(x^2, t^2).$$ Also, we know that $F(x,1)$ is the Catalan generating function $C(x) := (1-\sqrt{1-4x})/2$. Writing primes for derivative with respect to $t$, we have $$F'(x,1) = x + 2 F'(x,1) F(x,1) - 2 F'(x^2,1).$$

Putting $G(x) = F'(x,1)$, we have $$G(x) = x + 2 G(x) C(x) - 2 G(x^2)$$ or $$G(x) = \frac{x - 2 G(x^2) }{1-2 C(x)}= \frac{x-2G(x^2)}{\sqrt{1-4x}}.$$ Plugging this formula into itself, $$G(x) = \frac{x}{\sqrt{1-4x}}- \frac{2 x^2}{\sqrt{(1-4x)(1-4 x^2)}} + \frac{4 x^4}{\sqrt{(1-4x)(1-4x^2)(1-4 x^4)}} - \cdots.$$

As $x \to 1/4^{-}$, the product $G(x) \sqrt{1-4x}$ approaches $$\frac{1}{4} - \frac{2}{4^2 \sqrt{1-4/4^2}} + \frac{4}{4^4 \sqrt{(1-4/4^2)(1-4/4^4)}} - \frac{8}{4^8 \sqrt{(1-4/4^2)(1-4/4^4)(1-4/4^8)}} + \cdots$$ Call this sum $\beta$. I doubt that it has a closed form, but it converges very rapidly to $\approx 0.1238$. In fact, the sum is alternating, so we can bound it between consecutive partial sums: going to $3$ and $4$ terms gives $0.123847$ and $0.123776$ if I didn't make any error keying it in.

So $$G(x) \approx \frac{\beta}{\sqrt{1-4x}} \ \mbox{as} \ x \to 1/4^{-}.$$

Meanwhile, $$x \frac{dC}{dx} = \frac{x}{\sqrt{1-4x}} \approx \frac{1/4}{\sqrt{1-4x}} \ \mbox{as} \ x \to 1/4^{-}.$$

You want to compute the ratio of the coefficient of $x^n$ in $G(x)$ and in $x \frac{d C}{d x}$. This suggests (and methods from books such as Wilf's Generatingfunctionology should be able to make this rigorous) that the limit is $4 \beta$.