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,6

Links

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

Wikipedia, Counting lattice paths

Example

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).

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 *)

Crossrefs

Cf. A303287, A304778.

Sequence in context: A231577 A325590 A277210 * A058762 A241314 A276056

Adjacent sequences: A304774 A304775 A304776 * A304778 A304779 A304780

Keyword

nonn

Author

Alois P. Heinz, May 18 2018

Status

approved