|
%I M1666 #157 Jun 27 2023 11:01:23
%S 1,1,2,6,23,103,513,2761,15767,94359,586590,3763290,24792705,
%T 167078577,1148208090,8026793118,56963722223,409687815151,
%U 2981863943718,21937062144834,162958355218089,1221225517285209,9225729232653663,70209849031116183,537935616492552297
%N Number of permutations in S_n with longest increasing subsequence of length <= 3 (i.e., 1234-avoiding permutations); vexillary permutations (i.e., 2143-avoiding).
%C 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
%C 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
%C 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
%C Also the number of permutations of length n simultaneously avoiding patterns 1324 and 3416725 (or 1324 and 3612745). - _Alexander Burstein_, Jan 31 2014
%C For any integer n > 0, we have (n+2)^2*a(n) - n^2*a(n-1} = 4*A086618(n). - _Zhi-Wei Sun_, Nov 16 2017
%D 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.
%D S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(e), p. 453.
%H Alois P. Heinz, <a href="/A005802/b005802.txt">Table of n, a(n) for n = 0..1060</a>
%H Michael Albert and Mireille Bousquet-Mélou, <a href="https://arxiv.org/abs/1312.4487">Permutations sortable by two stacks in parallel and quarter plane walks</a>, arXiv:1312.4487 [math.CO], 2014-2015.
%H Michael Albert and Mireille Bousquet-Mélou, <a href="https://doi.org/10.1016/j.ejc.2014.08.024">Permutations sortable by two stacks in parallel and quarter plane walks</a>, European Journal of Combinatorics 43 (2015), 131-164.
%H Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.
%H A. Burstein and J. Pantone, <a href="https://arxiv.org/abs/1402.3842">Two examples of unbalanced Wilf-equivalence</a>, arXiv preprint arXiv:1402.3842 [math.CO], 2014.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/jump">Generate pattern-avoiding permutations</a>
%H Andrew R. Conway and Anthony J. Guttmann, <a href="https://doi.org/10.1016/j.aam.2014.12.004">On 1324-avoiding permutations</a>, Advances in Applied Mathematics, Volume 64, March 2015, p. 50-69.
%H Andrew R. Conway and Anthony J. Guttmann, <a href="https://arxiv.org/abs/2306.12682">Counting occurrences of patterns in permutations</a>, arXiv:2306.12682 [math.CO], 2023. See p. 18.
%H Tom Denton, <a href="https://arxiv.org/abs/1303.3767">Algebraic and Affine Pattern Avoidance</a>, arXiv preprint arXiv:1303.3767 [math.CO], 2013.
%H Eric S. Egge, <a href="/A000139/a000139.pdf">Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics</a>, MAA Focus, August/September 2015, pp. 33-34. [Annotated scanned copy]
%H Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, <a href="https://arxiv.org/abs/1504.02513">The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r</a>, arXiv:1504.02513 [math.CO], 2015.
%H Steven Finch, <a href="https://web.archive.org/web/20160511035941/http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a> [Cached copy at the Wayback Machine]
%H Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a> [Cached copy, with permission]
%H A. L. L. Gao, S. Kitaev, and P. B. Zhang, <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.
%H Ira M. Gessel, <a href="https://doi.org/10.1016/0097-3165(90)90060-A">Symmetric functions and P-recursiveness</a>, J. Combin. Theory A 53 (1990), 257-285.
%H O. Guibert and E. Pergola, <a href="https://doi.org/10.1016/S0012-365X(00)00139-4">Enumeration of vexillary involutions which are equal to their mirror/complement</a>, Discrete Math., Vol. 224 (2000), pp. 281-287.
%H Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.
%H Eric Marberg, <a href="https://arxiv.org/abs/1203.5738">Crossings and nestings in colored set partitions</a>, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
%H J. Noonan and D. Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/forbid.pdf">The Enumeration of Permutations With A Prescribed Number of "Forbidden" Patterns</a>.
%H J. Noonan and D. Zeilberger, <a href="https://doi.org/10.1006/aama.1996.0016">The Enumeration of Permutations With A Prescribed Number of "Forbidden" Patterns</a>, Advances in Applied Mathematics, Vol. 17, 1996, pp. 381-407.
%H J. Noonan and D. Zeilberger, <a href="https://arxiv.org/abs/math/9808080">The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns</a>, arXiv:math/9808080 [math.CO], 1998.
%H Erik Ouchterlony, <a href="http://garsia.math.yorku.ca/fpsac06/papers/83.pdf">Pattern avoiding doubly alternating permutations</a>
%H Nathaniel Shar, <a href="https://doi.org/10.7282/T3BK1FKF">Experimental methods in permutation patterns and bijective proof</a>, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
%H Anders Bjorner and Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>
%H R. P. Stanley, <a href="https://doi.org/10.1090/S0273-0979-02-00966-7">Recent Progress in Algebraic Combinatorics</a>, Bull. Amer. Math. Soc., 40 (2003), 55-68.
%F 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)).
%F (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
%F 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
%F a(n) = ((18*n+45)*A002893(n) - (7+2*n)*A002893(n+1)) / (6*(n+2)^2). - _Mark van Hoeij_, Jul 02 2010
%F 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
%F a(n) ~ 3^(2*n+9/2)/(16*Pi*n^4). - _Vaclav Kotesovec_, Jul 29 2013
%F 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]
%F a(n) = hypergeom([1/2, -1 - n, -n], [2, 2], 4) / (n+1). - _Vaclav Kotesovec_, Jun 07 2021
%p 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);
%p 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
%t 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}]
%t (* Second program:*)
%t 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 *)
%t Table[HypergeometricPFQ[{1/2, -1 - n, -n}, {2, 2}, 4] / (n+1), {n, 0, 25}] (* _Vaclav Kotesovec_, Jun 07 2021 *)
%o (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
%Y A column of A047888. See also A224318, A223034, A223905.
%Y Column k=3 of A214015.
%Y A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_, _Simon Plouffe_
%E Additional comments from _Emeric Deutsch_, Dec 06 2000
%E More terms from _Naohiro Nomoto_, Jun 18 2001
%E Edited by _Dean Hickerson_, Dec 10 2002
%E More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
| 