A079128 -id:A079128 - cp's OEIS frontend

A324514 Number of aperiodic permutations of {1..n}.

1, 0, 3, 16, 115, 660, 5033, 39936, 362718, 3624920, 39916789, 478953648, 6227020787, 87177645996, 1307674338105, 20922779566080, 355687428095983, 6402373519409856, 121645100408831981, 2432902004460734000, 51090942171698415483, 1124000727695858073380

Offset: 1

Gus Wiseman, Mar 04 2019

nonn

A permutation is defined to be aperiodic if every cyclic rotation of {1..n} acts on the cycle decomposition to produce a different digraph.

			The a(4) = 16 aperiodic permutations:
  (1243) (1324) (1342) (1423)
  (2134) (2314) (2413) (2431)
  (3124) (3142) (3241) (3421)
  (4132) (4213) (4231) (4312)

Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, Cycle decompositions of the a(4) = 16 aperiodic permutations.

Cf. A000740, A000939, A027375, A061417, A079128, A086675, A192332, A323860, A323867, A323869.

Cf. A306669, A324461, A324462, A324512, A324513, A324514.

Table[Length[Select[Permutations[Range[n]],UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]&]],{n,6}]

a(n) = sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019

a(n) = A306669(n) * n.

a(n) = Sum_{d|n} mu(n/d)*(n/d)^d*d!. - Andrew Howroyd, Aug 19 2019

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

A346085 Number T(n,k) of permutations of [n] such that k is the GCD of the cycle lengths; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 4, 0, 2, 0, 15, 3, 0, 6, 0, 96, 0, 0, 0, 24, 0, 455, 105, 40, 0, 0, 120, 0, 4320, 0, 0, 0, 0, 0, 720, 0, 29295, 4725, 0, 1260, 0, 0, 0, 5040, 0, 300160, 0, 22400, 0, 0, 0, 0, 0, 40320, 0, 2663199, 530145, 0, 0, 72576, 0, 0, 0, 0, 362880

Offset: 0

Alois P. Heinz, Jul 04 2021

			T(3,1) = 4: (1)(23), (13)(2), (12)(3), (1)(2)(3).
T(4,4) = 6: (1234), (1243), (1324), (1342), (1423), (1432).
Triangle T(n,k) begins:
  1;
  0,       1;
  0,       1,      1;
  0,       4,      0,     2;
  0,      15,      3,     0,    6;
  0,      96,      0,     0,    0,    24;
  0,     455,    105,    40,    0,     0, 120;
  0,    4320,      0,     0,    0,     0,   0, 720;
  0,   29295,   4725,     0, 1260,     0,   0,   0, 5040;
  0,  300160,      0, 22400,    0,     0,   0,   0,    0, 40320;
  0, 2663199, 530145,     0,    0, 72576,   0,   0,    0,     0, 362880;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Permutation

Columns k=0-1 give: A000007, A079128.
Even bisection of column k=2 gives A346086.
Row sums give A000142.
T(2n,n) gives A110468(n-1) for n >= 1.
Cf. A057731, A145877, A346066, A359951.

b:= proc(n, g) option remember; `if`(n=0, x^g, add((j-1)!
      *b(n-j, igcd(g, j))*binomial(n-1, j-1), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..12);

b[n_, g_] := b[n, g] = If[n == 0, x^g, Sum[(j - 1)!*
     b[n - j, GCD[g, j]] Binomial[n - 1, j - 1], {j, n}]];
T[n_] := CoefficientList[b[n, 0], x];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)

Sum_{k=1..n} k * T(n,k) = A346066(n).

Sum_{prime p <= n} T(n,p) = A359951(n). - Alois P. Heinz, Jan 20 2023

A226388 Number of n-permutations such that all cycle lengths have a common divisor >= 2.

Original entry on oeis.org

0, 0, 1, 2, 9, 24, 265, 720, 11025, 62720, 965601, 3628800, 130478425, 479001600, 19151042625, 191132125184, 4108830350625, 20922789888000, 1448301616386625, 6402373705728000, 466136852576275881, 5675242696048640000, 193688172394325870625, 1124000727777607680000

Offset: 0

Geoffrey Critzer, Jun 05 2013

nonn

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

			a(6) = 265 counting permutations with cycle types: 6; 4-2; 3-3; 2-2-2; of which there are 120 + 90 + 40 + 15 = 265.

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

Cf. A000142, A079128, A335088.

with(combinat):
b:= proc(n, i, g) option remember; `if`(n=0, `if`(g>1, 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-> b(n, n, 0):
seq(a(n), n=0..30);  # 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=0..30);  # Alois P. Heinz, Jul 04 2021

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[Partitions[n], Apply[GCD, #] > 1 &]]], {n, 0,
  25}]

a(n) = n! - A079128(n) for n >= 1. - Alois P. Heinz, Jul 04 2021

A079129 Number of degree-n permutations with pairwise coprime cycle lengths.

Original entry on oeis.org

1, 1, 2, 6, 21, 105, 530, 3710, 27265, 229705, 2083354, 24025694, 263359173, 3457302849, 44575118874, 600902614598, 9242750538593, 169974915437041, 2905860232733458, 56257078771371478, 1041600031067604437, 19990420041926339577, 419763750266646291714

Offset: 0

Vladeta Jovovic, Vladimir Baltic, Dec 27 2002

nonn

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

Cf. A051424, A079128.

More terms from Alois P. Heinz, Jan 10 2014

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

Original entry on oeis.org

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

Alois P. Heinz, Jan 19 2023

nonn

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

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

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

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

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

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

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

A383878 Number of permutations of [n] with distinct cycle lengths whose GCD is 1.

Original entry on oeis.org

0, 1, 0, 3, 8, 50, 264, 2394, 15840, 158976, 1490400, 20124720, 181543680, 3213905760, 36459964800, 602127540000, 9045463311360, 187660890063360, 2596164765465600, 64849189355274240, 1037566851245568000, 24684232291242854400, 498833466644833689600

Offset: 0

Alois P. Heinz, May 13 2025

nonn

			a(3) = 3: (1)(23), (13)(2), (12)(3).
a(4) = 8: (1)(234), (1)(243), (134)(2), (143)(2), (124)(3), (142)(3), (123)(4), (132)(4).

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

Cf. A079128, A382781.

b:= proc(n, i, m) option remember; `if`(i*(i+1)/2 b(n$2, 0):
seq(a(n), n=0..23);

cp's OEIS Frontend

A324514 Number of aperiodic permutations of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A346085 Number T(n,k) of permutations of [n] such that k is the GCD of the cycle lengths; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A226388 Number of n-permutations such that all cycle lengths have a common divisor >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A079129 Number of degree-n permutations with pairwise coprime cycle lengths.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A383878 Number of permutations of [n] with distinct cycle lengths whose GCD is 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple