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,5

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.

Links

Table of n, a(n) for n=0..31.

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.

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).

Example

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:
     .
    / \
   ._._.
  /  |  \

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).

Sequence in context: A227099 A225976 A093967 * A052201 A320460 A178704

Adjacent sequences: A380253 A380254 A380255 * A380257 A380258 A380259

Keyword

nonn,new

Author

Noah A Rosenberg, Jan 17 2025

Status

approved