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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005802 Number of permutations in S_n with longest increasing subsequence of length <= 3 (i.e. 1234-avoiding permutations); vexillary permutations (i.e. 2143-avoiding).
(Formerly M1666)
19
1, 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, 3763290, 24792705, 167078577, 1148208090, 8026793118, 56963722223, 409687815151, 2981863943718, 21937062144834, 162958355218089, 1221225517285209, 9225729232653663, 70209849031116183, 537935616492552297 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also the dimension of SL(3)-invariants in V^n tensor (V^*)^n, where V is the standard 3-dimensional representation of SL(3) and V^* is its dual. - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

Also the number of doubly-alternating permutations of length 2n with no four-term increasing subsequence (i.e., 1234-avoiding doubly-alternating permutations). The doubly-alternating permutations (counted by sequence A007999) are those permutations w such that both w and w^(-1) have descent set {2, 4, 6, ...}. [From Joel B. Lewis, May 21 2009]

Any permutation without an increasing subsequence of length 4 has a decreasing subsequence of length >= n/3, where n is the length of the sequence, by the Erdős-Szekeres theorem. - Charles R Greathouse IV, Sep 26 2012

Also the number of permutations of length n simultaneously avoiding patterns 1324 and 3416725 (or 1324 and 3612745). - Alexander Burstein, Jan 31 2014

REFERENCES

S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(e), p. 453.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..300

A. Burstein, J. Pantone, Two examples of unbalanced Wilf-equivalence, arXiv preprint arXiv:1402.3842, 2014.

Tom Denton, Algebraic and Affine Pattern Avoidance, arXiv preprint arXiv:1303.3767, 2013

Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.

O. Guibert, E. Pergola, Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math., Vol. 224 (2000), pp. 281-287.

Eric Marberg, Crossings and nestings in colored set partitions, Arxiv preprint arXiv:1203.5738, 2012.

J. Noonan and D. Zeilberger, [math/9808080] The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns

J. Noonan and D. Zeilberger, The Enumeration of Permutations With A Prescribed Number of "Forbidden" Patterns

Erik Ouchterlony, Pattern avoiding doubly alternating permutations [From Joel B. Lewis, May 21 2009]

R. P. Stanley, A combinatorial miscellany

R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.

FORMULA

a(n) = 2 * sum_{k=0..n} binomial(2*k, k) * (binomial(n, k))^2 * (3*k^2+2*k+1-n-2*k*n)/((k+1)^2 * (k+2) * (n-k+1))

(4*n^2 - 2*n + 1)*(n + 2)^2*(n + 1)^2*a(n) = (44*n^3 - 14*n^2 - 11*n + 8)*n*(n + 1)^2*a(n - 1) - (76*n^4 + 42*n^3 - 49*n^2 - 24*n + 24)*(n - 1)^2*a(n - 2) + 9*(4*n^2 + 6*n + 3)*(n - 1)^2*(n - 2)^2*a(n - 3). - Vladeta Jovovic, Jul 16 2004

a(0) = 1, a(1) = 1, (n^2 + 8 n + 16) a(n + 2) = (10 n^2 + 42 n + 41) a(n + 1) - (9 n^2 + 18 n + 9) a(n). - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

a(n) = ((18*n+45)*A002893(n) - (7+2*n)*A002893(n+1)) / (6*(n+2)^2). - Mark van Hoeij, Jul 02 2010

G.f.:  (1+5*x-(1-9*x)^(3/4)*(1-x)^(1/4)*hypergeom([-1/4, 3/4],[1],64*x/((x-1)*(1-9*x)^3)))/(6*x^2). - Mark van Hoeij, Oct 25 2011.

a(n) ~ 3^(2*n+9/2)/(16*Pi*n^4). - Vaclav Kotesovec, Jul 29 2013

MAPLE

a:= n-> 2*add(binomial(2*k, k)*(binomial(n, k))^2*(3*k^2+2*k+1-n-2*k*n)/ (k+1)^2/(k+2)/(n-k+1), k=0..n);

A005802:=rsolve({a(0) = 1, a(1) = 1, (n^2 + 8*n + 16)*a(n + 2) = (10*n^2 + 42*n + 41)*a(n + 1) - (9*n^2 + 18*n + 9)*a(n)}, a(n), makeproc): # Mihailovs

MATHEMATICA

a[n_] := 2Sum[Binomial[2k, k]Binomial[n, k]^2(3k^2+2k+1-n-2k*n)/((k+1)^2(k+2)(n-k+1)), {k, 0, n}]

PROG

(PARI) a(n)=2*sum(k=0, n, binomial(2*k, k)*binomial(n, k)^2*(3*k^2+2*k+1-n-2*k*n)/(k+1)^2/(k+2)/(n-k+1)) \\ Charles R Greathouse IV, Sep 26 2012

CROSSREFS

A column of A047888. See also A224318, A223034, A223905.

Sequence in context: A022558 A004040 A216040 * A061552 A053488 A117106

Adjacent sequences:  A005799 A005800 A005801 * A005803 A005804 A005805

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane, Simon Plouffe

EXTENSIONS

Additional comments from Emeric Deutsch, Dec 06 2000

More terms from Naohiro Nomoto, Jun 18 2001

Edited by Dean Hickerson (dean.hickerson(AT)yahoo.com), Dec 10 2002

More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 17 18:08 EDT 2014. Contains 240655 sequences.