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. 



Average number of distinguished leaves in a binary tree
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.


