login
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.
8
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,4
LINKS
FORMULA
a(2n) = A303284(2n).
EXAMPLE
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.
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(n, 0, 1):
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[n, 0, 1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, May 25 2018, translated from Maple *)
CROSSREFS
Bisections give: A303285 (even part), A177042 (odd part).
Sequence in context: A191643 A151356 A238530 * A321068 A158466 A065694
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Apr 20 2018
STATUS
approved