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

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

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

Crossrefs

Cf. A079129, A000837, A079129, A226388.

Sequence in context: A208991 A109365 A352415 * A356524 A289489 A221095

Adjacent sequences: A079125 A079126 A079127 * A079129 A079130 A079131

Keyword

nonn

Author

Vladeta Jovovic, Vladimir Baltic, Dec 27 2002

Status

approved