A025246 a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-3)*a(3) for n >= 4, with initial terms 1, 0, 1, 1.

1, 0, 1, 1, 1, 2, 4, 7, 13, 26, 52, 104, 212, 438, 910, 1903, 4009, 8494, 18080, 38656, 82988, 178802, 386490, 837928, 1821664, 3970282, 8673258, 18987930, 41652382, 91539466, 201525238, 444379907, 981384125, 2170416738, 4806513660, 10657780276

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

Essentially the same as A023431.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 666

Crossrefs

Cf. A000108, A023431.

Programs

Magma

[n le 2 select 2-n else (&+[Binomial(n-k-3, 2*k)*Catalan(k): k in [0..Floor((n-3)/3)]]): n in [1..45]]; // G. C. Greubel, Jun 15 2022

Maple

a := n -> ifelse(n < 3, 0^(n - 1),
   hypergeom([(3 - n)/3, (4 - n)/3, (5 - n)/3], [2, -n + 3], 27)):
seq(simplify(a(n)), n = 1..32); # Peter Luschny, Jun 15 2022

Mathematica

a[n_]:= a[n]= If[n<4, 1-Boole[n==2], Sum[a[j]*a[n-j], {j,n-3}]];
Table[a[n], {n, 45}] (* G. C. Greubel, Jun 15 2022 *)

PARI

a(n)=polcoeff((1+x-sqrt(1-2*x+x^2-4*x^3+x*O(x^n)))/2,n)

SageMath

[bool(n==1) + sum(binomial(n-k-3,2*k)*catalan_number(k) for k in (0..((n-3)//3))) for n in (1..45)] # G. C. Greubel, Jun 15 2022

Formula

a(n) = A023431(n-3).

G.f.: (1+x-sqrt(1-2*x+x^2-4*x^3))/2. - Michael Somos, Jun 08 2000

n*a(n) = (2*n-3)*a(n-1) -(n-3)*a(n-2) +2*(2*n-9)*a(n-3). - R. J. Mathar, Feb 25 2015

a(n) = hypergeom([(3 - n)/3, (4 - n)/3, (5 - n)/3], [2, 3 - n], 27) for n >= 3. - Peter Luschny, Jun 15 2022