A114208 Number of permutations of [n] having exactly one fixed point and avoiding the patterns 123 and 231.
1, 0, 3, 2, 6, 6, 12, 10, 21, 16, 31, 24, 44, 32, 60, 42, 77, 54, 97, 66, 120, 80, 144, 96, 171, 112, 201, 130, 232, 150, 266, 170, 303, 192, 341, 216, 382, 240, 426, 266, 471, 294, 519, 322, 570, 352, 622, 384, 677, 416, 735, 450, 794, 486, 856, 522, 921, 560
Offset: 1
Examples
a(2)=0 because none of the permutations 12 and 21 has exactly one fixed point. a(3)=3 because we have 132, 213 and 321. a(4)=2 because we have 4132 and 4213.
Links
- Harvey P. Dale, Table of n, a(n) for n = 1..1000
- T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Annals of Combinatorics, 6, 2002, 407-418.
- Index entries for linear recurrences with constant coefficients, signature (-1,2,3,0,-3,-2,1,1).
Programs
-
Maple
a:=proc(n) if n mod 6 = 0 then n^2/6 elif n mod 6 = 1 or n mod 6 = 5 then (7*n^2-12*n+29)/24 elif n mod 6 = 2 or n mod 6 = 4 then (n^2-4)/6 else (7*n^2-12*n+45)/24 fi end: seq(a(n),n=1..70);
-
Mathematica
npn[n_]:=Module[{c=Mod[n,6]},Which[c==0,n^2/6,c==1,(7n^2-12n+29)/24,c==2,(n^2-4)/6,c==3,(7n^2-12n+45)/24,c==4,(n^2-4)/6,c==5,(7n^2-12n+29)/24]]; Array[npn,60] (* or *) LinearRecurrence[{-1,2,3,0,-3,-2,1,1},{1,0,3,2,6,6,12,10},60] (* Harvey P. Dale, Mar 05 2012 *)
Formula
n^2/6 if n mod 6 = 0; (7*n^2-12*n+29)/24 if n mod 6 = 1 or 5; (n^2-4)/6 if n mod 6 = 2 or 4; (7*n^2-12*n+45)/24 if n mod 6 = 3.
a(n) = a(n-1)+ 2*a(n-2)+3*a(n-3)-3*a(n-5)-2*a(n-6)+a(n-7)+a(n-8). [Harvey P. Dale, Mar 05 2012]
G.f.: -x*(2*x^6+2*x^5+2*x^4+2*x^3+x^2+x+1) / ((x-1)^3*(x+1)^3*(x^2+x+1)). [Colin Barker, Aug 11 2013]