cp's OEIS Frontend

A327399 Number of factorizations of n that are constant or whose distinct factors are pairwise coprime.

%I A327399 #15 Aug 22 2025 10:32:28
%S A327399 1,1,1,2,1,2,1,2,2,2,1,3,1,2,2,3,1,3,1,3,2,2,1,3,2,2,2,3,1,5,1,2,2,2,
%T A327399 2,6,1,2,2,3,1,5,1,3,3,2,1,4,2,3,2,3,1,3,2,3,2,2,1,7,1,2,3,4,2,5,1,3,
%U A327399 2,5,1,5,1,2,3,3,2,5,1,4,3,2,1,7,2,2,2
%N A327399 Number of factorizations of n that are constant or whose distinct factors are pairwise coprime.
%C A327399 First differs from A327400 at A327400(24) = 4, a(24) = 3.
%C A327399 From _Jianing Song_, Jun 09 2025: (Start)
%C A327399 Let n = (p_1)^(e_1) * ... * (p_r)^(e_r), then a(n) is the number of partitions of the multiset formed by e_1 1's, e_2 2's, ..., e_r r's such that each pair of parts is either equal or nonintersecting. Let's call such a partition a (e_1,...,e_r)-partition of {1,2,...,r}.
%C A327399 Note that every (e_1,...,e_r)-partition has a base partition by removing duplicates of parts and elements in each part (e.g., {{1,2,2},{1,2,2},{3,3},{4}} -> {{1,2},{3},{4}}), and the base partition is itself a partition on {1,2,...,r}. Since the number of partitions into identical parts of the multiset formed by e_{i_1} (i_1)'s, ..., e_{i_k} (i_k)'s is d(gcd(e_{i_1},...,e_{i_k})), where d = A000005, the number of (e_1,...,e_r)-partitions having base partition P of {1,2,...,r} is Product_{S in P} d(gcd_{i in S} (e_i)). As a result, the number (e_1,...,e_r)-partitions is Sum_{P is a partition of {1,2,...,r}} Product_{S in P} d(gcd_{i in S} (e_i)).
%C A327399 Examples:
%C A327399   # of e_1-partitions = d(e_1);
%C A327399   # of (e_1,e_2)-partitions = d(gcd(e_1,e_2)) + d(e_1)*d(e_2);
%C A327399   # of (e_1,e_2,e_3)-partitions = d(gcd(e_1,e_2,e_3)) + d(gcd(e_1,e_2))*d(e_3) + d(gcd(e_1,e_3))*d(e_2) + d(gcd(e_2,e_3))*d(e_1) + d(e_1)*d(e_2)*d(e_3);
%C A327399   # of (e_1,e_2,e_3,e_4)-partitions = d(gcd(e_1,e_2,e_3,e_4)) + (d(gcd(e_1,e_2,e_3))*d(e_4) + ...) + (d(gcd(e_1,e_2))*d(gcd(e_3,e_4)) + ...) + (d(gcd(e_1,e_2))*d(e_3)*d(e_4) + ...) + d(e_1)*d(e_2)*d(e_3)*d(e_4).
%C A327399 (End)
%H A327399 Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vSX9dPMGJhxB8rOknCGvOs6PiyhupdWNpqLsnphdgU6MEVqFBnWugAXidDhwHeKqZe_YnUqYeGOXsOk/pub">Sequences counting and encoding certain classes of multisets</a>
%F A327399 a(n) = A327695(n) + A089723(n).
%e A327399 The a(90) = 7 factorizations together with the corresponding multiset partitions of {1,2,2,3}:
%e A327399   (2*3*3*5)  {{1},{2},{2},{3}}
%e A327399   (2*5*9)    {{1},{3},{2,2}}
%e A327399   (2*45)     {{1},{2,2,3}}
%e A327399   (3*3*10)   {{2},{2},{1,3}}
%e A327399   (5*18)     {{3},{1,2,2}}
%e A327399   (9*10)     {{2,2},{1,3}}
%e A327399   (90)       {{1,2,2,3}}
%t A327399 facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
%t A327399 Table[Length[Select[facs[n],Length[Union[#]]==1||CoprimeQ@@Union[#]&]],{n,100}]
%Y A327399 Constant factorizations are A089723.
%Y A327399 Partitions whose distinct parts are pairwise coprime are A304709.
%Y A327399 Factorizations that are constant or relatively prime are A327400.
%Y A327399 See link for additional cross-references.
%Y A327399 Cf. A007359, A050320, A051424, A281116, A302569, A302696, A304711.
%K A327399 nonn
%O A327399 1,4
%A A327399 _Gus Wiseman_, Sep 22 2019