login
A359951
Number of permutations of [n] such that the GCD of the cycle lengths is a prime.
2
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
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 *)
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jan 19 2023
STATUS
approved