A287901 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has at least one peak.

1, 1, 1, 3, 6, 17, 49, 147, 459, 1476, 4856, 16282, 55466, 191474, 668510, 2356944, 8380944, 30025814, 108289093, 392871484, 1432934360, 5251507624, 19329771911, 71430479820, 264914270527, 985737417231, 3679051573264, 13769781928768, 51670641652576

Offset

0,4

Links

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

Wikipedia, Counting lattice paths

Example

. a(3) = 3:
.                   /\      /\
.      /\/\/\    /\/  \    /  \/\ .
.
. a(4) = 6:
.                    /\      /\        /\/\    /\        /\/\
.     /\/\/\/\  /\/\/  \  /\/  \/\  /\/    \  /  \/\/\  /    \/\ .

Mathematica

b[n_, k_, j_]:=b[n, k, j]=If[j==n, 1, Sum[Sum[Binomial[i, m] Binomial[j - 1, i - 1 - m], {m, Max[k, i - j], i - 1}] b[n - j, k, i], {i, n - j}]];  a[n_]:=If[n==0, 1, Sum[b[n, 1, j], {j, n}]]; Table[a[n], {n, 0, 30}] (* 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([sum([binomial(i, m)*binomial(j - 1, i - 1 - m) for m in range(max(k, i - j), i)])*b(n - j, k, i) for i in range(1, n - j + 1)])
def a(n): return 1 if n==0 else sum([b(n, 1, j) for j in range(1, n + 1)])
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 09 2017

Crossrefs

Column k=1 of A288386.

Cf. A000108, A281874, A287846.

Sequence in context: A204517 A307685 A360273 * A354878 A143093 A117712

Adjacent sequences: A287898 A287899 A287900 * A287902 A287903 A287904

Keyword

nonn

Author

Alois P. Heinz, Jun 02 2017

Status

approved