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

Links

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

Wikipedia, Permutation

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

Example

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

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

Crossrefs

Cf. A000142, A001620, A007838, A227242.

Sequence in context: A199313 A003765 A138041 * A219597 A000832 A242462

Adjacent sequences: A351898 A351899 A351900 * A351902 A351903 A351904

Keyword

nonn

Author

Alois P. Heinz, Feb 24 2022

Status

approved