Combinatorial Proof of the Two-Thirds Leaf Limit

Definitions and mathematical statement

A finite rooted plane tree is a finite rooted tree together with a linear order on the children of each vertex. Write $V(T)$ for its vertex set and define its set of leaves by \[ L(T)=\{v\in V(T):v\text{ has no children}\}. \] The supplied statement describes a family $\mathcal T_n$ of labelled rooted plane trees by the phrase "whose child labels decrease." It does not specify the label set, the meaning of the parameter $n$, or whether decrease concerns parent--child comparisons, the order of siblings, or another condition. Thus the intended family cannot be uniquely defined from this record.

Once these missing conventions specify a finite nonempty family $\mathcal T_n$ for each positive integer $n$, choose $T$ uniformly from $\mathcal T_n$, and, conditional on $T$, choose $v$ uniformly from $V(T)$. The probability in the supplied question is then \[ p_n=\Pr\left(v\in L(T)\right) =\frac{1}{|\mathcal T_n|}\sum_{T\in\mathcal T_n}\frac{|L(T)|}{|V(T)|}. \] Requested proof challenge. For the intended family, find a simple, direct combinatorial proof, using neither generating functions nor induction, that \[ \lim_{n\to\infty}p_n=\frac23. \] This is a conditional transcription of the intended challenge, not an assertion that the limit holds for every possible interpretation of the family. The supplied curation describes the leaf proportion and its limit as established and the restricted proof challenge as unresolved; those assessments have not been independently verified here.

Short English statement

Choose a tree uniformly from the intended family, then choose one of its vertices uniformly. Find a simple combinatorial proof, without generating functions or induction, that the probability of choosing a leaf tends to $2/3$. The label rule and size parameter need clarification before the family, and hence the claim, is fully determined.

Sources

• Supplied local problem-registry record: permanent UnsolvedMath ID $30002545$, source problem code catalogue entry, title "Combinatorial Proof of the Two-Thirds Leaf Limit," in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2014 and identifies no individual proposer.
• Supplied report citation: Enumerative Combinatorics (2014), Oberwolfach Reports, pp. 635--720, DOI 10.4171/owr/2014/12. https://doi.org/10.4171/owr/2014/12. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Original Oberwolfach report, as linked in the supplied literature sources: https://ems.press/content/serial-article-files/46502?nt=1.
• Bóna--Pittel (2023), as labelled in the supplied literature sources: https://doi.org/10.1002/rsa.21138.
• Bóna--Pittel preprint, as labelled in the supplied literature sources: https://arxiv.org/abs/2108.04989.
• Literature assessment checked on 2026-08-21: the supplied curation labels the problem open, states that the leaf proportion and its limit are established, and describes the simple combinatorial proof challenge without generating functions or induction as unresolved. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. Time-sensitive status and cited claims require independent verification.