|
| |
|
|
A201204
|
|
Half-convolution of Catalan sequence A000108 with itself.
|
|
14
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
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
|
|
|
|
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).
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
|
|
|
MAPLE
|
C:= n -> binomial(2*n, n)/(n+1):
A:= n -> add(C(k)*C(n-k), k=0..floor(n/2));
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
