%I #28 Nov 25 2021 05:00:17

%S 0,1,2,7,22,74,252,875,3078,10950,39316,142278,518364,1899668,6997688,

%T 25894579,96211398,358779118,1342323364,5037146738,18953759988,

%U 71497359884,270321915848,1024217489278,3888253473180,14787937448380,56337410614088,214967841333868,821473056041464,3143521372849960

%N Let S be a strictly monotonic sequence of length 2n and let p and q be subsequences of S each of length n such that the least element belongs to p and every element of S belongs to either p or q. The number of ways to select p such that for any index i the exchange of p(i) and q(i) makes at least one of p and q non-monotonic, is given by a(n).

%C The sequence occurs as the diagonal of the triangle below.

%C 0;

%C 0, 1;

%C 0, 1, 2;

%C 0, 1, 3, 7;

%C 0, 1, 4, 11, 22;

%C 0, 1, 5, 16, 38, 74;

%C 0, 1, 6, 22, 60, 134, 252;

%C 0, 1, 7, 29, 89, 223, 475, 875;

%C The triangle is generated by:

%C b(n,0) = 0;

%C b(n,1) = 1;

%C b(n,k) = 2*b(k-2,k-2) + Sum_{i=k-1..n} b(i,k-1) for 2 <= k <= n;

%C or alternatively, for 2 <= k < n either b(n,k) = b(n,k-1) + b(n-1,k) or b(n,k) = Sum_{i=1..k} b(n-1,i) and b(n,n) = b(n-1,n-1) + 2*b(n-2,n-2) + b(n,n-1).

%C Let g(x) = 1/(1-2x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction). Then g.f. appears to be g(x)-1. - _Paul Barry_, Jan 22 2009

%C With offset 1, a(n) is the number of (2n)-step Grand Dyck paths (consisting of n upsteps U = (1,1) and n downsteps D = (1,-1), hence counted by central binomial coefficients A000984), that start with an upstep and have no peak vertex at height 1 nor valley vertex at height -1. For example, a(3) = 2 counts UUUDDD, UUDUDD, and a(4) = 7 counts UUUUDDDD, UUUDUDDD, UUUDDUDD, UUDUUDDD, UUDUDUDD, UUDDUUDD, UUDDDDUU. The generating function F = F(x) for such paths satisfies the equation: F = x*(C-1) + 2*x*(C-1)*F, where C = C(x) is the g.f. for Dyck paths A000108 (consider the first return to ground level). - _David Callan_, Nov 25 2021

%F a(1)=0, a(2)=1, a(3)=2, a(n) = 2*a(n-1) + 2*a(n-2) + Sum_{k=1..n-3} C(k)*a(n-k-1), where C(k) is the k-th Catalan number.

%F G.f.: 2*x^2 / (1 - 2*x - 4*x^2 + sqrt(1 - 4*x)).

%e a(6) = 74 = 2*a(5) + 2*a(4) + c(1)*a(4) + c(2)*a(3) + c(3)*a(2) = 2(22) + 2(7) + 1(7) + 2(2) + 5(1) = 44 + 14 + 7 + 4 + 5.

%e From _Andrew Howroyd_, Jun 07 2021: (Start)

%e The a(2) = 1 p/q subsequences of 1234 are 12/34.

%e The a(3) = 2 p/q subsequences of 123456 are 123/456, 124/356.

%e (End)

%p a:= proc(n) option remember; `if`(n<3, n-1, 2*(a(n-1)+a(n-2))+

%p add(binomial(2*i, i+1)/i*a(n-i-1), i=1..n-3))

%p end:

%p seq(a(n), n=1..30); # _Alois P. Heinz_, Jun 07 2021

%t CoefficientList[Series[2x / (1 - 2*x - 4*x^2 + Sqrt[1 - 4*x]), {x, 0, 40}], x] (* _Georg Fischer_, Jun 07 2021 *)

%o (PARI) seq(n)={Vec(2/(1 - 2*x - 4*x^2 + sqrt(1 - 4*x + O(x^(n-1)))), -n)} \\ _Andrew Howroyd_, Jun 07 2021

%Y Cf. A000108.

%K nonn

%O 1,3

%A Gordon Beavers (gordonb(AT)uark.edu), G. Starling (starling(AT)uark.edu) and W. Li (wingning(AT)uark.edu), Apr 11 2008, May 15 2008

%E Offset, a(15), a(18) corrected by and more terms from _Georg Fischer_, Jun 07 2021