A304777 Number of partitions p of n such that the sequence of level steps (when interpreted as ascents) and descents of p forms a Dyck path.

1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 3, 4, 3, 6, 5, 7, 5, 9, 10, 12, 10, 15, 13, 18, 19, 27, 20, 30, 30, 40, 40, 52, 48, 61, 61, 77, 79, 100, 99, 124, 129, 150, 150, 200, 199, 240, 249, 294, 303, 363, 369, 441, 484, 550, 569, 686, 716, 817, 885, 1003, 1065

Offset: 0

Author

Alois P. Heinz, May 18 2018

Keywords

• nonn

Examples

			a(5) = 2: 221, 5.
a(11) = 4: 33221, 443, 551, (11).
a(12) = 3: 33321, 552, (12).
a(15) = 6: 44331, 44421, 55221, 663, 771, (15).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Wikipedia, Counting lattice paths

Crossrefs

Cf. A303287, A304778.

Programs

Maple

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

Mathematica

b[n_, i_, c_] := b[n, i, c] = If[n == 0, If[c == 0, 1, 0], If[Min[i, c] < 1, 0, Sum[b[n - i*j, i - 1, If[j == 0, c, c + j - 2]], {j, 0, n/i}]]];
a[n_] := If[n == 0, 1, b[n, n, 1]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 28 2018, from Maple *)