A379035 Number of intervals in the lattice of Schroeder paths of length 2*n.

1, 3, 20, 201, 2574, 38740, 654334, 12050561, 237383562, 4935186778, 107233505624, 2417430607946, 56224895607144, 1343171657532430, 32841495349026802, 819503313717327041, 20820095694805722362, 537474654188020125882, 14075078600122360679520, 373373810133893669112710

Offset: 0

Author

Ludovic Schwob, Dec 14 2024

Keywords

• nonn

Comments

a(n) is the number of nested pairs of Schroeder paths of length 2*n.

Examples

			The a(2) = 20 pairs of Schroeder paths are:
.                              __
  ____   __/\   /\__   /\/\   /  \
  ____   ____   ____   ____   ____
.
   /\                   __     /\
  /  \   __/\   /\/\   /  \   /  \
  ____   __/\   __/\   __/\   __/\
.
                 __     /\
  /\__   /\/\   /  \   /  \   /\/\
  /\__   /\__   /\__   /\__   /\/\
.
   __     /\     __     /\     /\
  /  \   /  \   /__\   /__\   //\\
  /\/\   /\/\   /  \   /  \   /  \
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..661

Crossrefs

Cf. A006318 (number of Schroeder paths), A005700 (number of intervals in the lattice of Dyck paths), A379034 (number of intervals in the lattice of Motzkin paths).

Programs

Python

from collections import defaultdict
def a_gen(n): #generator of terms a(0) to a(n)
    D = {(0,0):1}
    for k in range(2*n+2):
        D2 = defaultdict(int)
        for i,j in D:
            d = D[(i,j)]
            mi,mj = (i-k)%2,(j-k)%2
            for a in range(-mi,mi+1):
                for b in range(-mj,mj+1):
                    if 0 <= i+a <= j+b <= 2*n-k+1:
                        D2[(i+a,j+b)] += d
        D = D2
        if k%2==1:
            yield D[(0,0)]