| Displaying 1-5 of 5 results found.
page
1
Number of aperiodic permutations of {1..n}.
+10
7
1, 0, 3, 16, 115, 660, 5033, 39936, 362718, 3624920, 39916789, 478953648, 6227020787, 87177645996, 1307674338105, 20922779566080, 355687428095983, 6402373519409856, 121645100408831981, 2432902004460734000, 51090942171698415483, 1124000727695858073380
COMMENTS
A permutation is defined to be aperiodic if every cyclic rotation of {1..n} acts on the cycle decomposition to produce a different digraph.
EXAMPLE
The a(4) = 16 aperiodic permutations:
(1243) (1324) (1342) (1423)
(2134) (2314) (2413) (2431)
(3124) (3142) (3241) (3421)
(4132) (4213) (4231) (4312)
MATHEMATICA
Table[Length[Select[Permutations[Range[n]], UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n, 1, k+1]]&, #, n-1]&]], {n, 6}]
PROG
(PARI) a(n) = sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019
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.
+10
5
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
FORMULA
Sum_{k=1..n} k * T(n,k) = A346066(n).
EXAMPLE
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;
...
MAPLE
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);
MATHEMATICA
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];
CROSSREFS
Even bisection of column k=2 gives A346086. T(2n,n) gives A110468(n-1) for n >= 1.
Number of n-permutations such that all cycle lengths have a common divisor >= 2.
+10
3
0, 0, 1, 2, 9, 24, 265, 720, 11025, 62720, 965601, 3628800, 130478425, 479001600, 19151042625, 191132125184, 4108830350625, 20922789888000, 1448301616386625, 6402373705728000, 466136852576275881, 5675242696048640000, 193688172394325870625, 1124000727777607680000
COMMENTS
a(p) = (p-1)! for p a prime.
EXAMPLE
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.
MAPLE
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):
# 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):
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[Partitions[n], Apply[GCD, #] > 1 &]]], {n, 0,
25}]
Number of degree-n permutations with pairwise coprime cycle lengths.
+10
2
1, 1, 2, 6, 21, 105, 530, 3710, 27265, 229705, 2083354, 24025694, 263359173, 3457302849, 44575118874, 600902614598, 9242750538593, 169974915437041, 2905860232733458, 56257078771371478, 1041600031067604437, 19990420041926339577, 419763750266646291714
Number of permutations of [n] such that the GCD of the cycle lengths is a prime.
+10
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
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];
Search completed in 0.082 seconds
|