A380256 Number of rooted binary normal unlabeled galled trees with n leaves and exactly 1 gall.

0, 0, 0, 1, 4, 15, 48, 148, 435, 1250, 3512, 9726, 26587, 71975, 193200, 515051, 1364896, 3598794, 9447028, 24704031, 64382465, 167288460, 433512724, 1120719444, 2891035926, 7443225226, 19129208972, 49082742607, 125752279124, 321744111359, 822165920924, 2098475215237

Offset: 0

Author

Noah A Rosenberg, Jan 17 2025

Keywords

• nonn

Comments

The asymptotic growth of a(n) follows (0.3910...)(2.4833...^n)n^(1/2), where 2.4833... is the constant represented by A086317.

Examples

			For n=3 leaves, there is a unique rooted binary unlabeled tree with a root gall from which 3 leaves are descended; hence a(3)=1. This galled tree has the shape:
     .
    / \
   ._._.
  /  |  \
		

Links

• Lily Agranat-Tamir, Shaili Mathur, and Noah A. Rosenberg, Enumeration of rooted binary unlabeled galled trees, Bull. Math. Biol. 86 (2024), 45. (see Table 3)
• Lily Agranat-Tamir, Michael Fuchs, Bernhard Gittenberger, and Noah A. Rosenberg, Asymptotic enumeration of rooted binary unlabeled galled trees with a fixed number of galls. In C. Mailler, S. Wild, eds. Proceedings of the 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs) 302: 27. Schloss Dagstuhl — Leibniz-Zentrum für Informatik.

Crossrefs

Cf. A001190 (rooted binary unlabeled galled trees with n leaves and 0 galls), A380211 (rooted binary unlabeled galled trees with n leaves and any number of galls).

Radius of convergence of the generating function follows the contstant A240943 (exponential growth according to A086317).

Formula

G.f.: 1/(1-U(x)) - 1/(1-U(x))^2 + U(x)/(2*(1-U(x))^3) + U(x)/(2*(1-U(x))*(1-U(x^2))), where U(x) is the g.f. of A001190 (eq. 48 of Agranat-Tamir et al., Bull. Math. Biol. 86 (2024), 45).