cp's OEIS Frontend

A346121 Number of permutations of [n] whose order is a multiple of n.

%I A346121 #23 Aug 23 2021 10:22:33
%S A346121 1,1,2,6,24,240,720,5040,40320,816480,3628800,108108000,479001600,
%T A346121 14789174400,254431457280,1307674368000,20922789888000,
%U A346121 872545722048000,6402373705728000,411616608508385280,7817896752906240000,128126503414990080000,1124000727777607680000
%N A346121 Number of permutations of [n] whose order is a multiple of n.
%H A346121 Alois P. Heinz, <a href="/A346121/b346121.txt">Table of n, a(n) for n = 1..450</a>
%H A346121 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%F A346121 a(n) = Sum_{i>=1} A057731(n,i*n).
%F A346121 a(n) = (n-1)! <=> n in { A000961 }.
%F A346121 a(n) = A057731(n,n) = A074351(n) = A052699(n-1) for n <= 9.
%p A346121 b:= proc(n, g) option remember; `if`(n=0, x^g, add((j-1)!
%p A346121       *b(n-j, ilcm(g, j))*binomial(n-1, j-1), j=1..n))
%p A346121     end:
%p A346121 a:= n-> (p-> add(coeff(p, x, i*n), i=1..degree(p)/n))(b(n, 1)):
%p A346121 seq(a(n), n=1..23);
%p A346121 # second Maple program:
%p A346121 h:= proc(n, j) option remember; uses padic, numtheory; n/mul(`if`(
%p A346121       ordp(j, p)<ordp(n, p), 1, p^ordp(n, p)), p=factorset(igcd(n, j)))
%p A346121     end:
%p A346121 b:= proc(n, m) option remember; `if`(n=0, `if`(m=1, 1, 0),
%p A346121       add((j-1)!*b(n-j, h(m, j))*binomial(n-1, j-1), j=1..n))
%p A346121     end:
%p A346121 a:= n-> b(n$2):
%p A346121 seq(a(n), n=1..23);
%t A346121 b[n_, g_] := b[n, g] = If[n == 0, x^g, Sum[(j - 1)!*b[n - j, LCM[g, j]]* Binomial[n - 1, j - 1], {j, 1, n}]] // Expand;
%t A346121 a[n_] := With[{p = b[n, 1]}, Sum[Coefficient[p, x, i*n], {i, 1, Exponent[p, x]/n}]];
%t A346121 Array[a, 40] (* _Jean-François Alcover_, Aug 23 2021, after _Alois P. Heinz_'s first program *)
%Y A346121 Cf. A000142, A000961, A052699, A057731, A074351, A074759.
%K A346121 nonn
%O A346121 1,3
%A A346121 _Alois P. Heinz_, Jul 05 2021