A158243 Derangements with at least one 2-cycle.

0, 0, 1, 0, 3, 20, 105, 714, 5845, 52632, 525105, 5777090, 69337521, 901364100, 12618959353, 189284859750, 3028559357265, 51485499960944, 926738981188065, 17608040824708242, 352160816656099465, 7395377145973453980, 162698297211819995241, 3742060835955157848110

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Formula

E.g.f.: (1-exp(-x^2/2))*exp(-x)/(1-x).

a(n) ~ n! * (exp(-1)-exp(-3/2)). - Vaclav Kotesovec, Jul 30 2013

Example

There is just one derangement of 2 elements, it is a 2-cycle, so a(2)=1. The 2 derangements of 3 elements are cyclic shifts (3-cycles), so a(3)=0. The 9 derangements of 4 elements are (both array and cycle notation):
1: [ 1 0 3 2 ] (0, 1) (2, 3)
2: [ 1 2 3 0 ] (0, 1, 2, 3)
3: [ 1 3 0 2 ] (0, 1, 3, 2)
4: [ 2 0 3 1 ] (0, 2, 3, 1)
5: [ 2 3 0 1 ] (0, 2) (1, 3)
6: [ 2 3 1 0 ] (0, 2, 1, 3)
7: [ 3 0 1 2 ] (0, 3, 2, 1)
8: [ 3 2 0 1 ] (0, 3, 1, 2)
9: [ 3 2 1 0 ] (0, 3) (1, 2)
Of these, three (number 1, 5, and 9) contain a 2-cycle, so a(4)=3.

Maple

a:= n-> coeff(series((1-exp(-x^2/2))*exp(-x)/(1-x), x, n+1), x, n)*n!:
seq(a(n), n=0..25); # Alois P. Heinz, May 20 2013
# second Maple program:
a:= proc(n) option remember; `if`(n<4, n*(n-1)*(3-n)/2,
      ((n-1)*((n-3)*a(n-1) +(n-2)*(a(n-2)
      +(n-2)*a(n-3) +(n-3)*a(n-4))))/(n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 08 2013

Mathematica

nn = 21; Rest[ Range[0, nn]! CoefficientList[ Series[(Exp[-x] - Exp[-x - x^2/2])/(1 - x), {x, 0, nn}], x]] (* Geoffrey Critzer, May 20 2013 *)

Prog

(PARI) N=25; z='x+O('x^N); k=2; v=Vec(serlaplace((1-exp(-z^k/k))* exp(-sum(j=1, k-1, z^j/j))/(1-x))) /* vector starting with index 2 */

Crossrefs

Second row of A145877. Cf. A000166.

Sequence in context: A000917 A025535 A119693 * A139471 A154641 A178711

Adjacent sequences: A158240 A158241 A158242 * A158244 A158245 A158246

Keyword

nonn

Author

Joerg Arndt, Mar 14 2009

Status

approved