|
|
A088921
|
|
The number of 321- and 2143-avoiding permutations of length n.
|
|
2
|
|
|
1, 2, 5, 13, 33, 80, 185, 411, 885, 1862, 3853, 7881, 15993, 32284, 64945, 130359, 261293, 523282, 1047397, 2095781, 4192721, 8386792, 16775145, 33552083, 67106213, 134214750, 268432125, 536867201, 1073737705, 2147479092
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
That is, both the patterns 321 and 2143 are to be avoided. - N. J. A. Sloane, Oct 21 2010.
321- and 2143-avoiding permutations of length n are in one-to-one correspondence with simple Dyck paths of semilength n (a Dyck path is simple if it has at most one long upward edge or at most one long downward edge, an edge being "long" if it consists of at least two steps). They are the Grassmannian permutations and their inverses. They can also be characterized as those permutations whose essential set is contained in one row or one column. This sequence also enumerates the cyclic arrangements of 1, 2, ... n+1 which avoid the cyclic arrangement 1234.
Also, number of 1324-avoiding circular permutations on [n+1].
Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) < e(k) and e(i) != e(k). [Martinez and Savage, 2.9] - Eric M. Schmidt, Jul 17 2017
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2^(n+1) - binomial(n+1, 3) - 2*n - 1.
G.f.: x*(2*x^4-5*x^3+7*x^2-4*x+1)/((1-2*x)*(1-x)^4). - Emeric Deutsch, Feb 22 2004
|
|
MATHEMATICA
|
Table[2^(n + 1) - Binomial[n + 1, 3] - 2 n - 1, {n, 30}] (* or *)
Rest@ CoefficientList[Series[x (2 x^4 - 5 x^3 + 7 x^2 - 4 x + 1)/((1 - 2 x) (1 - x)^4), {x, 0, 30}], x] (* Michael De Vlieger, May 13 2017 *)
|
|
PROG
|
(PARI) a(n) = 2^(n+1) - binomial(n+1, 3) - 2*n - 1 \\ Michel Marcus, Jul 11 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Antoine Vella (avella(AT)math.uwaterloo.ca), Oct 23 2003
|
|
STATUS
|
approved
|
|
|
|