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, ...}. - 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
Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, pp. 65-82 of "A Century of Advancing Mathematics", ed. S. F. Kennedy et al., MAA Press 2015.
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..1060
Michael Albert and Mireille Bousquet-Mélou, Permutations sortable by two stacks in parallel and quarter plane walks, arXiv:1312.4487 [math.CO], 2014-2015.
Michael Albert and Mireille Bousquet-Mélou, Permutations sortable by two stacks in parallel and quarter plane walks, European Journal of Combinatorics 43 (2015), 131-164.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
A. Burstein and J. Pantone, Two examples of unbalanced Wilf-equivalence, arXiv preprint arXiv:1402.3842 [math.CO], 2014.
CombOS - Combinatorial Object Server, Generate pattern-avoiding permutations
Andrew R. Conway and Anthony J. Guttmann, On 1324-avoiding permutations, Advances in Applied Mathematics, Volume 64, March 2015, p. 50-69.
Andrew R. Conway and Anthony J. Guttmann, Counting occurrences of patterns in permutations, arXiv:2306.12682 [math.CO], 2023. See p. 18.
Tom Denton, Algebraic and Affine Pattern Avoidance, arXiv preprint arXiv:1303.3767 [math.CO], 2013.
Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, MAA Focus, August/September 2015, pp. 33-34. [Annotated scanned copy]
Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r, arXiv:1504.02513 [math.CO], 2015.
Steven Finch, Pattern-Avoiding Permutations [Cached copy at the Wayback Machine]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
A. L. L. Gao, S. Kitaev, and P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.
O. Guibert and E. Pergola, Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math., Vol. 224 (2000), pp. 281-287.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and 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. 381-407.
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), 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
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
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]
For n > 0, (n+2)^2*a(n) - n^2*a(n-1) = 4*A086618(n). - Zhi-Wei Sun, Nov 16 2017
a(n) = hypergeom([1/2, -1 - n, -n], [2, 2], 4) / (n+1). - Vaclav Kotesovec, Jun 07 2021
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): # Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
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}]
(* Second program:*)
a[0] = a[1] = 1; a[n_] := a[n] = ((10*n^2+2*n-3)*a[n-1] + (-9*n^2+18*n-9)* a[n-2])/(n+2)^2; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 20 2017 *)
Table[HypergeometricPFQ[{1/2, -1 - n, -n}, {2, 2}, 4] / (n+1), {n, 0, 25}] (* Vaclav Kotesovec, Jun 07 2021 *)
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
KEYWORD
nonn,nice
AUTHOR
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