login
A162973
Number of cycles in all derangement permutations of {1,2,...,n}.
2
0, 1, 2, 12, 64, 425, 3198, 27216, 258144, 2701737, 30933770, 384675148, 5163521856, 74417353985, 1146203362822, 18790377267840, 326682354342336, 6003886529652657, 116305541572943826, 2368629865508978284
OFFSET
1,3
LINKS
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
FORMULA
a(n) = Sum_{k>=1} k*A008306(n,k).
E.g.f.: exp(-z)*(z+log(1-z))/(z-1).
a(n) ~ n! * (log(n) + gamma - 1)/exp(1), where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, Sep 25 2013
a(n) = A000254(n) - A162972(n). - Anton Zakharov, Oct 18 2016
D-finite with recurrence a(n) +2*(-n+2)*a(n-1) +(n-2)*(n-6)*a(n-2) +(3*n-8)*(n-3)*a(n-3) +3*(n-3)^2*a(n-4) +(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Jul 26 2022
EXAMPLE
a(4)=12 because in the derangements of {1,2,3,4}, namely (12)(34), (13)(24), (14)(23), (1234), (1243), (1324), (1342), (1423), and (1432), we have a total of 2+2+2+1+1+1+1+1+1=12 cycles.
MAPLE
G := exp(-z)*(z+ln(1-z))/(z-1): Gser := series(G, z = 0, 25): seq(factorial(n)*coeff(Gser, z, n), n = 1 .. 22);
MATHEMATICA
With[{nn=20}, Rest[CoefficientList[Series[Exp[-x] (x+Log[1-x])/(x-1), {x, 0, nn}], x] Range[0, nn]!]] (* Harvey P. Dale, Jul 25 2013 *)
PROG
(PARI) x='x+O('x^30); concat([0], Vec(serlaplace(exp(-x)*(x+log(1-x))/(x -1)))) \\ G. C. Greubel, Sep 01 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jul 22 2009
STATUS
approved