cp's OEIS Frontend

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

%I A226388 #23 Jul 04 2021 15:02:30
%S A226388 0,0,1,2,9,24,265,720,11025,62720,965601,3628800,130478425,479001600,
%T A226388 19151042625,191132125184,4108830350625,20922789888000,
%U A226388 1448301616386625,6402373705728000,466136852576275881,5675242696048640000,193688172394325870625,1124000727777607680000
%N A226388 Number of n-permutations such that all cycle lengths have a common divisor >= 2.
%C A226388 a(p) = (p-1)! for p a prime.
%H A226388 Alois P. Heinz, <a href="/A226388/b226388.txt">Table of n, a(n) for n = 0..200</a>
%F A226388 a(n) = n! - A079128(n) for n >= 1. - _Alois P. Heinz_, Jul 04 2021
%e A226388 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.
%p A226388 with(combinat):
%p A226388 b:= proc(n, i, g) option remember; `if`(n=0, `if`(g>1, 1, 0),
%p A226388       `if`(i<2, 0, b(n, i-1, g) +`if`(igcd(g, i)<2, 0,
%p A226388        add((i-1)!^j/j! *multinomial(n, i$j, n-i*j)*
%p A226388          b(n-i*j, i-1, igcd(i, g)), j=1..n/i))))
%p A226388     end:
%p A226388 a:= n-> b(n, n, 0):
%p A226388 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jun 06 2013
%p A226388 # second Maple program:
%p A226388 b:= proc(n, g) option remember; `if`(n=0, `if`(g>1, 1, 0), add(
%p A226388       (j-1)!*b(n-j, igcd(g, j))*binomial(n-1, j-1), j=1..n))
%p A226388     end:
%p A226388 a:= n-> b(n, 0):
%p A226388 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jul 04 2021
%t A226388 f[list_] :=
%t A226388 Total[list]!/Apply[Times, Table[list[[i]], {i, 1, Length[list]}]]/
%t A226388   Apply[Times,
%t A226388    Select[Table[
%t A226388       Count[list, i], {i, 1, Total[list]}], # > 0 &]!]; Table[
%t A226388 Total[Map[f, Select[Partitions[n], Apply[GCD, #] > 1 &]]], {n, 0,
%t A226388   25}]
%Y A226388 Cf. A000142, A079128, A335088.
%K A226388 nonn
%O A226388 0,4
%A A226388 _Geoffrey Critzer_, Jun 05 2013