Combinatorics and Graph Theory · Problem 1.4.2

Fundamentals — David Guichard

Mathematics — Combinatorics · counting-factorizations

Problem

Suppose

n

is a square-free number, that is, no number

m^2

divides

n

; put another way, square-free numbers are products of distinct prime factors, that is,

n = p_1 p_2 \cdots p_k

, where each

p_i

is prime and no two prime factors are equal. Find the number of factorizations of

n

. For example,

30 = 2 \cdot 3 \cdot 5

, and the factorizations of 30 are

30

6 \cdot 5

10 \cdot 3

2 \cdot 15

, and

2 \cdot 3 \cdot 5

. Note we count 30 alone as a factorization, though in some sense a trivial factorization.