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
Keywords
Examples
The a(3) = 9 pairs of Motzkin paths are:
_
___ _/\ /\_ / \ _/\
___ ___ ___ ___ _/\
.
_ _ _
/ \ /\_ / \ /_\
_/\ /\_ /\_ / \
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1061
Crossrefs
Programs
-
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 -
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)]
Comments