A393172 G.f. A(x) satisfies A(x-x^2) = x + A(x)^2.

1, 2, 8, 42, 260, 1808, 13744, 112290, 974880, 8922276, 85580496, 856495752, 8913100944, 96181220816, 1073829057728, 12380935349458, 147183697957428, 1801623160794480, 22680386387491816, 293333571234859004, 3893918653806360608, 53009297608751805168, 739458889943201941584, 10562209578309277545672

Offset

1,2

Comments

Conjecture: for n > 1, a(n) == 2 (mod 4) iff n is a power of 2, otherwise a(n) is divisible by 4.

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 + A(x)^2.

(2) A(x*(1-x)*(1-x+x^2)) = x + 2*x*A(x)^2 + A(x)^4.

(3) A(x) = C(x) + A(C(x))^2, where C(x) = x + C(x)^2 is a g.f. of the Catalan numbers (A000108).

(4) A(x) = C(x) + sq(C^2(x) + sq(C^3(x) + sq(C^4(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) = A000108(n-1) + Sum_{k=1..n} k/(2*n-k) * binomial(2*n-k,n-k) * b(k) where A000108(n) = binomial(2*n+1,n)/(2*n+1).

(5.d) a(n) = A000108(n-1) + Sum_{k=0..n-1} (n-k)/(n+k) * binomial(n+k,n) * b(n-k).

Example

G.f.: A(x) = x + 2*x^2 + 8*x^3 + 42*x^4 + 260*x^5 + 1808*x^6 + 13744*x^7 + 112290*x^8 + 974880*x^9 + 8922276*x^10 + ...
RELATED SERIES.
The g.f. of A393171 equals A(x-x^2) = x + A(x)^2, where
A(x)^2 = 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 + ... + A393171(n)*x^n + ...
A(C(x)) = x + 3*x^2 + 14*x^3 + 81*x^4 + 542*x^5 + 4046*x^6 + 32924*x^7 + 287407*x^8 + 2660942*x^9 + ...
A(C(x))^2 = x^2 + 6*x^3 + 37*x^4 + 246*x^5 + 1766*x^6 + 13612*x^7 + 111861*x^8 + 973450*x^9 + ... where A(x) = C(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) \\ By definition A(x-x^2) = x + A(x)^2
{a(n) = my(A=[0, 1]); for(i=1, n, A = concat(A, 0);
A[#A] = polcoef( x + Ser(A)^2 - subst(Ser(A), x, x-x^2), #A-1) ); polcoef(Ser(A), n)}
for(n=1, 30, print1(a(n), ", "))

Crossrefs

Cf. A393171 (A(x-x^2)), A000108, A392210.

Sequence in context: A013999 A130649 A054993 * A188912 A229285 A339460

Adjacent sequences: A393169 A393170 A393171 * A393173 A393174 A393175

Keyword

nonn

Author

Paul D. Hanna, Feb 04 2026

Status

approved