login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of permutations of length n which avoid the patterns 1234 and 2341.
1

%I #26 Jun 14 2016 12:59:38

%S 1,2,6,22,89,376,1611,6901,29375,123996,518971,2155145,8888348,

%T 36442184,148669894,603984658,2445184835,9870338447,39746337616,

%U 159728191141,640811439917,2567220813272,10272592695691,41064215020977,164014588869574,654627778362521,2611244306191009,10410752330836178,41488934932279847,165282459721996836,658248561748273483

%N Number of permutations of length n which avoid the patterns 1234 and 2341.

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

%H Alois P. Heinz, <a href="/A165540/b165540.txt">Table of n, a(n) for n = 1..1000</a>

%H David Bevan, <a href="http://arxiv.org/abs/1407.0570">The permutation classes Av(1234,2341) and Av(1243,2314)</a>, arXiv:1407.0570 [math.CO], 2014.

%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 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 G.f.: ((2-10*z+9*z^2+7*z^3-4*z^4)*sqrt(1-4*z) - (2-16*z+41*z^2-39*z^3+12*z^4)) / ((1-4*z)*(1-3*z+z^2)*((1-z)*sqrt(1-4*z) + (1-3*z))). - _David Bevan_, Jun 23 2014

%F a(n) ~ 2^(2*n+1)/sqrt(Pi*n). - _Vaclav Kotesovec_, Aug 23 2014

%F Conjecture: +(14681*n+187954)*(n+3) *a(n) +(14681*n^2-2696783*n-4897218) *a(n-1) +(-888761*n^2+12771539*n+5490342) *a(n-2) +2*(1635223*n^2-14850835*n+13281012) *a(n-3) +2*(-1908503*n^2+15402653*n-25889820) *a(n-4) +156*(2*n-7)*(3301*n-14374) *a(n-5)=0. - _R. J. Mathar_, Jun 14 2016

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

%t Rest[CoefficientList[ Series[ ((2-10z+9z^2+7z^3-4z^4) Sqrt[1-4z] -(2-16z+41z^2-39z^3+12z^4)) / ((1-4z) (1-3z+z^2) ((1-z) Sqrt[1-4z] +(1-3z))), {z,0,40}], z]] (* _David Bevan_, Jun 23 2014 *)

%K nonn

%O 1,2

%A _Vincent Vatter_, Sep 21 2009

%E More terms from _David Bevan_, Jun 23 2014