Let $d_{3}(n)$ denote the number of ordered 3-tuples of positive integers whose product is $n$ and $\omega(n)$ the number of distinct primes dividing $n$. How does one show that $3^{\omega(n)} \geq d_{3}(n)$ for every $n$?
Inequality involving $\omega(n)$
-
0One doesn't. If $n$ is, say, $2^{10}$, then $\omega(n)=1$, so $3^{\omega(n)}=3$, but $d_3(2^{10})$ is a lot bigger than $3$. – 2012-11-29
1 Answers
As pointed out in the comments this is false. But, write $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$, the prime decomposition of $n$. Then define $\theta(n)=\alpha_1+\ldots+\alpha_k$. Now suppose $(a,b,c)$ is an ordered 3-tuple whose product is $n$. Clearly, $a,b,c$ can be written solely as products of powers of the primes $p_1,\ldots,p_k$. In particular, think of $n$ writen as $n=p_1\cdots p_1\cdot p_2\cdots p_2\cdots$, where each prime appears $\alpha_i$ times. To form a tuple $(a,b,c)$ we just need to ask in how many ways can we partition $\alpha_1+\alpha_2+\ldots+\alpha_n$ primes amoungst $(a,b,c)$. We can think of each prime recieving a number $1,2,3$ indicating it belongs to $a,b,c$ respectively. But this doesn't take into account the multiplicity of the primes, so we can bound this above by just selecting 1,2, or 3 for each prime, giving 3 choices for each prime for a total of $3\cdot3\cdot 3\ldots$ , $\theta(n)$ times, giving $3^{\theta(n)}$.