A202364 Number of n-permutations with at least one cycle of length >=4.

0, 0, 0, 0, 6, 54, 444, 3828, 34404, 331812, 3457224, 38902104, 472682088, 6185876904, 86896701072, 1305666612144, 20907918062064, 355572850545648, 6401460197543904, 121637573726005152, 2432837939316094944, 51090380436082401504, 1123995659389121919168

Offset: 0

Author

Geoffrey Critzer, Jan 09 2013

Keywords

• nonn

Comments

a(n) = n! - A057693(n). - Vaclav Kotesovec, Oct 09 2013

References

• R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.

Links

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

Crossrefs

Cf. A000142, A033312, A066052, A028418.

Programs

Maple

b:= proc(n) option remember; `if`(n<4, [6, 54, 444, 3828][n+1],
      ((5*n+3+n^2)*b(n-1) -(n+3)*b(n-2) -(n+3)*(n+2)*b(n-3)
      -(n+3)*(n+2)*(n+1)^2*b(n-4))/n)
    end:
a:= n-> `if`(n<4, 0, b(n-4)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 09 2013

Mathematica

nn=25;Range[0,nn]!CoefficientList[Series[1/(1-x)-Exp[x+x^2/2+x^3/3],{x,0,nn}],x]
(* Second program: *)
b[n_] := b[n] = If[n<4, {6, 54, 444, 3828}[[n+1]], ((5*n+3+n^2)*b[n-1] - (n + 3)*b[n-2] - (n+3)*(n+2)*b[n-3] - (n+3)*(n+2)*(n+1)^2*b[n-4])/n]; a[n_] := If[n<4, 0, b[n-4]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 08 2017, after Alois P. Heinz *)

Formula

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