%I A005802 M1666
%S A005802 1,1,2,6,23,103,513,2761,15767,94359,586590,3763290,24792705,167078577,
%T A005802 1148208090,8026793118,56963722223,409687815151,2981863943718,
%U A005802 21937062144834,162958355218089,1221225517285209,9225729232653663
%N 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).
%C A005802 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 A005802 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 Brewster Lewis (jblewis(AT)post.harvard.edu), 
               May 21 2009]
%D A005802 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005802 Gessel, Ira M., Symmetric functions and P-recursiveness. J. Combin. Theory 
               Ser. A 53 (1990), no. 2, 257-285.
%D A005802 O. Guibert, E. Pergola, Enumeration of vexillary involutions which are 
               equal to their mirror/complement, Discrete Math., Vol. 224 (2000), 
               pp. 281-287.
%D A005802 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see 
               Problem 7.16(e), p. 453.
%D A005802 R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. 
               Math. Soc., 40 (2003), 55-68.
%H A005802 J. Noonan and D. Zeilberger, <a href="http://arXiv.org/abs/math.CO/9808080">
               [math/9808080] The Enumeration of Permutations With a Prescribed 
               Number of ``Forbidden'' Patterns</a>
%H A005802 J. Noonan and D. Zeilberger, <a href="http://www.math.temple.edu/~zeilberg/
               mamarim/mamarimPDF/forbid.pdf">The Enumeration of Permutations With 
               A Prescribed Number of "Forbidden" Patterns</a>
%H A005802 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.ps">
               A combinatorial miscellany</a>
%H A005802 Erik Ouchterlony, <a href="http://garsia.math.yorku.ca/fpsac06/papers/
               83.pdf">Pattern avoiding doubly alternating permutations</a> [From 
               Joel Brewster Lewis (jblewis(AT)post.harvard.edu), May 21 2009]
%F A005802 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 A005802 (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 (vladeta(AT)eunet.rs), Jul 16 2004
%F A005802 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
%p A005802 a := n->2*sum(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 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)
%t A005802 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}]
%Y A005802 A column of A047888.
%Y A005802 Sequence in context: A088929 A004040 A022558 this_sequence A061552 A053488 
               A117106
%Y A005802 Adjacent sequences: A005799 A005800 A005801 this_sequence A005803 A005804 
               A005805
%K A005802 nonn,nice,easy
%O A005802 0,3
%A A005802 N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe (simon.plouffe(AT)gmail.com)
%E A005802 Additional comments from Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 
               06 2000
%E A005802 More terms from Naohiro Nomoto (6284968128(AT)geocities.co.jp), Jun 18 
               2001
%E A005802 Edited by Dean Hickerson (dean.hickerson(AT)yahoo.com), Dec 10 2002
%E A005802 More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005