|
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. |
|||||||||||||
|
|
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. |
|||||
|
