150 Friends Problem - 2

$150150=2\times3\times5^2\times7\times11\times13$ Excepting $5^2$ ,the remaining 5 elements are distinguishable and the number of ways to arrange them into 6 different variables is $6^5$ . In these $6^5$ arrangements, $2$ indistinguishable $5$ are to be arranged into 6 different variables. By Stars and Bars there are $\binom{6+2-1}{2} = 21$ ways to arrange them $6^5 \times 21 = 163296$

My solution is same as Vishnu but just more general.

Let this be our problem -

$\displaystyle a_1 a_2 a_3 \cdots a_m = n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}$

Now, one can see that $\displaystyle a_i = p_1^{x_{i,1}} p_2^{x_{i,2}} \cdots p_n^{x_{i,n}}$

such that $\displaystyle \prod_i{a_i} = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}$ which gives us that

$\displaystyle x_{1,j} + x_{2,j} + x_{3,j} + \cdots + x_{m,j} = \alpha_j , x_{k,j}\geq 0$

giving us the number of solutions for $\displaystyle \alpha_j$ by generating functions $\displaystyle = \dbinom{m + \alpha_j -1}{m-1}$

and the similar results will be there for all $\displaystyle \alpha$ 's, thus giving by Law of multiplication,

$\displaystyle \text{Total number of solutions for} (a_1 a_2 a_3 \cdots a_m = n) = \prod_{j=1}^{n}{\dbinom{m+\alpha_j-1}{m-1}}$

In general, let the prime decomposition of $n$ be $n = p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$ with $1 < p_1 < p_2 < \dots < p_n$ .

Each prime factor must be assigned to one of the six factors $a, b, c, d, e, f$ . If there are $e_i$ factors $p_i$ , then this assignment can be made in $\left(\begin{array}{c} 5+e_i \\ 5 \end{array}\right)$ ways. Multiplying gives $N = \left(\begin{array}{c} 5+e_1 \\ 5 \end{array}\right) \cdot \left(\begin{array}{c} 5+e_2 \\ 5 \end{array}\right) \cdots \left(\begin{array}{c} 5+e_n \\ 5 \end{array}\right).$

For $n = 150150$ , $150150 = 150\times 1100 = 2\times 3 \times 5^2 \times 7 \times 11 \times 13,$ so that $N = \left(\begin{array}{c} 6 \\ 5 \end{array}\right)^5 \cdot \left(\begin{array}{c} 7 \\ 5 \end{array}\right) = 6^5\times 21 = 163296.$