cp's OEIS Frontend

A303285 Number of permutations p of [2n] such that the sequence of ascents and descents of p0 forms a Dyck path.

%I A303285 #41 Nov 02 2018 19:14:02
%S A303285 1,1,8,172,7296,518324,55717312,8460090160,1726791794432,
%T A303285 456440969661508,151770739970889792,62022635037246022000,
%U A303285 30564038464166725328768,17876875858414492985045712,12245573879235563308351042496,9711714975145772145881269175104
%N A303285 Number of permutations p of [2n] such that the sequence of ascents and descents of p0 forms a Dyck path.
%C A303285 Here p is a permutation of 1,2,3,...,2n, and p0 refers to the string p followed by 0.
%C A303285 Also the number of permutations p of [2n] such that the sequence of ascents and descents of 0p forms a Dyck path. a(2) = 8: 1432, 2143, 2431, 3142, 3241, 3421, 4132, 4231.
%C A303285 Also the number of permutations p of [2n] that are of odd order and whose M statistic (as defined in the Spiro paper) is equal to n-1. - _Sam Spiro_, Nov 01 2018
%H A303285 Alois P. Heinz, <a href="/A303285/b303285.txt">Table of n, a(n) for n = 0..200</a>
%H A303285 S. Spiro, <a href="https://arxiv.org/abs/1810.00993">Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic</a>, arXiv:1810.00993 [math.CO], 2018.
%H A303285 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%F A303285 a(n) ~ c * 2^(2*n) * n^(2*n - 1) / exp(2*n), where c = 8.838022110416151362523442920999767406145711133564692... - _Vaclav Kotesovec_, May 22 2018
%F A303285 a(n) = (1/2)*Sum_{k odd} binomial(2*n,k)*A177042((k-1)/2)*A177042((2n-k-1)/2) for n>0. - _Sam Spiro_, Nov 01 2018
%F A303285 a(n) = A321280(2n,n-1) for n >= 1. - _Alois P. Heinz_, Nov 02 2018
%e A303285 a(0) = 1: the empty permutation.
%e A303285 a(1) = 1: 12.
%e A303285 a(2) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
%p A303285 b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p A303285       `if`(t>0,   add(b(u-j, o+j-1, t-1), j=1..u), 0)+
%p A303285       `if`(o+u>t, add(b(u+j-1, o-j, t+1), j=1..o), 0))
%p A303285     end:
%p A303285 a:= n-> b(0, 2*n, 0):
%p A303285 seq(a(n), n=0..20);
%t A303285 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 A303285 a[n_] := b[0, 2n, 0];
%t A303285 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, May 29 2018, from Maple *)
%o A303285 (PARI) \\ here b(n) is A177042
%o A303285 b(n)={if(n==0, 1, 2*sum(k=0, n, (-1)^k*binomial(2*n+1,k)*(n-k+1)^(2*n)));}
%o A303285 a(n)={if(n==0, 1, sum(k=1, n, binomial(2*n, 2*k-1)*b(k-1)*b(n-k))/2);} \\ _Andrew Howroyd_, Nov 01 2018
%Y A303285 Bisection (even part) of A303284.
%Y A303285 Bisection (even part) of A303287.
%Y A303285 Column k=0 of A316728.
%Y A303285 Cf. A177042, A180056, A316727, A321280.
%K A303285 nonn
%O A303285 0,3
%A A303285 _Alois P. Heinz_, Apr 20 2018