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).

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

Offset: 1

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

Keywords

• nonn

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

Examples

			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.
From _Andrew Howroyd_, Jun 07 2021: (Start)
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)
		

Links

• Taras Goy and Mark Shattuck, Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries, Carpathian Math. Publ., Vol. 15 (2023), No. 2, 420-436. See Theorem 3.

Crossrefs

Cf. A000108.

Programs

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:
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 07 2021

Mathematica

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

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

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)).

Extensions

Offset, a(15), a(18) corrected by and more terms from Georg Fischer, Jun 07 2021