5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Does full mean that each non leaf has 2 children? Also, does an automorphism have to fix the root node? $\endgroup$ Mar 11, 2014 at 15:30
  • $\begingroup$ @TheMaskedAvenger Yes, full means nodes have 0 or 2 children. In particular, an automorphism fixes the root node because it is the only node of degree 2 (or 0 in the case of a single vertex). $\endgroup$
    – Olivier
    Mar 11, 2014 at 15:33
  • $\begingroup$ Then one should investigate a recurrence for the average number a_k. In particular, a_n should involve a weighted sum of terms like (w_k*w_{n-k})(a_k + a_{n-k}), with the tricky bit being when n=2k. The w_k are equal or in proportion to the kth Catalan number(s). $\endgroup$ Mar 11, 2014 at 15:43

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ There are some off by 1 errors here. The first few polynomials should be $D_1 = t$, $D_2 = 1$, $D_3 = 2t$, $D_4 = 1+4 t^2$. But running your recursion, I get $D_1 = D_0^2 = t^2$ and $D_2 = 2 D_0 D_1 + (D_1(1) - D_1(t^2)) = 2 t^3 + 1 - t^4$. $\endgroup$ Mar 11, 2014 at 17:47
  • $\begingroup$ I think the correct equation is $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))$, with the recursion starting at $D_1(t) = t$. $\endgroup$ Mar 11, 2014 at 17:51
  • 2
    $\begingroup$ No, the index $n$ counts internal vertices, the number of leaves is one more. $\endgroup$ Mar 11, 2014 at 18:16
  • 1
    $\begingroup$ Oh, I see. You have the correct recursion with $n$ equal to internal vertices, and I have the correct recursion when $n$ is leaves. $\endgroup$ Mar 11, 2014 at 18:37
  • $\begingroup$ Merci beaucoup, Roland. $\endgroup$
    – Olivier
    Mar 12, 2014 at 9:03
4
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot. Not only is the math beautiful but Roland's answer and yours do cast an interesting light on the motivating linguistic problem. $\endgroup$
    – Olivier
    Mar 12, 2014 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.