

A005802


Number of permutations in S_n with longest increasing subsequence of length <= 3 (i.e., 1234avoiding permutations); vexillary permutations (i.e., 2143avoiding).
(Formerly M1666)


24



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 3dimensional representation of SL(3) and V^* is its dual.  Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
Also the number of doublyalternating permutations of length 2n with no fourterm increasing subsequence (i.e., 1234avoiding doublyalternating permutations). The doublyalternating permutations (counted by sequence A007999) are those permutations w such that both w and w^(1) have descent set {2, 4, 6, ...}.  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ősSzekeres 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
For any integer n > 0, we have (n+2)^2*a(n)  n^2*a(n1} = 4*A086618(n).  ZhiWei Sun, Nov 16 2017


REFERENCES

Eric S. Egge, Defying God: The StanleyWilf Conjecture, StanleyWilf Limits, and a TwoGeneration Explosion of Combinatorics, pp. 6582 of "A Century of Advancing Mathematics", ed. S. F. Kennedy et al., MAA Press 2015.
S. Kitaev, Patterns in Permutations and Words, SpringerVerlag, 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..1060
Michael Albert and Mireille BousquetMélou, Permutations sortable by two stacks in parallel and quarter plane walks, arXiv:1312.4487 [math.CO], 20142015.
Michael Albert and Mireille BousquetMélou, Permutations sortable by two stacks in parallel and quarter plane walks, European Journal of Combinatorics 43 (2015), 131164.
A. Burstein and J. Pantone, Two examples of unbalanced Wilfequivalence, arXiv preprint arXiv:1402.3842 [math.CO], 2014.
Tom Denton, Algebraic and Affine Pattern Avoidance, arXiv preprint arXiv:1303.3767 [math.CO], 2013.
Eric S. Egge, Defying God: The StanleyWilf Conjecture, StanleyWilf Limits, and a TwoGeneration Explosion of Combinatorics, MAA Focus, August/September 2015, pp. 3334. [Annotated scanned copy]
Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, The number of 1...davoiding permutations of length d+r for SYMBOLIC d but numeric r, arXiv:1504.02513 [math.CO], 2015.
Steven Finch, PatternAvoiding Permutations [Broken link?]
Steven Finch, PatternAvoiding Permutations [Cached copy, with permission]
A. L. L. Gao, S. Kitaev, P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Ira M. Gessel, Symmetric functions and Precursiveness, J. Combin. Theory A 53 (1990), 257285.
O. Guibert and E. Pergola, Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math., Vol. 224 (2000), pp. 281287.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
J. Noonan and D. Zeilberger, 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, Advances in Applied Mathematics, Vol. 17, 1996, pp. 381407.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns, arXiv:math/9808080 [math.CO], 1998.
Erik Ouchterlony, Pattern avoiding doubly alternating permutations
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
Anders Bjorner and Richard P. Stanley, A combinatorial miscellany
R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 5568.


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) * (nk+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(19*x)^(3/4)*(1x)^(1/4)*hypergeom([1/4, 3/4],[1],64*x/((x1)*(19*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
a(n) = Sum_{k=0..n} binomial(2k,k)*binomial(n+1,k+1)*binomial(n+2,k+1)/((n+1)^2*(n+2)). [Conway and Guttmann, Adv. Appl. Math. 64 (2015) 50]


MAPLE

a:= n> 2*add(binomial(2*k, k)*(binomial(n, k))^2*(3*k^2+2*k+1n2*k*n)/ (k+1)^2/(k+2)/(nk+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): # Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005


MATHEMATICA

a[n_] := 2Sum[Binomial[2k, k]Binomial[n, k]^2(3k^2+2k+1n2k*n)/((k+1)^2(k+2)(nk+1)), {k, 0, n}]
(* Second program:*)
a[0] = a[1] = 1; a[n_] := a[n] = ((10*n^2+2*n3)*a[n1] + (9*n^2+18*n9)* a[n2])/(n+2)^2; Table[a[n], {n, 0, 25}] (* JeanFrançois Alcover, Feb 20 2017 *)


PROG

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


CROSSREFS

A column of A047888. See also A224318, A223034, A223905.
Column k=3 of A214015.
A005802, A022558, A061552 are representatives for the three Wilf classes for lengthfour avoiding permutations (cf. A099952).
Sequence in context: A022558 A004040 A216040 * A061552 A263778 A053488
Adjacent sequences: A005799 A005800 A005801 * A005803 A005804 A005805


KEYWORD

nonn,nice,changed


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, Dec 10 2002
More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005


STATUS

approved



