login
Number of permutations of a multiset whose multiplicities are the prime indices of n.
27

%I #23 Oct 16 2023 01:32:08

%S 1,1,1,2,1,3,1,6,6,4,1,12,1,5,10,24,1,30,1,20,15,6,1,60,20,7,90,30,1,

%T 60,1,120,21,8,35,180,1,9,28,120,1,105,1,42,210,10,1,360,70,140,36,56,

%U 1,630,56,210,45,11,1,420,1,12,420,720,84,168,1,72,55

%N Number of permutations of a multiset whose multiplicities are the prime indices of n.

%C This multiset is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

%H Alois P. Heinz, <a href="/A318762/b318762.txt">Table of n, a(n) for n = 1..20000</a>

%F If n = Product prime(x_i)^y_i is the prime factorization of n, then a(n) = (Sum x_i * y_i)! / Product (x_i!)^y_i.

%F a(n) = A008480(A181821(n)).

%F a(n) = A112624(n) * A124794(n). - _Max Alekseyev_, Oct 15 2023

%F Sum_{m in row n of A215366} a(m) = A005651(n).

%F Sum_{m in row n of A215366} a(m) * A008480(m) = A000670(n).

%F Sum_{m in row n of A215366} a(m) * A008480(m) / A001222(m)! = A000110(n).

%e The a(12) = 12 permutations are (1123), (1132), (1213), (1231), (1312), (1321), (2113), (2131), (2311), (3112), (3121), (3211).

%p a:= n-> (l-> add(i, i=l)!/mul(i!, i=l))(map(i->

%p numtheory[pi](i[1])$i[2], ifactors(n)[2])):

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Sep 03 2018

%t primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t Table[Total[primeMS[n]]!/Times@@Factorial/@primeMS[n],{n,100}]

%o (PARI) sig(n)={my(f=factor(n)); concat(vector(#f~, i, vector(f[i, 2], j, primepi(f[i, 1]))))}

%o a(n)={if(n==1, 1, my(s=sig(n)); vecsum(s)!/prod(i=1, #s, s[i]!))} \\ _Andrew Howroyd_, Dec 17 2018

%Y Cf. A000041, A000110, A000258, A000670, A005651, A008277, A008480, A056239, A112624, A112798, A124794, A215366, A300335, A305936.

%K nonn,look

%O 1,4

%A _Gus Wiseman_, Sep 03 2018