login
A158243
Derangements with at least one 2-cycle.
3
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
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
KEYWORD
nonn
AUTHOR
Joerg Arndt, Mar 14 2009
STATUS
approved