login
Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.
41

%I #21 Mar 06 2024 14:47:25

%S 0,0,0,1,0,0,0,2,1,0,0,1,0,0,0,4,0,1,0,1,0,0,0,3,1,0,2,1,0,0,0,6,0,0,

%T 0,4,0,0,0,3,0,0,0,1,1,0,0,7,1,1,0,1,0,3,0,3,0,0,0,2,0,0,1,10,0,0,0,1,

%U 0,0,0,10,0,0,1,1,0,0,0,7,4,0,0,2,0,0

%N Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.

%C For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is counted under a(36).

%F a(n) + A368414(n) = A001055(n).

%e The a(1) = 0 through a(24) = 3 factorizations:

%e ... 2*2 ... 2*4 3*3 .. 2*2*3 ... 2*8 . 2*3*3 . 2*2*5 ... 2*2*6

%e 2*2*2 4*4 2*3*4

%e 2*2*4 2*2*2*3

%e 2*2*2*2

%t facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&, Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];

%t Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]=={}&]],{n,100}]

%Y For unlabeled graphs: A140637, complement A134964.

%Y For labeled graphs: A367867, A367868, A140638, complement A133686.

%Y For set-systems: A367903, ranks A367907, complement A367902, ranks A367906.

%Y For non-isomorphic set-systems: A368094, A368409, complement A368095.

%Y For non-isomorphic multiset partitions: A368097, A355529, A368411.

%Y Complement for non-isomorphic multiset partitions: A368098, A368100.

%Y The complement is counted by A368414.

%Y For non-isomorphic set multipartitions: A368421, complement A368422.

%Y For divisors instead of prime factors: A370813, complement A370814.

%Y A001055 counts factorizations, strict A045778.

%Y A007716 counts non-isomorphic multiset partitions, connected A007718.

%Y A058891 counts set-systems, unlabeled A000612, connected A323818.

%Y A283877 counts non-isomorphic set-systems, connected A300913.

%Y Cf. A340596, A340653, A367769, A367901, A368187, A368412.

%K nonn

%O 1,8

%A _Gus Wiseman_, Dec 27 2023