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

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 6, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

Offset

1,6

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 not counted under a(36).

Links

Table of n, a(n) for n=1..87.

Formula

a(n) = A001055(n) - A368413(n).

Example

The a(n) factorizations for selected n:
  1    6      12     24      30       60        72      120
       2*3    2*6    2*12    2*15     2*30      2*36    2*60
              3*4    3*8     3*10     3*20      3*24    3*40
                     4*6     5*6      4*15      4*18    4*30
                             2*3*5    5*12      6*12    5*24
                                      6*10      8*9     6*20
                                      2*3*10            8*15
                                      2*5*6             10*12
                                      3*4*5             2*3*20
                                                        2*5*12
                                                        2*6*10
                                                        3*4*10
                                                        3*5*8
                                                        4*5*6

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}]

Crossrefs

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

For unlabeled graphs: A134964, complement A140637.

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

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

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

For non-isomorphic multiset partitions: A368098, A368100.

The complement is counted by A368413.

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

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, A368413.

Sequence in context: A349056 A326516 A081707 * A303707 A335521 A323087

Adjacent sequences: A368411 A368412 A368413 * A368415 A368416 A368417

Keyword

nonn

Author

Gus Wiseman, Dec 29 2023

Status

approved