login
A212291
Number of permutations of n elements with at most one fixed point.
3
1, 1, 1, 5, 17, 89, 529, 3709, 29665, 266993, 2669921, 29369141, 352429681, 4581585865, 64142202097, 962133031469, 15394128503489, 261700184559329, 4710603322067905, 89501463119290213, 1790029262385804241, 37590614510101889081, 826993519222241559761
OFFSET
0,4
COMMENTS
Agrees with the number of maximal matchings in the n-crown graph up to at least n = 10. - Eric W. Weisstein, Jun 14-Dec 30 2017
LINKS
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
FORMULA
a(n) = 2/e * n! + O(n).
a(n) = 2*!n - (-1)^n, where !n is the subfactorial. - Eric W. Weisstein, Dec 30 2017
a(n) = A000166(n) + A000240(n).
E.g.f.: (1+x)*exp(-x)/(1-x).
From Mohammed Bouras, May 29 2023: (Start)
a(n) = n! - A155521(n-1).
A155521(n-1)/a(n) = 1/(2+3/(3+4/(4+5/(...(n-1)+n)))). (End)
MAPLE
b:= proc(n) b(n):= `if` (n<1, 1, n*b(n-1)+(-1)^(n)) end:
a:= n-> b(n) +n*b(n-1):
seq(a(n), n=0..30); # Alois P. Heinz, Jun 17 2012
MATHEMATICA
nn=20; Range[0, nn]! CoefficientList[Series[(1+x)Exp[-x]/(1-x), {x, 0, nn}], x] (* Geoffrey Critzer, Sep 27 2013 *)
Table[(-1)^n (HypergeometricPFQ[{1, -n}, {}, 1] - n HypergeometricPFQ[{1, 1 - n}, {}, 1]), {n, 20}] (* Eric W. Weisstein, Jun 14 2017 *)
Table[2 Subfactorial[n] - (-1)^n, {n, 20}] (* Eric W. Weisstein, Dec 30 2017 *)
PROG
(PARI) d(n)=if(n, round(n!/exp(1)), 1)
a(n)=if(n, n*d(n-1))+d(n)
(PARI) my(x='x+O('x^25)); Vec(serlaplace((1+x)/(1-x)*exp(-x))) \\ Joerg Arndt, Jun 04 2023
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved