login
Number of permutations of length n which avoid the patterns 1234, 3142, 3421.
0

%I #15 Nov 08 2017 04:28:49

%S 1,2,6,21,71,208,526,1174,2370,4416,7714,12783,20277,31004,45946,

%T 66280,93400,128940,174798,233161,306531,397752,510038,647002,812686,

%U 1011592,1248714,1529571,1860241,2247396

%N Number of permutations of length n which avoid the patterns 1234, 3142, 3421.

%H D. Callan, T. Mansour, <a href="http://arxiv.org/abs/1705.00933">Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns</a>, arXiv:1705.00933 (2017), Table 2 No 21.

%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/webbook/bookmain.html">Systematic Studies in Pattern Avoidance</a>, 2005.

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (7, -21, 35, -35, 21, -7, 1).

%F G.f.: A(x) = -{x(2x^8-3x^7+x^6-9x^5+15x^4-14x^3+13x^2-5x+1)}/{(x-1)^7}

%F For n >= 3, a(n) = (n^6 + 45n^5 - 245n^4 - 465n^3 + 8164n^2 - 24780n + 25920)/720. - Franklin T. Adams-Watters, Sep 16 2006

%F a(1)=1, a(2)=2, a(3)=6, a(4)=21, a(5)=71, a(6)=208, a(7)=526, a(8)=1174, a(9)=2370, a(n)=7*a(n-1)-21*a(n-2)+35*a(n-3)-35*a(n-4)+21*a(n-5)- 7*a(n-6)+a (n-7) [From Harvey P. Dale, Aug 31 2011]

%t Join[{1,2,6},Table[(n^6+45n^5-245n^4-465n^3+8164n^2-24780n+25920)/ 720,{n,4,40}]] (* or *) Join[{1,2},LinearRecurrence[ {7,-21,35,-35,21,-7,1},{6,21,71,208,526,1174,2370},40]] (* _Harvey P. Dale_, Aug 31 2011 *)

%K nonn,easy

%O 1,2

%A _Lara Pudwell_, Feb 26 2006