The number of trees half of whose vertices are leaves and asymptotic enumeration of plane real algebraic curves. (Q1427013)

The purpose of this paper is provide an upper bound for the number \(I_d\) of real regular algebraic curve types of degree \(d\). The basic obvervation is that every connected component of such a curve is homeomorphic to a circle so that the ``inclusion structure'' of these circles can be encoded by an unlabeled rooted tree. Since the number of connected components is less or equal to \((d-1)(d-2)/2+2\) it follows that \(I_d \leq T_{d^2/2+O(d)}\), where \(T_n\) denotes the number of unlabeled rooted trees of size \(n\) that encode an algebraic curve. Obviously one has \(T_n\leq t_n\), where \(t_n\) denotes the number of all unlabeled rooted trees of size \(n\). By a theorem of Otter it follows that \(t_n \sim c n^{-3/2} C^n\), where \(C = 2.95576\cdots\). Consequently \(T_n \leq c n^{-3/2} C^n\). The main objective of this paper is to improve this bound to \(T_n \ll C_1^n\), where \(C_1 = 2.9193800\ldots < C\). By use of Arnold inequalities the authors deduce that the number of leaves of trees that represent an algebraic curve structure is (more or less) half the number of nodes. Let \(a_{n,m}\) denote the number of unlabeled rooted trees of size \(n\) with \(m\) leaves. Then one gets an upper bound for \(T_n\) by \(T_n \leq \sum_{m\geq n/2} a_{n,m} \sim c_1 n^{-3/2} C_1^n\). The proof of the last asymptotic relation relies on analyticity properties of the generating function \(T(x,z) = \sum_{n,m\geq 0} a_{n,m} x^n z^m\) that satisfies the functional equation \[ T(x,z) = x(z-1) + x\exp\left( \sum_{k\geq 1} \frac{T(x^k,z^k)}{k} \right) \] that is due to \textit{R. W. Robinson} and \textit{A. J. Schwenk} [Discrete Math. 12, 359--372 (1975; Zbl 0308.05102)]. The derivation of the asymptotic relation for \(\sum_{m\geq n/2} a_{n,m}\) is in fact the main part of the paper. It should be, however, mentioned that this part can be considerably simplified (and shortened) by using a result by the reviewer [\textit{M. Drmota}, J. Comb. Theory, Ser. A 67, 169--184 (1994; Zbl 0801.60016)]. For example, by observing that \(T(x^k,z^k)\) are regular for \(k\geq 2\) in the ``critical range'' where \(T(x,z)\) gets singular one directly gets an asymptotic formula for \(a_{n,[n/2]+\delta}\) (where \(\delta = O(1)\)) of the form \(a_{n,[n/2]} \sim c_2 n^{-2} C_1^n\). Nevertheless this will not improve the upper bound for \(I_d\).