A212291 Number of permutations of n elements with at most one fixed point.

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

Author

Charles R Greathouse IV, Jun 17 2012

Keywords

• nonn
• easy

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

• Alois P. Heinz, Table of n, a(n) for n = 0..400
• 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

Crossrefs

Cf. A000166, A000240, A155521.

Programs

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 *)

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

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)