A177265 Number of permutations of {1,2,...,n} having exactly one string of consecutive fixed points (including singletons).

1, 1, 4, 12, 57, 321, 2176, 17008, 150505, 1485465, 16170036, 192384876, 2483177809, 34554278857, 515620794592, 8212685046336, 139062777326001, 2494364438359953, 47245095998005060, 942259727190907180, 19737566982241851721, 433234326593362631601

Offset

1,3

Comments

Empirically the partial sums of A000240. - Sean A. Irvine, Jul 12 2022

Links

Alois P. Heinz, Table of n, a(n) for n = 1..450

Formula

a(n) = (1/2)[1-(-1)^n] + Sum_{j=1..n} d[j], where d[j] = A000166(n) are the derangement numbers.

a(1) = 1, a(2) = 1, a(n) = a(n-1) + n*A000166(n-1). - Daniel Suteu, Jan 25 2018

Conjecture: D-finite with recurrence a(n) +(-n+1)*a(n-1) +(-n+1)*a(n-2) +(n-1)*a(n-3) +(n-2)*a(n-4)=0. - R. J. Mathar, Jul 01 2022

Example

a(4,1) = 12 because we have (the string of consecutive fixed points is between square brackets): [1]342, [1]423, [12]43, [1234], 3[2]41, 4[2]13, 4[23]1, 24[3]1, 41[3]2, 21[34], 231[4], and 312[4].

Maple

d := proc (n) options operator, arrow: factorial(n)*(sum((-1)^i/factorial(i), i = 0 .. n)) end proc: a := proc (n) options operator, arrow: 1/2-(1/2)*(-1)^n+add(d(j), j = 1 .. n) end proc; seq(a(n), n = 1 .. 22);

Mathematica

a[0] = 1; a[n_] := a[n] = n*a[n - 1] + (-1)^n; f[n_] := Sum[(n - k) a[n - k - 1], {k, 0, n - 1}]; Array[f, 20] (* Robert G. Wilson v, Apr 01 2011 *)

Crossrefs

Cf. A000166. Column A180192(n,1).

Cf. A000240.

Sequence in context: A065125 A208940 A209068 * A243923 A192331 A068525

Adjacent sequences: A177262 A177263 A177264 * A177266 A177267 A177268

Keyword

nonn

Author

Emeric Deutsch, May 25 2010

Status

approved