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

1, 1, 1, 4, 8, 60, 172, 1974, 7296, 114972, 518324, 10490392, 55717312, 1384890104, 8460090160, 250150900354, 1726791794432, 59317740001132, 456440969661508, 17886770092245360, 151770739970889792, 6687689652133397064, 62022635037246022000, 3037468107154650475868

Offset

0,4

Links

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

Wikipedia, Counting lattice paths

Formula

a(2n) = A303287(2n).

Example

a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(2) = 1: 21.
a(3) = 4: 132, 213, 231, 312.
a(4) = 8: 1432, 2143, 2431, 3142, 3241, 3421, 4132, 4231.

Maple

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(0, n, 0):
seq(a(n), n=0..25);

Mathematica

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[0, n, 0];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, May 25 2018, translated from Maple *)

Prog

(PARI) b(u, o, t) = if(u+o==0, 1, if(t > 0, sum(j=1, u, b(u-j, o+j-1, t-1)), 0) + if(o+u > t, sum(j=1, o, b(u+j-1, o-j, t+1)), 0))
a(n) = b(0, n, 0) \\ Felix Fröhlich, May 25 2018, adapted from Mathematica

Crossrefs

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

Cf. A180056, A303287.

Sequence in context: A270399 A269998 A335527 * A275574 A214590 A215713

Adjacent sequences: A303281 A303282 A303283 * A303285 A303286 A303287

Keyword

nonn

Author

Alois P. Heinz, Apr 20 2018

Status

approved