A137482 Number of permutations of n objects such that no two-element subset is preserved.

1, 1, 0, 2, 14, 54, 304, 2260, 18108, 161756, 1618496, 17815896, 213767080, 2778833992, 38904145344, 583563781424, 9337011390224, 158729175524880, 2857125341582848, 54285381652008736, 1085707629235539936, 22799860214350346336, 501596924799005576960

Offset

0,4

Comments

In other words, there are no two objects which the permutation leaves fixed and no two objects that the permutation swaps.

The limit as n -> infinity of a(n)/n! = 2/exp(3/2) or approximately 0.4462603203. - Les Reid, Jun 04 2012

Links

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

Hannah Jackson, Kathryn Nyman and Les Reid, Properties of generalized derangement graphs, Involve, Vol. 6 (2013), No. 1, 25-33; DOI: 10.2140/involve.2013.6.25.

Formula

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

a(n) = (n-1)*a(n-1) - a(n-2) + (n-2)*n*a(n-3) for n > 2, a(n) = (n+1)*(2-n)/2 for n < 3. - Alois P. Heinz, Feb 19 2019

Example

a(3)=2 because we have 312 and 231.

Maple

g:=(1+x)*exp(-x)*exp(-(1/2)*x^2)/(1-x): gser:=series(g, x=0, 25): seq(factorial(n)*coeff(gser, x, n), n=0..20);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, (n+1)*(2-n)/2,
      (n-1)*a(n-1)-a(n-2)+(n-2)*n*a(n-3))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 19 2019

Mathematica

With[{nn=20}, CoefficientList[Series[((1+x)Exp[-x]Exp[-x^2/2])/(1-x), {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Nov 17 2013 *)

Crossrefs

Cf. A000166, A000266.

Sequence in context: A067056 A208428 A356373 * A346033 A277761 A203576

Adjacent sequences: A137479 A137480 A137481 * A137483 A137484 A137485

Keyword

nonn

Author

Jono Henshaw (jjono(AT)hotmail.com), Apr 22 2008, corrected Apr 30 2008

Status

approved