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

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

Comments

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

Links

Table of n, a(n) for n=1..49.

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

Example

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;

Crossrefs

First column (k=0) is A001190.

Second column (k=1) is A380256.

Row sums give A380211.

Sequence in context: A259476 A271363 A115399 * A109429 A358820 A366027

Adjacent sequences: A380303 A380304 A380305 * A380307 A380308 A380309

Keyword

nonn,tabf

Author

Noah A Rosenberg, Jan 19 2025

Status

approved