|
| |
|
|
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)
|
|
18
|
|
|
|
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
|
|
|
REFERENCES
|
Gessel, Ira M., Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A 53 (1990), no. 2, 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.
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.
R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..300
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
|
|
|
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
A005802(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.
|
|
|
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,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 (dean.hickerson(AT)yahoo.com), Dec 10 2002
More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
|
|
|
STATUS
|
approved
|
| |
|
|
