A288743 Number of Dyck paths of semilength n such that the maximal number of peaks per level equals two.

1, 1, 7, 18, 59, 193, 616, 1955, 6244, 19926, 63490, 202068, 642816, 2044571, 6502193, 20673020, 65714586, 208870774, 663868055, 2109997964, 6706282384, 21315049217, 67748772174, 215343287489, 684507346839, 2175916952697, 6917096914771, 21989855308501

Offset

2,3

Links

Alois P. Heinz, Table of n, a(n) for n = 2..1000

Wikipedia, Counting lattice paths

Example

. a(4) = 7:       /\      /\        /\/\    /\        /\  /\
.            /\/\/  \  /\/  \/\  /\/    \  /  \/\/\  /  \/  \ .
.
.                        /\/\
.             /\/\      /    \
.            /    \/\  /      \  .

Maple

b:= proc(n, k, j) option remember; `if`(j=n, 1, add(
      b(n-j, k, i)*add(binomial(i, m)*binomial(j-1, i-1-m),
       m=max(0, i-j)..min(k, i-1)), i=1..min(j+k, n-j)))
    end:
g:= proc(n, k) option remember; add(b(n, k, j), j=1..k) end:
a:= n-> g(n, 2)-g(n, 1):
seq(a(n), n=2..35);

Mathematica

b[n_, k_, j_]:=b[n, k, j]=If[j==n, 1, Sum[b[n - j, k, i] Sum[Binomial[i, m] Binomial[j - 1, i - 1 - m], {m, Max[0, i - j], Min[k, i - 1]}], {i, Min[j + k, n - j]}]]; g[n_, k_]:=Sum[b[n, k, j], {j, k}]; Table[g[n, 2] - g[n, 1], {n, 2, 35}] (* Indranil Ghosh, Aug 09 2017 *)

Prog

(Python)
from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def b(n, k, j): return 1 if j==n else sum(b(n - j, k, i)*sum(binomial(i, m)*binomial(j - 1, i - 1 - m) for m in range(max(0, i - j), min(k, i - 1) + 1)) for i in range(1, min(j + k, n - j) + 1))
def g(n, k): return sum(b(n, k, j) for j in range(1, k + 1))
def a(n): return g(n, 2) - g(n, 1)
print([a(n) for n in range(2, 36)]) # Indranil Ghosh, Aug 09 2017

Crossrefs

Column k=2 of A287822.

Cf. A000108.

Sequence in context: A346494 A220031 A197092 * A223240 A304142 A019534

Adjacent sequences: A288740 A288741 A288742 * A288744 A288745 A288746

Keyword

nonn

Author

Alois P. Heinz, Jun 14 2017

Status

approved