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

Author

Noah A Rosenberg, Jan 19 2025

Keywords

• nonn
• tabf

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

Examples

			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;
		

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

First column (k=0) is A001190.

Second column (k=1) is A380256.

Row sums give A380211.

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