More convolution identities.

[Antti Karttunen]

>

Dear readers,

As a variation of the convolution identity I recently submmited,
concerning A001405:

ID Number: A001405 (Formerly M0769 and N0294)
Sequence:  1,1,2,3,6,10,20,35,70,126,252,462,924,1716,3432,6435,12870,
           24310,48620,92378,184756,352716,705432,1352078,2704156,
           5200300,10400600,20058300,40116600,77558760,155117520,
           300540195,601080390,1166803110
Name:      Central binomial coefficients: C(n,[ n/2 ]).
Comments:  Sperner's theorem says that this is the maximal number of
subsets of an
              n-set such that no one contains another.
           When computed from index -1,
              [seq(binomial(n,floor(n/2)),n=-1..30)]; -->
              [1,1,1,2,3,6,10,20,35,70,126,...] and convolved with
aerated
              Catalans [seq((n+1 mod
2)*binomial(n,n/2)/((n/2)+1),n=0..30)];
              --> [1,0,1,0,2,0,5,0,14,0,42,0,132,0,...] shifts left by
one:
              [1,1,2,3,6,10,20,35,70,126,252,...], and if again
convolved with
              aerated Catalans, seems to give A037952 apart from the
initial term. -
              Antti Karttunen (karttu at megabaud.fi), Jun 05 2001

The first identity is based on the fact, that each binary sequence in
A061854
which encode lattice that use steps (+1,+1), (+1,-1) origin (0,0) and
never "dive"
under the "sea-level" y=0, can be expressed _uniquely_ as a combination
of totally balanced binary sequences in A014486 (Dyck paths) and lattice
walks
(+1,+1), (+1,-1) that never _return_ to y=0 line, which thus are
obtained from
the sequences of A061854 by adding a bit 1 to the front. (i.e. one
updward
step / to the beginning of the corresponding lattice walks), thus while
the "nondivers"
are counted by A001405, the "never returners" are counted by the same
sequence shifted right by one (with 1 prepended to the front).

(and this everything is just a variation of the example "4. Free
monoids"
in I. M. Gessel, R. P. Stanley, Algebraic Enumeration, i.e. Chapter 21,
pages 1021-1061
of Handbook of Combinatorics, Volume 2. See pages 1028 & 1029.
Essentially
we are dividing by 2 the sequence counting words of T given there.)

Now, here is a simple application of the same idea, if we take _the
bisections_
of the both sequences to be convoluted:


%C A001700 When computed from index -1, [seq(binomial(2*n+1,
n+1),n=-1..31)]; --> [1,1,3,10,35,126,...] (i.e. bisection of A001405
computed from -1)  and convolved with Catalans (bisection of aerated
Catalans), gives A000984 (bisection of A001405).

Compare this with Wofdieter's note at Formula lines:
[A001700 is] Convolution of A000108 (Catalan) and A000984 (central
binomial):
              Sum(C(k)*binomial(2*(n-k),n-k),k=0..n),

and combining these two identities, we get

if we first set:
A001700from_minus_one := [seq(binomial(2*n+1, n+1),n=-1..31)];
 [1,1,3,10,35,126,462,1716,6435,...]

CONV(A000108,CONV(A001700from_minus_one,A000108));
[1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078,
5200300, 20058300, 77558760, 300540195]

or, because convolution here is associative and commutative, and because
Catalan's
shift left when convoluted once with themselves:
CONV(A001700_from_minus_one, A000108[2..nops(A000108)]);
[1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078,
5200300, 20058300, 77558760,...]

i.e
%C A001700  if computed from -1, [1,1,3,10,35,...] and convolved with
Catalan's
shifted once left [1,2,5,14,42,...] shifts left by one.

Should we collect these identities with more concice notation, e.g.:

A001700 := CONV(A000108,A000984)
A000984 := CONV(R(A001700),A000108)
thus: A001700 := CONV(R(A001700),L(A000108))
where R and L are the right shift (with 1 prepended)
and the left shift respectively.

(Although not related to this, the following comment could also give a
pointer to A057514):
%C A001700 Total number of leaves [A057514] in all ordered trees with
n+1 edges.


Convolutedly yours,

Antti