A380211 Number of rooted binary normal unlabeled galled trees with n leaves.

0, 1, 1, 2, 6, 20, 72, 272, 1064, 4271, 17497, 72843, 307307, 1310792, 5643555, 24493270, 107043258, 470668034, 2080681402, 9242180923, 41229189089, 184634145428, 829732117279, 3740636883361, 16912812764736, 76673344515050, 348449086540653, 1587154540744158

Offset

0,4

Comments

The asymptotic growth of a(n) follows (0.0779...)*(4.8230...^n)*n^(-3/2).

Links

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

Lily Agranat-Tamir, Shaili Mathur, and Noah A. Rosenberg, Enumeration of rooted binary unlabeled galled trees, Bull. Math. Biol. 86 (2024), 45.

Formula

G.f. satisfies A(x) = 1 + x + (1/2)*A(x)^2 + (1/2)*A(x^2) - 1/(1-A(x)) + A(x)/(2*(1-A(x))^2) + A(x)/(2*(1-A(x^2))).

Example

For n=3 leaves, there is the unique rooted binary unlabeled tree with 3 leaves and no galls, and there is a rooted binary unlabeled tree with a root gall from which 3 leaves are descended; hence a(3)=2.

Mathematica

terms = 28; A[_] = 0; Do[A[x_] = x + (1/2)*(A[x]^2 + A[x^2]) +A[x]((A[x]/(1-A[x]))^2+A[x^2]/(1-A[x^2]))/2+ O[x]^terms // Normal, terms]; CoefficientList[A[x], x] (* Stefano Spezia, Mar 22 2025 *)

Crossrefs

Cf. A001190 (rooted binary unlabeled galled trees with n leaves and 0 galls).

Sequence in context: A063376 A161168 A049139 * A071356 A141200 A186996

Adjacent sequences: A380208 A380209 A380210 * A380212 A380213 A380214

Keyword

nonn

Author

Noah A Rosenberg, Jan 16 2025

Status

approved