A201204 Half-convolution of Catalan sequence A000108 with itself.

1, 1, 3, 7, 23, 66, 227, 715, 2529, 8398, 30275, 104006, 380162, 1337220, 4939443, 17678835, 65844845, 238819350, 895451117, 3282060210, 12374186318, 45741281820, 173257703723, 644952073662, 2452607696798, 9183676536076, 35042725663002, 131873975875180, 504697422982484, 1907493251046152

Offset: 0

Author

Wolfdieter Lang, Jan 02 2012

Keywords

• nonn
• easy

Comments

In general the half-convolution of a sequence {b(n)}_0^infty with itself is defined by chat(n):=sum(b(k)*b(n-k), k=0..floor(n/2)), n>=0. The o.g.f. of the sequence {chat(n)} is obtained from the bisection 2*chat(2*k) - b(k)^2 = c(2*k), k>=0, with the ordinary convolution c(n):=sum(b(k)*b(n-k),k=0..n), n>=0, and 2*chat(2*k+1) = c(2*k+1), k>=0. This leads to the o.g.f.s for the corresponding even (e) and odd (o) parts:

2*Chate(x) - B2(x) = Ce(x) and 2*Chato(x) = Co(x), where Chate(x):= sum(chat(2*k)*x^k,k=0..infty), Chato(x):= sum(chat(2*k+1)*x^k,k=0..infty), B2(x) := sum(b(k)^2*x^k, k=0..infty), Ce(x) := sum(c(2*k)*x^k, k=0..infty) and Co(x) := sum(c(2*k+1)*x^k, k=0..infty). Thus Chate(x)=(Ce(x) + B2(x))/2 and Chato(x)=Co(x)/2. Expressing this in terms of C(x), the o.g.f. of {c(n)}, and B2(x) leads to the result: Chat(x)= (C(x) + B2(x^2))/2.

In the Catalan case b(n)=A000108(n), c(n)=b(n+1), C(x)= (cata(x)+1)/x, with the o.g.f. of A000108 cata(x)=(1-sqrt(1-4*x))/(2*x), and B2(x) is found under A001246 to be (-1 + hypergeom([-1/2,-1/2],[1],16*x))/(4*x). This produces the o.g.f. given in the formula section.

This computation was motivated by a question about the o.g.f. of A000992 ("half-Catalan numbers"). Note, however, that this sequence is not the half-convolution of the Catalan numbers presented here.

Apparently the number of hills to the left of or at the midpoint in all Dyck paths of semilength n+1. [David Scambler, Apr 30 2013]

Links

• Robert Israel, Table of n, a(n) for n = 0..170

Crossrefs

A000108, bisection: A201205 and A065097.

Programs

Maple

C:= n -> binomial(2*n,n)/(n+1):
A:= n -> add(C(k)*C(n-k),k=0..floor(n/2));
seq(A(i),i=1..100); # Robert Israel, Jun 06 2014

Mathematica

Table[Sum[CatalanNumber[k]CatalanNumber[n-k],{k,0,Floor[n/2]}],{n,0,30}] (* Harvey P. Dale, Jun 12 2012 *)
Table[CatalanNumber[n + 1]/2 + 2^(2 n + 1) Binomial[1/2, n/2 + 1]^2, {n, 0, 30}] (* Vladimir Reshetnikov, Oct 03 2016 *)

Formula

a(n) = sum(Catalan(k)*Catalan(n-k),k=0..floor(n/2)), n>=0, with Catalan(n)=A000108(n).

O.g.f.: G(x)=(catalan(x)-1)/(2*x)+(-1+hypergeom([-1/2,-1/2],[1],16*x^2))/(8*x^2), with the o.g.f. catalan(x) of the Catalan numbers (see also the comment section).

a(n) ~ 2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Oct 15 2014

a(n) = A000108(n+1)/2 + 2^(2*n+1) * binomial(1/2, n/2+1)^2. - Vladimir Reshetnikov, Oct 03 2016

D-finite with recurrence: (n+1)*(n+2)^2*a(n) +6*(n-2)*(n+1)^2*a(n-1) +4*(-16*n^3+25*n^2+4*n-4)*a(n-2) +16*(-4*n^3+25*n^2-56*n+41)*a(n-3) +192*(4*n-7)*(n-3)^2*a(n-4) -256*(2*n-7)*(n-4)^2*a(n-5)=0. - R. J. Mathar, Feb 21 2020