cp's OEIS Frontend

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

%I A379034 #15 Dec 16 2024 10:10:42
%S A379034 1,1,3,9,36,156,754,3886,21239,121411,721189,4423167,27884979,
%T A379034 180023715,1186646085,7966608939,54362492505,376401432105,
%U A379034 2640553802523,18745081044417,134511480800046,974773373273658,7127937477283896,52556513927004360,390494071802647015
%N A379034 Number of intervals in the lattice of Motzkin paths of length n.
%C A379034 a(n) is the number of nested pairs of Motzkin paths of length n.
%H A379034 Alois P. Heinz, <a href="/A379034/b379034.txt">Table of n, a(n) for n = 0..1061</a>
%e A379034 The a(3) = 9 pairs of Motzkin paths are:
%e A379034                      _
%e A379034   ___   _/\   /\_   / \   _/\
%e A379034   ___   ___   ___   ___   _/\
%e A379034 .
%e A379034    _           _     _
%e A379034   / \   /\_   / \   /_\
%e A379034   _/\   /\_   /\_   / \
%p A379034 a:= proc(n) option remember; `if`(n<3, [1$2, 3][n+1],
%p A379034       (n*(7*n+13)*(n+3)*a(n-1)+3*(n+1)*(n-1)*(7*n+6)*a(n-2)
%p A379034         -27*(n+1)*(n-1)*(n-2)*a(n-3))/((n+4)*(n+3)^2))
%p A379034     end:
%p A379034 seq(a(n), n=0..24);  # _Alois P. Heinz_, Dec 14 2024
%o A379034 (Python)
%o A379034 from collections import defaultdict
%o A379034 def a_gen(n): #generator of terms a(0) to a(n)
%o A379034     D = {(0,0):1}
%o A379034     yield 1
%o A379034     for k in range(n):
%o A379034         D2 = defaultdict(int)
%o A379034         for i,j in D:
%o A379034             d = D[(i,j)]
%o A379034             for a in range(-1,2):
%o A379034                 for b in range(-1,2):
%o A379034                     if 0 <= i+a <= j+b <= n-k-1:
%o A379034                         D2[(i+a,j+b)] += d
%o A379034         D = D2
%o A379034         yield D[(0,0)]
%Y A379034 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).
%K A379034 nonn
%O A379034 0,3
%A A379034 _Ludovic Schwob_, Dec 14 2024