cp's OEIS Frontend

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.

%I A303284 #17 May 25 2018 08:59:14
%S A303284 1,1,1,4,8,60,172,1974,7296,114972,518324,10490392,55717312,
%T A303284 1384890104,8460090160,250150900354,1726791794432,59317740001132,
%U A303284 456440969661508,17886770092245360,151770739970889792,6687689652133397064,62022635037246022000,3037468107154650475868
%N 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.
%H A303284 Alois P. Heinz, <a href="/A303284/b303284.txt">Table of n, a(n) for n = 0..400</a>
%H A303284 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%F A303284 a(2n) = A303287(2n).
%e A303284 a(0) = 1: the empty permutation.
%e A303284 a(1) = 1: 1.
%e A303284 a(2) = 1: 21.
%e A303284 a(3) = 4: 132, 213, 231, 312.
%e A303284 a(4) = 8: 1432, 2143, 2431, 3142, 3241, 3421, 4132, 4231.
%p A303284 b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p A303284       `if`(t>0,   add(b(u-j, o+j-1, t-1), j=1..u), 0)+
%p A303284       `if`(o+u>t, add(b(u+j-1, o-j, t+1), j=1..o), 0))
%p A303284     end:
%p A303284 a:= n-> b(0, n, 0):
%p A303284 seq(a(n), n=0..25);
%t A303284 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 A303284 a[n_] := b[0, n, 0];
%t A303284 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, May 25 2018, translated from Maple *)
%o A303284 (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))
%o A303284 a(n) = b(0, n, 0) \\ _Felix Fröhlich_, May 25 2018, adapted from Mathematica
%Y A303284 Bisections give: A303285 (even part), A303286 (odd part).
%Y A303284 Cf. A180056, A303287.
%K A303284 nonn
%O A303284 0,4
%A A303284 _Alois P. Heinz_, Apr 20 2018