This site is supported by donations to The OEIS Foundation.

# The Catalan-Seidel connection

## Some entries related to the Seidel transform and its variants

... which we discussed in the last two blog posts Seidel Transform, BernoulliNumbers and will discuss in this post. We assume that the reader is familiar with the discussion in Seidel Transform.

## The Catalan triangle

Consider the classical Catalan triangle A053121. The zeros in the triangle can be filled with the complementary Catalan numbers A189230 to give the extended Catalan triangle A189231. For now we will just ignore the zeros and show the Seidel way of computing this compacted form, which is A008313.

```def SeidelCatalanTriangle(n) :
D = [0]*((n+5)//2); D[1] = 1
b = True; h = 1
for i in range(n) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1
else :
for k in range(1,h, 1) : D[k] += D[k+1]
b = not b
print [D[z] for z in (1..h-1)]
```
```SeidelCatalanTriangle(13)

[1]
[1]
[1, 1]
[2, 1]
[2, 3, 1]
[5, 4, 1]
[5, 9, 5, 1]
[14, 14, 6, 1]
[14, 28, 20, 7, 1]
[42, 48, 27, 8, 1]
[42, 90, 75, 35, 9, 1]
[132, 165, 110, 44, 10, 1]
[132, 297, 275, 154, 54, 11, 1]
```

Same with Maple:

```SeidelCatalanTriangle := proc(n) local d,b,i,h,k:
d := array(0..iquo(n+4,2));
d[0] := 0; d[1] := 1;
b := true;
for i from 0 to n do
h := iquo(i+4,2);
d[h] := 0;
if b then
for k from h-1 by -1 to 1 do d[k] := d[k] + d[k-1] od;
else
for k from 1 to h-1 do  d[k] := d[k] + d[k+1] od;
fi;
b := not b;
print([i],seq(d[k], k= 1..h-1));
od end:
```

## Catalan numbers (A000108)

By simply applying a filter to the Catalan triangle function the Catalan numbers will be generated in Seidel's algorithmic way.

```def A000108_list(n) :
D = [0]*(n+1); D[1] = 1
b = True; h = 1; R = []
for i in range(2*n-1) :
if b :
for k in range(h, 0, -1) : D[k] += D[k-1]
h += 1; R.append(D[1])
else :
for k in range(1, h, 1) : D[k] += D[k+1]
b = not b
return R
```

The charm of this algorithm is that no division and no multiplication is needed.

## First differences of Catalan numbers (A000245)

```def A000245_list(n) :
D = [0]*(n+1); D[1] = 1
b = False; h = 1; R = []
for i in range(2*n-1) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1; R.append(D[2])
else :
for k in range(1,h, 1) : D[k] += D[k+1]
b = not b
return R
```

## q-Catalan numbers for q = -1 (A090192)

```def A090192_list(n) :
D = [0]*(n+2); D[1] = 1
b = True; h = 1; R = []
for i in range(2*n-1) :
if b :
for k in range(h, 0, -1) : D[k] -= D[k-1]
h += 1; R.append(D[1])
else :
for k in range(1, h, 1) : D[k] += D[k+1]
b = not b
return R
```

## Aerated Catalan numbers. (A126120)

Also integral(x=-2..2, x^n*sqrt((2-x)*(2+x)))/(2*Pi).

```def A126120_list(n) :
D = [0]*(n+2); D[1] = 1
b = True; h = 2; R = []
for i in range(2*n-1) :
if b :
for k in range(h, 0, -1) : D[k] -= D[k-1]
h += 1; R.append(abs(D[1]))
else :
for k in range(1, h, 1) : D[k] += D[k+1]
b = not b
return R
```

## An inverse Chebyshev transform of 1-x (A099363)

```def A099363_list(n) :
D = [0]*(n+2); D[1] = 1
b = True; h = 2; R = []
for i in range(2*n-1) :
if b :
for k in range(h, 0, -1) : D[k] -= D[k-1]
h += 1; R.append((-1)^(h//2)*D[2])
else :
for k in range(1, h, 1) : D[k] += D[k+1]
b = not b
return R
```

## Little Schröder numbers (A001003)

As I remarked in Schröder Numbers there are two kinds of little Schröder numbers, the even little Schröder numbers and the odd little Schröder numbers counting different combinatorial objects, for example
Seven(6) = 1 + 140 + 630 + 132 = 903
Sodd(6) = 21 + 420 + 462 = 903
Here we count the even little Schröder numbers which start with 1 (see the link for more on this).

```def A001003_list(n) :
D = [0]*(n+1); D[1] = 1/2
b = True; h = 2; R = [1]
for i in range(2*n-2) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1;
else :
for k in range(1,h, 1) : D[k] += D[k-1]
R.append(D[h-1]);
b = not b
return R
```

## Large Schröder numbers (A006318)

Almost identical is the computation of the large Schröder numbers.

```def A006318_list(n) :
D = [0]*(n+1); D[1] = 1
b = True; h = 1; R = []
for i in range(2*n) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1;
else :
for k in range(1,h, 1) : D[k] += D[k-1]
R.append(D[h-1]);
b = not b
return R
```

## Royal paths in a lattice (convolution of large Schröder numbers) (A006319).

```def A006319_list(n) :
D = [0]*(n+1); D[1] = 1
b = True; h = 2; R = [1]
for i in range(2*n-2) :
if b :
for k in range(h, 0, -1) : D[k] += D[k-1]
h += 1;
else :
for k in range(1, h, 1) : D[k] += D[k-1]
R.append(D[h-2]);
b = not b
return R
```

## Partial sums of the large Schröder numbers (A086616)

```def A086616_list(n) :
D = [0]*(n+2); D[1] = 1
b = True; h = 2; R = []
for i in range(2*n) :
if b :
for k in range(h, 0, -1) : D[k] += D[k-1]
else :
for k in range(1, h, 1) : D[k] += D[k-1]
R.append(D[h-1]); h += 1;
b = not b
return R
```

## Large Schröder numbers minus 1 (A035011)

```def A035011_list(n) :
D = [0]*(n+2); D[1] = 1
b = True; h = 2; R = []
for i in range(2*n) :
if b :
for k in range(h, 0, -1) : D[k] += D[k-1]
else :
for k in range(1, h, 1) : D[k] += D[k-1]
R.append(D[h-2]); h += 1;
b = not b
return R
```

## Powers of x in terms of Chebyshev's U-polynomials (A039598, A039599)

Because of the importance of the Catalan numbers we indicate also two popular variants which can be derived from the above function. Looking only at the even case one gets A039599, a triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials Un(x).

```def A039599_triangle(n) :
D = [0]*(n+2); D[1] = 1
b = True; h = 1
for i in range(2*n-1) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1
else :
for k in range(1,h, 1) : D[k] += D[k+1]
if b : print [D[z] for z in (1..h-1)]
b = not b

A039599_triangle(10)
[1]
[1, 1]
[2, 3, 1]
[5, 9, 5, 1]
[14, 28, 20, 7, 1]
[42, 90, 75, 35, 9, 1]
[132, 297, 275, 154, 54, 11, 1]
[429, 1001, 1001, 637, 273, 77, 13, 1]
[1430, 3432, 3640, 2548, 1260, 440, 104, 15, 1]
[4862, 11934, 13260, 9996, 5508, 2244, 663, 135, 17, 1]
```

Looking only at the odd case one gets A039598, a triangle formed from odd-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials Un(x).

```def A039598_triangle(n) :
D = [0]*(n+2); D[1] = 1
b = True; h = 1
for i in range(2*n) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1
else :
for k in range(1,h, 1) : D[k] += D[k+1]
b = not b
if b : print [D[z] for z in (1..h-1)]

A039598_triangle(10)
[1]
[2, 1]
[5, 4, 1]
[14, 14, 6, 1]
[42, 48, 27, 8, 1]
[132, 165, 110, 44, 10, 1]
[429, 572, 429, 208, 65, 12, 1]
[1430, 2002, 1638, 910, 350, 90, 14, 1]
[4862, 7072, 6188, 3808, 1700, 544, 119, 16, 1]
[16796, 25194, 23256, 15504, 7752, 2907, 798, 152, 18, 1]
```

## Two Riordan arrays of Paul Barry (A165621, A112554)

We give a closely related signed version of Paul Barry's A165621, Riordan array (c(x^2)*(1+xc(x^2)), xc(x^2)).

```def Signed_A165621_triangle(n) :
D = [0]*(n+4); D[1] = 1
b = False; h = 3
for i in range(2*n) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1
else :
for k in range(1,h, 1) : D[k] -= D[k+1]
if b : print [D[z] for z in (2..h-2)]
b = not b

Signed_A165621_triangle(11)
[1]
[1, 1]
[-1, 1, 1]
[-2, -2, 1, 1]
[2, -3, -3, 1, 1]
[5, 5, -4, -4, 1, 1]
[-5, 9, 9, -5, -5, 1, 1]
[-14, -14, 14, 14, -6, -6, 1, 1]
[14, -28, -28, 20, 20, -7, -7, 1, 1]
[42, 42, -48, -48, 27, 27, -8, -8, 1, 1]
[-42, 90, 90, -75, -75, 35, 35, -9, -9, 1, 1]
```

If one compares this procedure with Barry's formula the powerful simplicity of Seidel's approach impresses again.

```T(n,k) = sum{j = 0..n, b(n - j)*sum{i = 0..k, (-1)^(k - i)*
C(k, i)*sum{m = 0..i, C(i, m)*(C(i - m, m + k)
- C(i - m,i + k + 2))}}}<br />
where b(n) is the sequence beginning with 1 followed by the
aerated Catalan numbers: 1,1,0,1,0,2,0,5,0,14,...
```

Similarly Barry's triangle A112554, Riordan array (c(x^2)^2, xc(x^2)), c(x) the g. f. of the Catalan numbers A000108, can be computed as follows.

```def Signed_A112554_triangle(n) :
D = [0]*(n+4); D[1] = 1
b = False; h = 2
for i in range(2*n+2) :
if b :
for k in range(h,0,-1) : D[k] += D[k-1]
h += 1
else :
for k in range(1,h, 1) : D[k] -= D[k+1]
b = not b
if b and i > 0 : print [D[z] for z in (2..h-1)]

Signed_A112554_triangle(13)
[1]
[0, 1]
[-2, 0, 1]
[0, -3, 0, 1]
[5, 0, -4, 0, 1]
[0, 9, 0, -5, 0, 1]
[-14, 0, 14, 0, -6, 0, 1]
[0, -28, 0, 20, 0, -7, 0, 1]
[42, 0, -48, 0, 27, 0, -8, 0, 1]
[0, 90, 0, -75, 0, 35, 0, -9, 0, 1]
[-132, 0, 165, 0, -110, 0, 44, 0, -10, 0, 1]
[0, -297, 0, 275, 0, -154, 0, 54, 0, -11, 0, 1]
[429, 0, -572, 0, 429, 0, -208, 0, 65, 0, -12, 0, 1]
```