You are given positive integers $N$ and $M$ .

How many sequences a of length N consisting of positive integers satisfy $a_1 \times a_2 \times ... \times a_n = M$ ?

Here , two sequences $a'$ and $a''$ are considered different when there exists some $i$ such that $ai' != ai''$ .

For example $N = 2$ and $M = 6$, the answer is $4$.

$\{a_1 , a_2 \} = \{ (1,6) (2,3) (3,2) (6,1) \}$


The different prime factors are independent.
In your example, the 2 could appearas $(1,2)$ or $(2,1)$, and the 3 could be $(1,3)$ or $(3,1)$. Multiply them together, for example $(1,2)\times(1,3)=(1\times1,2\times3)=(1,6)$.
Now how many ways can $p^k$ be placed in $N$ spots? This is a good use of stars and bars.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.