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,3

Links

Table of n, a(n) for n=0..35.

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

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

Example

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

Maple

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

Crossrefs

Cf. A061547.

Sequence in context: A068911 A243543 A094769 * A358650 A357546 A294918

Adjacent sequences: A068015 A068016 A068017 * A068019 A068020 A068021

Keyword

nonn,easy

Author

Emeric Deutsch, Mar 22 2002

Status

approved