# Total number of ways to arrange the prime divisor of a number so it can be written using M digits

How many ways we can arrange all the prime divisor of a number so it can be written using M factors, where M <=T. T is the total number of prime divisor of the give number N. Example:N=27, its prime divisor is 3(repeating 3 times, so T=3). Now for a given value M=2. There are 2 ways {(3,9),(9,3)}.

The above problem can be solved using brute force approach for small value. I am trying to figure out a generic formula for the above. Please suggest.

-
$9$ is not a prime divisor. For $N=11$, there is $T=1$, hence $M\le T$ implies you want only one digit even though $11$ is a two-digit number? – Hagen von Eitzen Jan 11 '13 at 16:05
Do you mean to ask "how many ways can we arrange all the prime divisors of a number so it can be written using M factors? A digit is a numeral $0, 1, ..., 8, 9$. Also, for N = 27, there is only ONE prime divisor, and that being 3. – amWhy Jan 11 '13 at 16:05
Perhaps your question is : How many ways can a number $N$ be written as product of $M$ numbers. Or $M$ factors larger than 1. (And I suppose order of factors counts). – Maesumi Jan 11 '13 at 16:09
@amWhy,Maesumi:yeah u guys are getting it right...I have modified the question accordingly. – rspr Jan 11 '13 at 17:21
For your example of $27$, what about $(1,27)$ and $(27,1)$? Do they count? It gets easier then. – Ross Millikan Jan 11 '13 at 17:25

If you number is $N$, you can express it as a product of primes to exponents, $N=p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}$. The first thing to notice is that you don't care about the $p_i$, the number of ways will only depend upon the $e_i$
Now you can think about your factors being $M$ buckets that you put the prime factors into, multiplying all the prime factors in each bucket. The powers of $p_1$ can be distributed in the number of compositions of $e_1+M$ into $M$ parts. Each part is at least $1$ and you put one less than the part into the particular bin. For example, with $e_1=4, M=3$, you can have $7=5+1+1, 4+2+1, 3+2+2,$ and many others. These would correspond to numbers of factors of $p_1$ split $(4,0,0), (3,1,0), (2,1,1),$ and so on. The article shows that the number of compositions is then ${e_1+M-1} \choose {M-1}$. You then multiply all of these terms for each prime, so the total number is $$\prod_i {{e_i+M-1} \choose {M-1}}$$
This will include cases where one or more of the factors is $1$ because a bucket didn't get any factors at all. It is harder to count those because it makes interactions between the various primes.