login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A029759 Number of permutations which are the union of an increasing and a decreasing subsequence. 3
1, 1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, 71429176, 278586182, 1087537414, 4249391468, 16618640836, 65048019092, 254814326164, 998953992728, 3919041821896, 15385395144092, 60438585676636 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Michael H. Albert, M. D. Atkinson, Mathilde Bouvel, Nik Ruškuc, Vincent Vatter, Geometric grid classes of permutations, arXiv:1108.6319 [math.CO], 2011-2012.

M. H. Albert and V. Vatter, Generating and enumerating 321-avoiding and skew-merged simple permutations, arXiv preprint arXiv:1301.3122 [math.CO], 2013. - N. J. A. Sloane, Feb 11 2013

M. D. Atkinson, Permutations which are the union of an increasing and a decreasing subsequence, Electronic Journal of Combinatorics, R6 of Volume 5(1), 1998.

E. Rowland, R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635 [math.NT], 2013.

Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

Wikipedia, Permutation classes avoiding two patterns of length 4.

FORMULA

G.f.: (1-3*x)/((1-2*x)*sqrt(1-4*x)). - Vincent Vatter, Jun 21 2011

n*a(n) +(-9*n+8)*a(n-1) +2*(13*n-23)*a(n-2) +12*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Aug 24 2013

a(n) ~ 2^(2*n-1)/sqrt(Pi*n). - Vaclav Kotesovec, Mar 18 2014

a(n) = (binomial(2*n, n)*(hypergeom([1, n+1/2], [n+1], 2) + 2) + i*2^n)/2, where i is the imaginary unit. - Peter Luschny, Oct 25 2018

MAPLE

f := n->binomial(2*n, n)-sum( 2^(n-m-1)*binomial(2*m, m), m=0.. n-1 );

MATHEMATICA

CoefficientList[Series[(1 - 3 x) / ((1 - 2 x) Sqrt[1 - 4 x]), {x, 0, 60}], x] (* Vincenzo Librandi, Aug 25 2013 *)

CROSSREFS

Cf. A220589.

Sequence in context: A165530 A116707 A116704 * A150255 A107243 A107244

Adjacent sequences:  A029756 A029757 A029758 * A029760 A029761 A029762

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 07:10 EST 2018. Contains 317258 sequences. (Running on oeis4.)