A114209 Number of permutations of [n] having exactly two fixed points and avoiding the patterns 123 and 231.
0, 1, 0, 2, 1, 3, 2, 5, 3, 7, 5, 9, 7, 12, 9, 15, 12, 18, 15, 22, 18, 26, 22, 30, 26, 35, 30, 40, 35, 45, 40, 51, 45, 57, 51, 63, 57, 70, 63, 77, 70, 84, 77, 92, 84, 100, 92, 108, 100, 117, 108, 126, 117, 135, 126, 145, 135, 155, 145, 165, 155, 176, 165, 187, 176, 198, 187
Offset: 1
Keywords
Examples
a(2)=1 because we have 12; a(3)=0 because no permutation of [3] can have exactly two fixed points; a(4)=2 because we have 1432 and 3214.
Links
- 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 (0,2,1,-1,-2,0,1).
Programs
-
Maple
a:=proc(n) if n mod 6 = 0 then n*(n+6)/24 elif n mod 6 = 1 or n mod 6 = 5 then (n^2-1)/24 elif n mod 6 = 2 or n mod 6 = 4 then (n+2)*(n+4)/24 else (n^2-9)/24 fi end: seq(a(n),n=1..70);
Formula
a(n) = n(n+6)/24 if n mod 6 = 0; (n^2-1)/24 if n mod 6 = 1 or 5; (n+2)(n+4)/24 if n mod 6 = 2 or 4; (n^2-9)/24 if n mod 6 = 3.
a(n) = A008731(n-2). O.g.f.: x^2/((1-x)^3(1+x)^2(1+x+x^2)). [R. J. Mathar, Aug 11 2008]