A304777 -id:A304777 - 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).

A304778 Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 9, 15, 23, 38, 62, 100, 163, 267, 441, 725, 1198, 1986, 3291, 5472, 9116, 15204, 25399, 42494, 71183, 119396, 200507, 337090, 567318, 955749, 1611672, 2720212, 4595198, 7768975, 13145109, 22258264, 37716358, 63953853, 108515011

Offset: 0

Alois P. Heinz, May 18 2018

nonn

			a(6) = 4: 132, 141, 231, 6.
a(7) = 6: 12121, 142, 151, 232, 241, 7.
a(8) = 9: 12131, 13121, 143, 152, 161, 242, 251, 341, 8.
a(9) = 15: 12132, 12141, 12321, 13131, 14121, 153, 162, 171, 23121, 243, 252, 261, 342, 351, 9.

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

Cf. A003242, A303287, A304777.

b:= proc(n, l, c) option remember; `if`(c<0 and l>0, 0,
      `if`(n=0, `if`(l<0 or c=0, 1, 0), add(`if`(i=l, 0,
       b(n-i, i, c+`if`(i>l, 1, -1))), i=1..n)))
    end:
a:= n-> b(n, -1$2):
seq(a(n), n=0..50);

b[n_, l_, c_] := b[n, l, c] = If[c<0 && l>0, 0, If[n==0, If[l<0 || c==0, 1, 0], Sum[If[i==l, 0, b[n-i, i, c + If[i>l, 1, -1]]], {i, 1, n}]]];
a[n_] := b[n, -1, -1];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 31 2018, from Maple *)

a(n) ~ c * d^n / n^(3/2), where d = A241902 = 1.7502412917183090312497386246... and c = 7.0142545527132612683043468956... - Vaclav Kotesovec, May 22 2018

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