A379034 Number of intervals in the lattice of Motzkin paths of length n.

1, 1, 3, 9, 36, 156, 754, 3886, 21239, 121411, 721189, 4423167, 27884979, 180023715, 1186646085, 7966608939, 54362492505, 376401432105, 2640553802523, 18745081044417, 134511480800046, 974773373273658, 7127937477283896, 52556513927004360, 390494071802647015

Offset

0,3

Comments

a(n) is the number of nested pairs of Motzkin paths of length n.

Links

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

Formula

a(n) = A151483(n) * A151483(n+1) / 4^n. - Mark van Hoeij, Dec 27 2025

Example

The a(3) = 9 pairs of Motzkin paths are:
                     _
  ___   _/\   /\_   / \   _/\
  ___   ___   ___   ___   _/\
.
   _           _     _
  / \   /\_   / \   /_\
  _/\   /\_   /\_   / \

Maple

a:= proc(n) option remember; `if`(n<3, [1$2, 3][n+1],
      (n*(7*n+13)*(n+3)*a(n-1)+3*(n+1)*(n-1)*(7*n+6)*a(n-2)
        -27*(n+1)*(n-1)*(n-2)*a(n-3))/((n+4)*(n+3)^2))
    end:
seq(a(n), n=0..24);  # Alois P. Heinz, Dec 14 2024

Prog

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

Crossrefs

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

Sequence in context: A058540 A350451 A245888 * A394959 A295739 A156016

Adjacent sequences: A379031 A379032 A379033 * A379035 A379036 A379037

Keyword

nonn

Author

Ludovic Schwob, Dec 14 2024

Status

approved