OFFSET
0,3
COMMENTS
Compare to C(x) = Sum_{n>=0} c(n)*x^n where c(n) = Sum_{k=0..n-1} [x^k] C(x)^(n-k) for n >= 1 with c(0) = 1, holds when C(x) is the g.f. of the Catalan numbers (A000108).
LINKS
Paul D. Hanna, Table of n, a(n) for n = 0..300
FORMULA
G.f. A(x) = Sum_{n>=0} a(n)*x^n satisfies the following formulas.
(1) a(n) = Sum_{k=0..n-1} [x^k] A(x)^(k*(n-k)) for n >= 1, with a(0) = 1.
(2) A(x) = 1 + x*Sum_{n>=0} x^n/n! * ( d^n/dy^n A(y)^n/(1 - x*A(y)^n) ) evaluated at y = 0.
a(n) ~ c * n! * n^alpha / LambertW(1)^n, where alpha = 0.68670155428... and c = 0.09981115968806..., conjecture: alpha = 2*LambertW(1) - 3 + 4/(1 + LambertW(1)) = 0.6867015542800108601...- Vaclav Kotesovec, Nov 23 2024
EXAMPLE
G.f.: A(x) = 1 + x + 2*x^2 + 8*x^3 + 55*x^4 + 525*x^5 + 6202*x^6 + 85842*x^7 + 1350421*x^8 + 23687392*x^9 + 457238998*x^10 + 9620344475*x^11 + 219011293036*x^12 + ...
By definition, a(n) equals the sum of the coefficients of x^k in A(x)^(k*(n-k)), k = 0..n-1, for n >= 1, as illustrated below.
a(1) = [x^0] A(x)^0;
a(2) = 1 + [x^1] A(x)^1;
a(3) = 1 + [x^1] A(x)^2 + [x^2] A(x)^2;
a(4) = 1 + [x^1] A(x)^3 + [x^2] A(x)^4 + [x^3] A(x)^3;
a(5) = 1 + [x^1] A(x)^4 + [x^2] A(x)^6 + [x^3] A(x)^6 + [x^4] A(x)^4;
a(6) = 1 + [x^1] A(x)^5 + [x^2] A(x)^8 + [x^3] A(x)^9 + [x^4] A(x)^8 + [x^5] A(x)^5;
a(7) = 1 + [x^1] A(x)^6 + [x^2] A(x)^10 + [x^3] A(x)^12 + [x^4] A(x)^12 + [x^5] A(x)^10 + [x^6] A(x)^6;
a(8) = 1 + [x^1] A(x)^7 + [x^2] A(x)^12 + [x^3] A(x)^15 + [x^4] A(x)^16 + [x^5] A(x)^15 + [x^6] A(x)^12 + [x^7] A(x)^7;
...
Explicitly,
a(1) = 1 = 1;
a(2) = 1 + 1 = 2;
a(3) = 1 + 2 + 5 = 8;
a(4) = 1 + 3 + 14 + 37 = 55;
a(5) = 1 + 4 + 27 + 128 + 365 = 525;
a(6) = 1 + 5 + 44 + 300 + 1406 + 4446 = 6202;
a(7) = 1 + 6 + 65 + 580 + 3795 + 17892 + 63503 = 85842;
a(8) = 1 + 7 + 90 + 995 + 8460 + 53088 + 258212 + 1029568 = 1350421;
...
RELATED TABLES.
The table of coefficients of x^k in A(x)^n begins as follows.
n\k 0 1 2 3 4 5 6 7
A^1 = [1, 1, 2, 8, 55, 525, 6202, 85842, ...];
A^2 = [1, 2, 5, 20, 130, 1192, 13738, 187068, ...];
A^3 = [1, 3, 9, 37, 231, 2037, 22877, 306201, ...];
A^4 = [1, 4, 14, 60, 365, 3104, 33944, 446208, ...];
A^5 = [1, 5, 20, 90, 540, 4446, 47330, 610580, ...];
A^6 = [1, 6, 27, 128, 765, 6126, 63503, 803424, ...];
A^7 = [1, 7, 35, 175, 1050, 8218, 83020, 1029568, ...];
A^8 = [1, 8, 44, 232, 1406, 10808, 106540, ...];
A^9 = [1, 9, 54, 300, 1845, 13995, 134838, ...];
A^10 = [1, 10, 65, 380, 2380, 17892, 168820, ...];
A^11 = [1, 11, 77, 473, 3025, 22627, 209539, ...];
A^12 = [1, 12, 90, 580, 3795, 28344, 258212, ...];
A^13 = [1, 13, 104, 702, 4706, 35204, 316238, ...];
A^14 = [1, 14, 119, 840, 5775, 43386, 385217, ...];
A^15 = [1, 15, 135, 995, 7020, 53088, 466970, ...];
A^16 = [1, 16, 152, 1168, 8460, 64528, 563560, ...];
...
PROG
(PARI) {a(n) = my(A=[1]); for(m=1, n, A=concat(A, 0);
A[#A] = 1 + sum(k=1, m-1, (polcoeff(Ser(A)^(k*(m-k)), k)) )); A[n+1]}
for(n=0, 30, print1(a(n), ", "))
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Nov 10 2024
STATUS
approved