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

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, 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, 0, 0, 0, 10, 0, 0, 1, 1, 0, 0, 0, 7, 4, 0, 0, 2, 0, 0

Offset: 1

Author

Gus Wiseman, Dec 27 2023

Keywords

• nonn

Comments

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).

Examples

			The a(1) = 0 through a(24) = 3 factorizations:
 ... 2*2 ... 2*4   3*3 .. 2*2*3 ... 2*8     . 2*3*3 . 2*2*5 ... 2*2*6
             2*2*2                  4*4                         2*3*4
                                    2*2*4                       2*2*2*3
                                    2*2*2*2
		

Crossrefs

For unlabeled graphs: A140637, complement A134964.

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

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

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

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

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

The complement is counted by A368414.

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

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

A001055 counts factorizations, strict A045778.

A007716 counts non-isomorphic multiset partitions, connected A007718.

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

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

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

Programs

Mathematica

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&, Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]=={}&]],{n,100}]

Formula

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