Question

Suppose that M is the product of k distinct primes. Find the number of ways to write N as the product of positive integers(>1), where the order of terms does not matter.

(a) ^MCN-k

(b) ^NCM

(c) N * Bk

(d) Bk

This question was posed to me in unit test.

Query is from Counting in section Counting of Discrete Mathematics

Answer 1

Correct choice is (d) Bk

The explanation: To solve the problem first find the prime factorization of each term of the product, and place the factors of each term into a box. Then, since N is the product of distinct prime factors, each prime factor appears in a unique box. Since the product of all of these terms is N, each prime factor must be in a box. Conversely, for any arrangement of these n distinct primes into r identical boxes, multiply the primes in a box to create a term and the product of these terms results in N. This establishes the bijection and the number of ways is Bk which is Bell number.