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

%I #20 Aug 18 2024 23:03:40

%S 0,1,2,4,6,12,18,40,62,148,234,576,918,2284,3650,9112,14574,36420,

%T 58266,145648,233030,582556,932082,2330184,3728286,9320692,14913098,

%U 37282720,59652342,149130828,238609314,596523256,954437198,2386092964,3817748730,9544371792

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

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,3,-8,4).

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

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

%F 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

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

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

%Y Cf. A061547.

%K nonn,easy

%O 0,3

%A _Emeric Deutsch_, Mar 22 2002