|
| |
|
|
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).
|
|
2
|
|
|
|
0, 1, 2, 7, 22, 74, 252, 875, 3078, 10950, 39316, 142278, 518364, 1899668, 6997688, 25894579, 96211398, 358779118, 1342323364, 5037146738, 18953759988, 71497359884, 270321915848, 1024217489278, 3888253473180, 14787937448380, 56337410614088, 214967841333868, 821473056041464, 3143521372849960
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
The sequence occurs as the diagonal of the triangle below.
0;
0, 1;
0, 1, 2;
0, 1, 3, 7;
0, 1, 4, 11, 22;
0, 1, 5, 16, 38, 74;
0, 1, 6, 22, 60, 134, 252;
0, 1, 7, 29, 89, 223, 475, 875;
The triangle is generated by:
b(n,0) = 0;
b(n,1) = 1;
b(n,k) = 2*b(k-2,k-2) + Sum_{i=k-1..n} b(i,k-1) for 2 <= k <= n;
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).
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
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
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.
G.f.: 2*x^2 / (1 - 2*x - 4*x^2 + sqrt(1 - 4*x)).
|
|
|
EXAMPLE
|
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.
The a(2) = 1 p/q subsequences of 1234 are 12/34.
The a(3) = 2 p/q subsequences of 123456 are 123/456, 124/356.
(End)
|
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<3, n-1, 2*(a(n-1)+a(n-2))+
add(binomial(2*i, i+1)/i*a(n-i-1), i=1..n-3))
end:
|
|
|
MATHEMATICA
|
CoefficientList[Series[2x / (1 - 2*x - 4*x^2 + Sqrt[1 - 4*x]), {x, 0, 40}], x] (* Georg Fischer, Jun 07 2021 *)
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
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
|
|
|
EXTENSIONS
|
Offset, a(15), a(18) corrected by and more terms from Georg Fischer, Jun 07 2021
|
|
|
STATUS
|
approved
|
| |
|
|
