A351901 Number of permutations of [n] having at least one repeated cycle length.

0, 0, 1, 1, 10, 46, 246, 1926, 16080, 143424, 1397520, 16163280, 190902240, 2534113440, 35501044320, 531674569440, 8558324490240, 147103748144640, 2631981703680000, 50393537347829760, 1011054905709004800, 21229069614652569600, 468171587690550374400

Offset: 0

Author

Alois P. Heinz, Feb 24 2022

Keywords

• nonn

Examples

			a(2) = 1: (1)(2).
a(3) = 1: (1)(2)(3).
a(4) = 10: (1)(2)(3)(4), (1)(2)(3,4), (1)(2,4)(3), (1)(2,3)(4), (1,4)(2)(3), (1,3)(2)(4), (1,2)(3)(4), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450
• Wikipedia, Permutation

Crossrefs

Cf. A000142, A001620, A007838, A227242.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+b(n-i, min(i-1, n-i))/i))
    end:
a:= n-> n!*(1-b(n$2)):
seq(a(n), n=0..23);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0,
     b[n, i - 1] + b[n - i, Min[i - 1, n - i]]/i]];
a[n_] := n!*(1 - b[n, n]);
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 19 2022, after Alois P. Heinz *)

Formula

E.g.f.: 1/(1-x) - Product_{j>=1} (1 + x^j/j).

a(n) = A000142(n) - A007838(n).

Limit_{n-> infinity} a(n)/n! = 1 - exp(-gamma) = A227242 = 0.43854... .