A216779 Number of derangements on n elements with an odd number of cycles.

0, 0, 1, 2, 6, 24, 135, 930, 7420, 66752, 667485, 7342290, 88107426, 1145396472, 16035550531, 240533257874, 3848532125880, 65425046139840, 1177650830516985, 22375365779822562, 447507315596451070, 9397653627525472280, 206748379805560389951, 4755212735527888968642

Offset: 0

Author

José H. Nieto S., Sep 16 2012

Keywords

• nonn
• easy

Crossrefs

Cf. A000166, A216778 (derangements with even number of cycles).

Programs

Maple

a := proc (n) local x, y, t, k; if n <= 1 then 0 else x := 0; y := 0; for k from 2 to n do t := y; y := (k-1)*(x+y-k+3); x := t end do; y end if end proc;

Mathematica

nn=23;Range[0,nn]!CoefficientList[Series[Sinh[Log[1/(1-x)]-x],{x,0,nn}],x] (* Geoffrey Critzer, Jun 23 2014 *)

Formula

a(n+1) = n*(a(n) + a(n-1) - n + 2), a(0)=0, a(1)=0.

a(n) = (A000166(n) + n - 1)/2.

E.g.f.: sinh(log(1/(1-x)) - x). - Geoffrey Critzer, Jun 23 2014