login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A165543 Number of permutations of length n which avoid the patterns 3241 and 4321. 2
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 (list; graph; refs; listen; history; text; internal format)
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, V. Vatter, Two Vignettes On Full Rook Placements, arXiv preprint arXiv:1310.6073 [math.CO], 2013.

J. Bloom, 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, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 12 19:33 EST 2019. Contains 329078 sequences. (Running on oeis4.)