login
A137482
Number of permutations of n objects such that no two-element subset is preserved.
6
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
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
Sequence in context: A067056 A208428 A356373 * A346033 A277761 A203576
KEYWORD
nonn
AUTHOR
Jono Henshaw (jjono(AT)hotmail.com), Apr 22 2008, corrected Apr 30 2008
STATUS
approved