# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a137398
Showing 1-1 of 1

%I A137398 #28 Nov 25 2021 05:00:17
%S A137398 0,1,2,7,22,74,252,875,3078,10950,39316,142278,518364,1899668,6997688,
%T A137398 25894579,96211398,358779118,1342323364,5037146738,18953759988,
%U A137398 71497359884,270321915848,1024217489278,3888253473180,14787937448380,56337410614088,214967841333868,821473056041464,3143521372849960
%N A137398 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 A137398 The sequence occurs as the diagonal of the triangle below.
%C A137398   0;
%C A137398   0,   1;
%C A137398   0,   1,   2;
%C A137398   0,   1,   3,   7;
%C A137398   0,   1,   4,  11,  22;
%C A137398   0,   1,   5,  16,  38,  74;
%C A137398   0,   1,   6,  22,  60, 134, 252;
%C A137398   0,   1,   7,  29,  89, 223, 475, 875;
%C A137398 The triangle is generated by:
%C A137398 b(n,0) = 0;
%C A137398 b(n,1) = 1;
%C A137398 b(n,k) = 2*b(k-2,k-2) + Sum_{i=k-1..n} b(i,k-1) for 2 <= k <= n;
%C A137398 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 A137398 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 A137398 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 A137398 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 A137398 G.f.: 2*x^2 / (1 - 2*x - 4*x^2 + sqrt(1 - 4*x)).
%e A137398 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 A137398 From _Andrew Howroyd_, Jun 07 2021: (Start)
%e A137398 The a(2) = 1 p/q subsequences of 1234 are 12/34.
%e A137398 The a(3) = 2 p/q subsequences of 123456 are 123/456, 124/356.
%e A137398 (End)
%p A137398 a:= proc(n) option remember; `if`(n<3, n-1, 2*(a(n-1)+a(n-2))+
%p A137398       add(binomial(2*i, i+1)/i*a(n-i-1), i=1..n-3))
%p A137398     end:
%p A137398 seq(a(n), n=1..30);  # _Alois P. Heinz_, Jun 07 2021
%t A137398 CoefficientList[Series[2x / (1 - 2*x - 4*x^2 + Sqrt[1 - 4*x]), {x, 0, 40}], x] (* _Georg Fischer_, Jun 07 2021 *)
%o A137398 (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 A137398 Cf. A000108.
%K A137398 nonn
%O A137398 1,3
%A A137398 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 A137398 Offset, a(15), a(18) corrected by and more terms from _Georg Fischer_, Jun 07 2021

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE