A079128 Number of degree-n permutations with (mutually) relatively prime cycle lengths.

1, 1, 4, 15, 96, 455, 4320, 29295, 300160, 2663199, 36288000, 348523175, 5748019200, 68027248575, 1116542242816, 16813959537375, 334764638208000, 4954072089341375, 115242726703104000, 1966765155600364119, 45415699475660800000, 930312555383281809375

Offset: 1

Author

Vladeta Jovovic, Vladimir Baltic, Dec 27 2002

Keywords

• nonn

Comments

a(p) = p!-(p-1)! for prime p. Conjecture: a(n) is divisible by n^2-1 for n>3.

Conjecture: gcd(a(n),n)=1. - Vladeta Jovovic, Jan 25 2003

Links

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

Crossrefs

Cf. A079129, A000837, A079129, A226388.

Programs

Maple

with(combinat):
b:= proc(n, i, g) option remember; `if`(n=0, `if`(g>=2, 1, 0),
      `if`(i<2, 0, b(n, i-1, g) +`if`(igcd(g, i)<2, 0,
       add((i-1)!^j/j! *multinomial(n, i$j, n-i*j)*
         b(n-i*j, i-1, igcd(i, g)), j=1..n/i))))
    end:
a:= n-> n!-b(n, n, 0):
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 06 2013
# second Maple program:
b:= proc(n, g) option remember; `if`(n=0, `if`(g=1, 1, 0), add(
      (j-1)!*b(n-j, igcd(g, j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..25);  # Alois P. Heinz, Jul 03 2021

Mathematica

f[list_] :=
Total[list]!/Apply[Times, Table[list[[i]], {i, 1, Length[list]}]]/
  Apply[Times, Select[Table[Count[list, i], {i, 1, Total[list]}], # > 0 &]!];
Table[Total[Map[f, Select[IntegerPartitions[n], Apply[GCD, #] == 1 &]]], {n, 1, 25}] (* Geoffrey Critzer, Jun 06 2013 *)
multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_, g_] := b[n, i, g] = If[n==0, If[g >= 2, 1, 0], If[i<2, 0, b[n, i-1, g] + If[GCD[g, i]<2, 0, Sum[(i-1)!^j/j!*multinomial[n, Append[Array[i&, j], n-i*j]]*b[n-i*j, i-1, GCD[i, g]], {j, 1, n/i}]]]]; a[n_] := n! - b[n, n, 0]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)