A380211 -id:A380211 - cp's OEIS frontend

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

Noah A Rosenberg, Jan 17 2025

nonn

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

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

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.

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

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

A380306 Irregular triangle read by rows: T(n,k) is the number of rooted binary normal unlabeled galled trees with n leaves and exactly k galls, 0 <= k <= floor((n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 3, 15, 2, 6, 48, 18, 11, 148, 107, 6, 23, 435, 528, 78, 46, 1250, 2295, 661, 19, 98, 3512, 9185, 4356, 346, 207, 9726, 34503, 24564, 3776, 67, 451, 26587, 123612, 123825, 31289, 1543, 983, 71975, 426218, 574149, 216501, 20720, 246

Offset: 1

Noah A Rosenberg, Jan 19 2025

For fixed k, the asymptotic growth of T(n,k) with n follows (2^(2*k-1) / ((2*k)! * g^(4*k-1) * sqrt(Pi))) * n^(2*k-3/2) * r^n, where r is the constant 2.4833... represented by A086317 and g is a constant 1.1300... (Theorem 10 of Agranat-Tamir et al., Leibniz International Proceedings in Informatics (LIPIcs) 302 (2024), 27).

			Triangle begins:
     1;
     1;
     1,      1;
     2,      4;
     3,     15,       2;
     6,     48,      18;
    11,    148,     107,       6;
    23,    435,     528,      78;
    46,   1250,    2295,     661,      19;
    98,   3512,    9185,    4356,     346;
   207,   9726,   34503,   24564,    3776,     67;
   451,  26587,  123612,  123825,   31289,   1543;
   983,  71975,  426218,  574149,  216501,  20720,  246;
  2179, 193200, 1425011, 2493129. 1316450, 206644, 6942;

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.

First column (k=0) is A001190.
Second column (k=1) is A380256.
Row sums give A380211.

G.f. satisfies A(x,y) = x + y + (1/2)*A(x,y)^2 + (1/2)*A(x^2,y^2) - y/(1-A(x,y)) + y*A(x,y)/(2*(1-A(x,y))^2) + y*A(x,y)/(2*(1-A(x^2,y^2))) (eq. 56 of Agranat-Tamir et al., Bull. Math. Biol. 86 (2024), 45).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula