|
%I #22 May 25 2018 06:00:17
%S 1,1,1,2,8,22,172,604,7296,31238,518324,2620708,55717312,325024572,
%T 8460090160,55942352184,1726791794432,12765597850950,456440969661508,
%U 3730771315561300,151770739970889792,1359124435588313876,62022635037246022000,603916464771468176392
%N 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.
%H Alois P. Heinz, <a href="/A303287/b303287.txt">Table of n, a(n) for n = 0..400</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%F a(2n) = A303284(2n).
%e a(0) = 1: the empty permutation.
%e a(1) = 1: 1.
%e a(2) = 1: 12.
%e a(3) = 2: 132, 231.
%e a(4) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
%e 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.
%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p `if`(t>0, add(b(u-j, o+j-1, t-1), j=1..u), 0)+
%p `if`(o+u>t, add(b(u+j-1, o-j, t+1), j=1..o), 0))
%p end:
%p a:= n-> b(n, 0, 1):
%p seq(a(n), n=0..25);
%t 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]];
%t a[n_] := b[n, 0, 1];
%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, May 25 2018, translated from Maple *)
%Y Bisections give: A303285 (even part), A177042 (odd part).
%Y Cf. A180056, A304001, A303284, A304777, A304778.
%K nonn
%O 0,4
%A _Alois P. Heinz_, Apr 20 2018
|
