OFFSET
1,3
COMMENTS
Conjecture: for n > 2, a(n) == 4 (mod 8) iff n = 2^k or n = 2^k + 1 for k >= 1, otherwise a(n) is divisible by 8.
LINKS
Paul D. Hanna, Table of n, a(n) for n = 1..520
FORMULA
G.f. A(x) = Sum_{n>=1} a(n)*x^n satisfies the following formulas.
(1) A(x-x^2) = x-x^2 + A(x)^2.
(2) A(x*(1-x)*(1-x+x^2)) = x*(1-x) + 2*x*(1-x)*A(x)^2 + A(x)^4.
(3) A(x) = x + A(C(x))^2, where C(x) = x + C(x)^2 is a g.f. of the Catalan numbers (A000108).
(4) A(x) = x + sq(C(x) + sq(C^2(x) + sq(C^3(x) + ...))), an infinitely nested square involving successive iterations of the Catalan function C(x) = x + C(x)^2, where sq(x) = x^2 and C^k(x) equals the k-th iteration of C(x).
Let A(x)^2 = Sum_{n>=2} b(n)*x^n then for n >= 2,
(5.a) b(n) = Sum_{k=1..n-1} a(k) * a(n-k), and
(5.b) b(n) = Sum_{k=0..[n/2]} (-1)^k * binomial(n-k,k) * a(n-k), where [n/2] = floor(n/2).
(5.c) a(n) = Sum_{k=1..n} k/(2*n-k) * binomial(2*n-k,n-k) * b(k).
(5.d) a(n) = Sum_{k=0..n-1} (n-k)/(n+k) * binomial(n+k,n) * b(n-k).
EXAMPLE
G.f.: A(x) = x + x^2 + 4*x^3 + 20*x^4 + 116*x^5 + 752*x^6 + 5328*x^7 + 40644*x^8 + 330324*x^9 + 2838296*x^10 + ...
RELATED SERIES.
A(x)^2 = x^2 + 2*x^3 + 9*x^4 + 48*x^5 + 288*x^6 + 1896*x^7 + 13488*x^8 + 102600*x^9 + 828096*x^10 + ... where A(x-x^2) = x-x^2 + A(x)^2.
The g.f. of A393172 equals A(C(x)) where
A(C(x)) = x + 2*x^2 + 8*x^3 + 42*x^4 + 260*x^5 + 1808*x^6 + 13744*x^7 + 112290*x^8 + ... + A393172(n)*x^n + ...
A(C(x))^2 = x^2 + 4*x^3 + 20*x^4 + 116*x^5 + 752*x^6 + ... where A(x) = x + A(C(x))^2.
The Catalan function C(x) = x + C(x)^2 begins
C(x) = x + x^2 + 2*x^3 + 5*x^4 + 14*x^5 + 42*x^6 + 132*x^7 + 429*x^8 + 1430*x^9 + ... + A000108(n-1)*x^n + ...
PROG
(PARI) \\ From A(x-x^2) = x-x^2 + A(x)^2
{a(n) = my(A=[0, 1]); for(i=1, n, A = concat(A, 0);
A[#A] = polcoef( x-x^2 + Ser(A)^2 - subst(Ser(A), x, x-x^2), #A-1) ); polcoef(Ser(A), n)}
for(n=1, 30, print1(a(n), ", "))
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Feb 04 2026
STATUS
approved