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.

A000108	A000111	A000182	A000245	A000364	A000367	A000657
A000660	A000667	A000734	A000737	A000795	A001003	A002084
A002445	A005439	A006318	A006319	A008280	A008313	A009747
A014781	A035011	A039598	A039599	A062161	A062162	A062272
A086616	A090192	A099363	A099960	A110501	A112554	A126120
A165621	A181131	A212196

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
S_even(6) = 1 + 140 + 630 + 132 = 903
S_odd(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 U_n(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 U_n(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]

User:Peter Luschny/SeidelTriangles

Contents