A068018 Number of fixed points in all 132- and 213-avoiding permutations of {1,2,...,n} (these are permutations with runs consisting of consecutive integers).

0, 1, 2, 4, 6, 12, 18, 40, 62, 148, 234, 576, 918, 2284, 3650, 9112, 14574, 36420, 58266, 145648, 233030, 582556, 932082, 2330184, 3728286, 9320692, 14913098, 37282720, 59652342, 149130828, 238609314, 596523256, 954437198, 2386092964, 3817748730, 9544371792

Offset: 0

Author

Emeric Deutsch, Mar 22 2002

Keywords

• nonn
• easy

Examples

			a(3) = 4 because the permutations 123, 231, 312, 321 of {1,2,3} contain 4 fixed points altogether (all three entries of the first permutation and entry 2 in the last one).
		

Links

• Index entries for linear recurrences with constant coefficients, signature (2,3,-8,4).

Crossrefs

Cf. A061547.

Programs

Maple

seq(2^n/4-(-2)^n/36+2*n/3-2/9,n=0..40);

Formula

a(n) = 2^n/4 - (-2)^n/36 + 2*n/3 - 2/9.

G.f.: z*(1 - 3*z^2)/((1 - 4*z^2)*(1 - z)^2).

E.g.f.: (cosh(x)*(5*sinh(x) + 6*x - 2) + 2*(cosh(2*x) + (3*x - 1)*sinh(x)))/9. - Stefano Spezia, Jun 12 2023