A287963 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has one or two peaks.

1, 1, 1, 2, 5, 10, 28, 71, 194, 532, 1495, 4256, 12176, 35251, 102664, 300260, 881909, 2599948, 7688164, 22788527, 67676144, 201308938, 599676445, 1788564038, 5339905904, 15956230705, 47713265536, 142763240666, 427390085963, 1280058256294, 3835332884686

Offset

0,4

Links

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

Wikipedia, Counting lattice paths

Example

. a(3) = 2:     /\      /\
.            /\/  \    /  \/\  .
.
. a(4) = 5:      /\      /\        /\/\    /\        /\/\
.           /\/\/  \  /\/  \/\  /\/    \  /  \/\/\  /    \/\ .

Maple

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

Mathematica

b[n_, j_] := b[n, j] = If[n == j, 1, Sum[b[n - j, i]*i*(Binomial[j - 1, i - 2] + (i - 1)/2*Binomial[j - 1, i - 3]), {i, 2, Min[j + 3, n - j]}]];
a[n_] := If[n == 0, 1, b[n, 1] + b[n, 2]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, May 29 2018, from Maple *)

Crossrefs

Cf. A000108, A281874, A287843, A287845, A287846.

Sequence in context: A370316 A257889 A363388 * A006401 A283460 A102964

Adjacent sequences: A287960 A287961 A287962 * A287964 A287965 A287966

Keyword

nonn

Author

Alois P. Heinz, Jun 03 2017

Status

approved