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,2

Comments

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

Links

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

Example

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

Prog

(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)]

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).

Sequence in context: A052595 A367924 A363136 * A244491 A295100 A367922

Adjacent sequences: A379032 A379033 A379034 * A379036 A379037 A379038

Keyword

nonn

Author

Ludovic Schwob, Dec 14 2024

Status

approved