login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)=2b(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)+2b(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

LINKS

Table of n, a(n) for n=1..30.

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.

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)

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

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

Cf. A000108.

Sequence in context: A293809 A307976 A114495 * A151439 A204218 A007141

Adjacent sequences:  A137395 A137396 A137397 * A137399 A137400 A137401

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 22 21:29 EDT 2021. Contains 345393 sequences. (Running on oeis4.)