A165543 Number of permutations of length n which avoid the patterns 3241 and 4321.

1, 1, 2, 6, 22, 89, 380, 1678, 7584, 34875, 162560, 766124, 3644066, 17469863, 84324840, 409471090, 1998933556, 9804748548, 48298256084, 238840150970, 1185256302910, 5900843531665, 29464355189120, 147522603762870, 740471407808372, 3725334547101464, 18782663124890072, 94889671255981134

Offset

0,3

Comments

These permutations have an enumeration scheme of depth 4.

Conjecturally, a(n) is the number of permutations pi of length n such that s(pi) avoids the patterns 231 and 321, where s denotes West's stack-sorting map. - Colin Defant, Sep 17 2018

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..270

J. Bloom and V. Vatter, Two Vignettes On Full Rook Placements, arXiv preprint arXiv:1310.6073 [math.CO], 2013.

J. Bloom and V. Vatter, Two Vignettes On Full Rook Placements, The Australasian Journal of Combinatorics, vol. 64(1), 2016, p. 80.

David Callan, Permutations avoiding 4321 and 3241 have an algebraic generating function, arXiv:1306.3193 [math.CO], 2013.

Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

Toufik Mansour, Howard Skogman, and Rebecca Smith, Passing through a stack k times with reversals, arXiv:1808.04199 [math.CO], 2018.

V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

From Vladimir Kruchinin, May 12 2011: (Start)

G.f.: 1/(1-x*A000108(x*A000108(x)))

a(n) = sum(m=1..n-1, (m*sum(k=1..n-m, (k*binomial(m+2*k-1,m+k-1)*binomial(2*(n-m)-k-1,n-m-1))/(m+k)))/(n-m))+1. (End)

From Gary W. Adamson, Nov 14 2011: (Start)

a(n) is the top left term in M^n, M = an infinite square production matrix with A000108 as the left column, as follows:

1, 1, 0, 0, 0, ...

1, 1, 1, 0, 0, ...

2, 1, 1, 1, 0, ...

5, 1, 1, 1, 1, ...

... (End)

G.f.: A035929(x)/x composed with x*A000108(x). - Alexander Burstein, Aug 07 2017

a(n) ~ 2^(4*n + 3/2) / (25 * sqrt(Pi) * n^(3/2) * 3^(n - 3/2)). - Vaclav Kotesovec, Aug 14 2018

Example

There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Mathematica

a[0] = 1; a[n_] := Sum[ (m*Sum[ (k*Binomial[m+2*k-1, m+k-1]*Binomial[2*(n-m)-k-1, n-m-1])/(m + k), {k, 1, n-m}])/(n-m), {m, 1, n-1}] + 1; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Jun 25 2013 *) (* adapted by Vincenzo Librandi, May 14 2017 *)

Prog

(Maxima)
a(n):=if n=0 then 0 else sum((m*sum((k*binomial(m+2*k-1, m+k-1)*binomial(2*(n-m)-k-1, n-m-1))/(m+k), k, 1, n-m))/(n-m), m, 1, n-1)+1; /* Vladimir Kruchinin, May 12 2011 */

Crossrefs

Sequence in context: A111053 A165541 A165542 * A049123 A200753 A165544

Adjacent sequences: A165540 A165541 A165542 * A165544 A165545 A165546

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

a(0)=1 prepended by Alois P. Heinz, Feb 18 2016

Status

approved