|
| |
|
|
A032351
|
|
Number of permutations of length n which avoid the patterns 2143, 1324 (smooth permutations); or avoid the patterns 1342, 2431; etc.
|
|
3
|
|
|
|
1, 1, 2, 6, 22, 88, 366, 1552, 6652, 28696, 124310, 540040, 2350820, 10248248, 44725516, 195354368, 853829272, 3733693872, 16333556838, 71476391800, 312865382004, 1369760107576, 5998008630244, 26268304208032, 115055864102504, 503997820344464, 2207927106851580, 9673223726469136, 42382192892577128, 185702341264971696
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
REFERENCES
|
H. Abe and S. Billey, Consequences of the Lakshmibai-Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry, 2014; http://www.math.washington.edu/~billey/papers/abe.billey.pdf
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7.
Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.47.
A. Woo and A. Yong, "When is a Schubert variety Gorenstein?", preprint 2004.
|
|
|
LINKS
|
Table of n, a(n) for n=0..29.
C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015. See Eq. (2).
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Miklos Bona, The permutation classes equinumerous to the smooth class, Electron. J. Combin., 5 (1998), no. 1, Research Paper 31, 12 pp.
M. Bousquet-Mélou and S. Butler, Forest-like permutations.
E. Rowland, R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635, 2013
Wikipedia, Permutation classes avoiding two patterns of length 4.
A. Woo and A. Yong, When is a Schubert variety Gorenstein?.
|
|
|
FORMULA
|
G.f.: (1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3).
G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (1 - x / (1 - x / (1 - x / ...))))))). - Michael Somos, Apr 18 2012
From Gary W. Adamson, Jul 11 2011: (Start)
a(n) = upper left term in n-th power of the following infinite square production matrix:
1, 1, 0, 0, 0, 0, ...
1, 2, 1, 0, 0, 0, ...
1, 3, 1, 1, 0, 0, ...
1, 4, 1, 1, 1, 0, ...
1, 5, 1, 1, 1, 1, ...
...
(End)
HANKEL transform is A011782. HANKEL transform of a(n+1) is A011782(n+1). INVERT transform of A026671 with 1 prepended. - Michael Somos, Apr 18 2012
Recurrence: (n-2)*a(n) = 2*(5*n-13)*a(n-1) - 4*(8*n-25)*a(n-2) + 12*(3*n-10)*a(n-3) - 8*(2*n-7)*a(n-4). - Vaclav Kotesovec, Aug 24 2014
a(n) ~ 1/11 * (1 - 5*r + 3*r^2 + r^2*sqrt(1-4*r)) *(25 - 44*r + 24*r^2) / r^n, where r = 1/6*(4 - 2/(-17 + 3*sqrt(33))^(1/3) + (-17 + 3*sqrt(33))^(1/3)) = 0.228155493653961819214572... is the root of the equation -1 + 6*r - 8*r^2 + 4*r^3 = 0. - Vaclav Kotesovec, Aug 24 2014
a(n) = (Sum_{m=0..n-2} (m+3)*(Sum_{k=0..m/2} Sum_{j=0..m-2*k-1} 2^j * binomial(j+k, k) * binomial(m-j, 2*k+1)) * binomial(2*n-m-2,n) + binomial(2*n,n))/(n+1). - Vladimir Kruchinin, Sep 19 2014
|
|
|
EXAMPLE
|
1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 88*x^5 + 366*x^6 + 1552*x^7 + ...
|
|
|
MAPLE
|
t1:=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);
series(t1, x, 40);
seriestolist(%); # N. J. A. Sloane, Nov 09 2016
|
|
|
MATHEMATICA
|
Table[(Sum[(m+3)*(Sum[Sum[2^j*Binomial[j+k, k]*Binomial[m-j, 2*k+1], {j, 0, m-2*k-1}], {k, 0, m/2}]) * Binomial[2*n-m-2, n], {m, 0, n-2}] + Binomial[2*n, n])/(n+1), {n, 0, 20}] (* Vaclav Kotesovec, Sep 19 2014, after Vladimir Kruchinin *)
|
|
|
PROG
|
(PARI) x='x+O('x^44) /* that many terms */
gf=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);
Vec(gf) /* show terms */ /* Joerg Arndt, Apr 20 2011 */
(Maxima)
a(n):=(sum((m+3)*(sum(sum(2^(j)*binomial(j+k, k)*binomial(m-j, 2*k+1), j, 0, m-2*k-1), k, 0, m/2))*binomial(2*n-m-2, n), m, 0, n-2)+binomial(2*n, n))/(n+1); /* Vladimir Kruchinin, Sep 19 2014 */
|
|
|
CROSSREFS
|
Cf. A053617.
Sequence in context: A165535 A319028 A165536 * A165537 A165538 A165539
Adjacent sequences: A032348 A032349 A032350 * A032352 A032353 A032354
|
|
|
KEYWORD
|
nonn,easy,nice,changed
|
|
|
AUTHOR
|
Miklos Bona
|
|
|
EXTENSIONS
|
More terms from Erich Friedman
|
|
|
STATUS
|
approved
|
| |
|
|
