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,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

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

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

Cf. A000166, A000240, A155521.

Sequence in context: A026685 A089923 A145041 * A307176 A309175 A179684

Adjacent sequences: A212288 A212289 A212290 * A212292 A212293 A212294

Keyword

nonn,easy

Author

Charles R Greathouse IV, Jun 17 2012

Status

approved