A165543 - OEIS

%I #59 Jun 05 2021 02:32:42

%S 1,1,2,6,22,89,380,1678,7584,34875,162560,766124,3644066,17469863,

%T 84324840,409471090,1998933556,9804748548,48298256084,238840150970,

%U 1185256302910,5900843531665,29464355189120,147522603762870,740471407808372,3725334547101464,18782663124890072,94889671255981134

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

%C These permutations have an enumeration scheme of depth 4.

%C 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

%H Vincenzo Librandi, <a href="/A165543/b165543.txt">Table of n, a(n) for n = 0..270</a>

%H J. Bloom and V. Vatter, <a href="http://arxiv.org/abs/1310.6073">Two Vignettes On Full Rook Placements</a>, arXiv preprint arXiv:1310.6073 [math.CO], 2013.

%H J. Bloom and V. Vatter, <a href="http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p077.pdf">Two Vignettes On Full Rook Placements</a>, The Australasian Journal of Combinatorics, vol. 64(1), 2016, p. 80.

%H David Callan, <a href="https://arxiv.org/abs/1306.3193">Permutations avoiding 4321 and 3241 have an algebraic generating function</a>, arXiv:1306.3193 [math.CO], 2013.

%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.

%H Darla Kremer and Wai Chee Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

%H Toufik Mansour, Howard Skogman, and Rebecca Smith, <a href="https://arxiv.org/abs/1808.04199">Passing through a stack k times with reversals</a>, arXiv:1808.04199 [math.CO], 2018.

%H V. Vatter, <a href="http://www.math.ufl.edu/~vatter/publications/wilfplus/">Enumeration schemes for restricted permutations</a>, Combin., Prob. and Comput. 17 (2008), 137-159.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.

%F From _Vladimir Kruchinin_, May 12 2011: (Start)

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

%F 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)

%F From _Gary W. Adamson_, Nov 14 2011: (Start)

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

%F   1, 1, 0, 0, 0, ...

%F   1, 1, 1, 0, 0, ...

%F   2, 1, 1, 1, 0, ...

%F   5, 1, 1, 1, 1, ...

%F   ... (End)

%F G.f.: A035929(x)/x composed with x*A000108(x). - _Alexander Burstein_, Aug 07 2017

%F a(n) ~ 2^(4*n + 3/2) / (25 * sqrt(Pi) * n^(3/2) * 3^(n - 3/2)). - _Vaclav Kotesovec_, Aug 14 2018

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

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

%o (Maxima)

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

%K nonn

%O 0,3

%A _Vincent Vatter_, Sep 21 2009

%E a(0)=1 prepended by _Alois P. Heinz_, Feb 18 2016