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

Author

Emeric Deutsch, Nov 17 2005

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A114209, A114210.

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]