|
%I #26 Feb 21 2020 07:04:58
%S 1,1,3,7,23,66,227,715,2529,8398,30275,104006,380162,1337220,4939443,
%T 17678835,65844845,238819350,895451117,3282060210,12374186318,
%U 45741281820,173257703723,644952073662,2452607696798,9183676536076,35042725663002,131873975875180,504697422982484,1907493251046152
%N Half-convolution of Catalan sequence A000108 with itself.
%C 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:
%C 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.
%C 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.
%C 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.
%C 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]
%H Robert Israel, <a href="/A201204/b201204.txt">Table of n, a(n) for n = 0..170</a>
%F a(n) = sum(Catalan(k)*Catalan(n-k),k=0..floor(n/2)), n>=0, with Catalan(n)=A000108(n).
%F 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).
%F a(n) ~ 2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Oct 15 2014
%F a(n) = A000108(n+1)/2 + 2^(2*n+1) * binomial(1/2, n/2+1)^2. - _Vladimir Reshetnikov_, Oct 03 2016
%F 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
%p C:= n -> binomial(2*n,n)/(n+1):
%p A:= n -> add(C(k)*C(n-k),k=0..floor(n/2));
%p seq(A(i),i=1..100); # _Robert Israel_, Jun 06 2014
%t Table[Sum[CatalanNumber[k]CatalanNumber[n-k],{k,0,Floor[n/2]}],{n,0,30}] (* _Harvey P. Dale_, Jun 12 2012 *)
%t Table[CatalanNumber[n + 1]/2 + 2^(2 n + 1) Binomial[1/2, n/2 + 1]^2, {n, 0, 30}] (* _Vladimir Reshetnikov_, Oct 03 2016 *)
%Y A000108, bisection: A201205 and A065097.
%K nonn,easy
%O 0,3
%A _Wolfdieter Lang_, Jan 02 2012
|
