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

Author

Emeric Deutsch, May 25 2010

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

Cf. A000166, A000240.

Column A180192(n,1).

Programs

Magma

A000166:= func< n | Factorial(n)*(&+[(-1)^j/Factorial(j): j in [0..n]]) >;
A177265:= func< n | n le 2 select 1 else Self(n-1) + n*A000166(n-1) >;
[A177265(n): n in [1..30]]; // G. C. Greubel, May 19 2024

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

SageMath

def A000166(n): return factorial(n)*sum((-1)^j/factorial(j) for j in range(n+1))
def a(n): return 1 if n<3 else a(n-1) + n*A000166(n-1) # a = A177265
[a(n) for n in range(1,31)] # G. C. Greubel, May 19 2024

Formula

a(n) = (1/2)*(1 - (-1)^n) + Sum_{j=1..n} d(j), where d(j) = A000166(j) 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