A165543 Number of permutations of length n which avoid both the patterns 3241 and 4321. Or, equivalently, avoids both 1234 and 1342.

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

Author

Vincent Vatter, Sep 21 2009

Keywords

• nonn

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

Examples

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

References

• Christian Bean, Combinatorial Exploration and Permutation Classes, talk in RUTGERS Experimental Mathematics Seminar Series, Thursday, March 27, 2025, (https://sites.math.rutgers.edu/~zeilberg/expmath/). The last slide is devoted to this sequence - N. J. A. Sloane, Apr 06 2025

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.
• Permutation Pattern Avoidance Library (PermPAL), Av(1234,1342).
• V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.
• Wikipedia, Permutation classes avoiding two patterns of length 4.

Programs

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 *)

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 */

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

Extensions

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

Definition expanded by N. J. A. Sloane, Apr 28 2025