|
|
A177265
|
|
Number of permutations of {1,2,...,n} having exactly one string of consecutive fixed points (including singletons).
|
|
3
|
|
|
1, 1, 4, 12, 57, 321, 2176, 17008, 150505, 1485465, 16170036, 192384876, 2483177809, 34554278857, 515620794592, 8212685046336, 139062777326001, 2494364438359953, 47245095998005060, 942259727190907180, 19737566982241851721, 433234326593362631601
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (1/2)*(1 - (-1)^n) + Sum_{j=1..n} d(j), where d(j) = A000166(j) are the derangement numbers.
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 *)
|
|
PROG
|
(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) >;
(SageMath)
def A000166(n): return factorial(n)*sum((-1)^j/factorial(j) for j in range(n+1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|