A359951 Number of permutations of [n] such that the GCD of the cycle lengths is a prime.

0, 0, 1, 2, 3, 24, 145, 720, 4725, 22400, 602721, 3628800, 67692625, 479001600, 12924021825, 103953833984, 2116670180625, 20922789888000, 959231402754625, 6402373705728000, 257071215652932681, 3242340687872000000, 142597230222616430625, 1124000727777607680000

Offset

0,4

Links

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

Wikipedia, Permutation

Formula

a(n) = Sum_{prime p <= n} A346085(n,p).

a(p) = (p-1)! for prime p.

Example

a(2) = 1: (12).
a(3) = 2: (123), (132).
a(4) = 3: (12)(34), (13)(24), (14)(23).
a(5) = 24: (12345), (12354), (12435), (12453), (12534), (12543), (13245), (13254), (13425), (13452), (13524), (13542), (14235), (14253), (14325), (14352), (14523), (14532), (15234), (15243), (15324), (15342), (15423), (15432).

Maple

b:= proc(n, g) option remember; `if`(n=0, `if`(isprime(g), 1, 0),
      add(b(n-j, igcd(j, g))*(n-1)!/(n-j)!, j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..23);

Mathematica

b[n_, g_] := b[n, g] = If[n == 0, If[PrimeQ[g], 1, 0], Sum[b[n - j, GCD[j, g]]*(n - 1)!/(n - j)!, {j, 1, n}]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Dec 13 2023, after Alois P. Heinz *)

Crossrefs

Cf. A000040, A000142, A005225, A079128, A214003, A346085, A346086.

Sequence in context: A047157 A353165 A003221 * A013312 A013318 A193338

Adjacent sequences: A359948 A359949 A359950 * A359952 A359953 A359954

Keyword

nonn

Author

Alois P. Heinz, Jan 19 2023

Status

approved