Multiplicative partitions

This article page is a stub, please help by expanding it.

Multiplicative partitions
(sorted by nondecreasing number of factors, then factors are in nondecreasing order)

n	Set of bags
1	{ { } }
2	{ {2} }
3	{ {3} }
4	{ {4}, {2, 2} }
5	{ {5} }
6	{ {6}, {2, 3} }
7	{ {7} }
8	{ {8}, {2, 4}, {2, 2, 2} }
9	{ {9}, {3, 3} }
10	{ {10}, {2, 5} }
11	{ {11} }
12	{ {12}, {2, 6}, {3, 4}, {2, 2, 3} }

A multiplicative partition or unordered factorization of a positive integer

n

is a way of writing

n

as a product of integers greater than 1, where two products are considered equivalent if they differ only in the ordering of the factors.

Examples giving the set of multiplicative partitions (each multiplicative partition expressed as a bag (multiset) of integers greater than 1) of

n

:

• 1 has one multiplicative partition (since the empty product is defined as the multiplicative identity, i.e. 1): { ∅ } = { { } };

• p

  , where

  p

  is prime, has one multiplicative partition: { {  p} };
• 12 has four multiplicative partitions: { {2, 2, 3}, {2, 6}, {3, 4}, {12} };
• 60 has eleven multiplicative partitions: { {2, 2, 3, 5}, {2, 2, 15}, {2, 3, 10}, {2, 5, 6}, {3, 4, 5}, {2, 30}, {3, 20}, {4, 15}, {5, 12}, {6, 10}, {60} }.
  
  

A162247 Irregular triangle in which row

n, n   ≥   2,

lists all factorizations of

n

, sorted by [increasing] number of factors in each factorization. (The factors are then in nondecreasing order.)

{2, 3, 4, 2, 2, 5, 6, 2, 3, 7, 8, 2, 4, 2, 2, 2, 9, 3, 3, 10, 2, 5, 11, 12, 2, 6, 3, 4, 2, 2, 3, 13, 14, 2, 7, 15, 3, 5, 16, 2, 8, 4, 4, 2, 2, 4, 2, 2, 2, 2, 17, 18, 2, 9, 3, 6, 2, 3, 3, 19, 20, 2, 10, 4, 5, ...}

Since the prime factors (with multiplicity) of a positive integer

n

constitute a bag (multiset), the multiplicative partitions of

n

correspond to partitions of the multiset of the prime factors (with multiplicity) of

n

.

Previous examples, expressed as the set of partitions of the multiset (each multiset partition being a multiset of multisets) of the prime factors (with multiplicity) of

n

:

• 1: { { ∅ } } = { { { } } };
• p : { { {  p} } };
• 12: { { {2}, {2}, {3} }, { {2}, {2, 3} }, { {3}, {2, 2} }, { {2, 2, 3} } };
• 60: { { {2}, {2}, {3}, {5} }, { {2}, {2}, {3, 5} }, { {2}, {3}, {2, 5} }, { {2}, {5}, {2, 3} }, { {3}, {2, 2}, {5} }, { {2}, {2, 3, 5} }, { {3}, {2, 2, 5} }, { {2, 2}, {3, 5} }, { {5}, {2, 2, 3} }, { {2, 3}, {2, 5} }, { {2, 2, 3, 5} } }.
  
  

Since the prime factors of a squarefree integer constitute a set (instead of a multiset in the case of a nonsquarefree integer), the number of multiplicative partitions of a squarefree integer corresponds to partitions of the set of the prime factors (which are all distinct in this case) of

n

.

Multiplicative partition function

A001055 The multiplicative partition function: number of ways of factoring

n

with all factors greater than 1 (

a (1) = 1

since the empty product is defined as the multiplicative identity, i.e. 1).

{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 4, 11, 2, 5, 1, 4, 2, 5, 1, 16, 1, 2, 4, 4, 2, 5, 1, 12, 5, ...}

Multiplicative partition function of squarefree numbers

Since the prime factors of a squarefree integer constitute a set (instead of a multiset in the case of a nonsquarefree integer), the number of multiplicative partitions of a squarefree integer with

i

prime factors corresponds to the number of partitions of a set with

i

members, which is the

i

-th Bell number,

Bi

.

A000110 Bell or exponential numbers: number of ways to partition a set of

n, n   ≥   0,

labeled elements.

{1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, ...}

See also

• Multiplicative compositions (or ordered factorizations)

External links

• Weisstein, Eric W., Unordered Factorization, from MathWorld—A Wolfram Web Resource.