A304778 -id:A304778 - cp's OEIS frontend

A303287 Number of permutations p of [n] such that the sequence of ascents and descents of p or of p0 (if n is even) forms a Dyck path.

1, 1, 1, 2, 8, 22, 172, 604, 7296, 31238, 518324, 2620708, 55717312, 325024572, 8460090160, 55942352184, 1726791794432, 12765597850950, 456440969661508, 3730771315561300, 151770739970889792, 1359124435588313876, 62022635037246022000, 603916464771468176392

Offset: 0

Alois P. Heinz, Apr 20 2018

nonn

			a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(2) = 1: 12.
a(3) = 2: 132, 231.
a(4) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
a(5) = 22: 12543, 13254, 13542, 14253, 14352, 14532, 15243, 15342, 23154, 23541, 24153, 24351, 24531, 25143, 25341, 34152, 34251, 34521, 35142, 35241, 45132, 45231.

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

Bisections give: A303285 (even part), A177042 (odd part).

Cf. A180056, A304001, A303284, A304777, A304778.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t>0,   add(b(u-j, o+j-1, t-1), j=1..u), 0)+
      `if`(o+u>t, add(b(u+j-1, o-j, t+1), j=1..o), 0))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..25);

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t > 0, Sum[b[u - j, o + j - 1, t - 1], {j, 1, u}], 0] + If[o + u > t, Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}], 0]];
a[n_] := b[n, 0, 1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, May 25 2018, translated from Maple *)

a(2n) = A303284(2n).

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.

Original entry on oeis.org

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

Alois P. Heinz, May 18 2018

nonn

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

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

Cf. A303287, A304778.

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

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

cp's OEIS Frontend

A303287 Number of permutations p of [n] such that the sequence of ascents and descents of p or of p0 (if n is even) forms a Dyck path.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula