# Average number of distinguished leaves in a binary tree

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. - Does full mean that each non leaf has 2 children? Also, does an automorphism have to fix the root node? – The Masked Avenger Mar 11 at 15:30 @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). – Olivier Mar 11 at 15:33 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). – The Masked Avenger Mar 11 at 15:43 ## 2 Answers 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. - 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. – David Speyer Mar 11 at 17:47 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. – David Speyer Mar 11 at 17:51 No, the index n counts internal vertices, the number of leaves is one more. – Roland Bacher Mar 11 at 18:16 Oh, I see. You have the correct recursion with n equal to internal vertices, and I have the correct recursion when n is leaves. – David Speyer Mar 11 at 18:37 Merci beaucoup, Roland. – Olivier Mar 12 at 9:03 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\$.

-
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. –  Olivier Mar 12 at 9:02