Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{a_2} \cdot \ldots \cdot n^{a_n}\mid a_i\geq 0, a_1+a_2+\ldots+a_n=m \}$.
How many results can be obtained?
Denote this number with $P(m,n)$ (the number of elements of the set defined above).
For example, if $m=1$, then $P(1,n)=n$.
Similarly, we have:
$P(m,1)=1$,
$P(m,2)=m+1$.
Moreover, if $n=p$ is prime then it is not difficult to see that
$$P(m,p)=\sum_{i=0}^{m}P(i,p-1).$$
(We define $P(0,n)$ to be equal $1$ for any $n$.)
Furhter, using the above property one can obtain the values of $P(m,n)$, for some small values of $n$, for example for $n\leq 10$ we have:
$P(m,3)=\binom{m+2}{2}$;
$P(m,4)=(m+1)^2$;
$P(m,5)=\frac{(m+1)(m+2)(2m+3)}{6}$
$P(m,6)=(m+1){{m+2}\choose{2}}$;
$P(m,7)=\frac{(m+1)(m+2)(m+3)(3m+4)}{24}$;
$P(m,8)=\frac{(m+1)^2(m+2)(m+3)}{6}$;
$P(m,9)=\frac{(m+1)^2(m+2)^2}{4}$;
$P(m,10)=\frac{(m+1)^2(m+2)(2m+3)}{6}$.
Is there a general method that would give precise value of $P(m,n)$ for any $m$ and $n$? Or at least an approximation of $P(m,n)$?
Best Answer
If you fix $m$, this is known as the $m$-dimensional multiplication problem. In 2010 Koukoulopoulos showed that as $n\rightarrow \infty$ $$P(m,n)=\left|\lbrace a_1\cdots a_m\ :\ a_i\leq n \text{ for all } \ i\rbrace\right|\asymp \frac{n^{m+1}}{(\log n)^{c_m}(\log\log n)^{3/2}}$$ where $$c_{m}=\int_{1}^{\frac{k}{\log(m+1)}}\log x\text{d}x=\frac{\log(m+1)+m\log\left(m\right)-m\log\log(m+1)-m}{\log(m+1)}.$$ See this answer for more details.
For $m\rightarrow \infty$, and $n$ fixed your calculations show that the order of magnitude looks like $m^{\pi(n)}$ where $\pi(n)=\sum_{p\leq n}1$ denotes the number of primes less that $n$. By considering those primes $p\leq n$, it is easy to see that we have a lower bound for $P(n,m)$ of this form. In what follows, by using Rankin's trick I will obtain the bound $$P(n,m)\leq m^{\pi(n)} e^{2n}\ \ \ \ \ \ \ \ \ \ \ (1) $$ which holds for any $m$ and $n\geq 3$. (Of course this bound is only strong when $n$ is very small compared to $m$) From this, it follows that for $n$ fixed and $m\rightarrow \infty$ we obtain the correct order of magnitude $$P(n,m)\asymp m^{\pi(n)}.$$
Notice that every element in your set lies in ${1,\dots,n^m}$, and has no prime factor larger than $n$. Let $S(y)=\{n\in\mathbb{Z}:P(n)\leq y\}$ where $P(n)$ is the largest prime factor of $n$. Then $$P(n,m)\leq \sum_{\begin{array}{c} k\leq n^{m}\\ k\in S(n) \end{array}}1.$$
For any $\sigma>0$, since $\sum_{n=1,\ n\in S(y)}^\infty n^{-\sigma}=\prod_{p\leq y} \left(1-1/p^\sigma\right)^{-1}$, we have that $$P(n,m)\leq \sum_{\begin{array}{c} k\leq n^{m}\\ k\in S(n) \end{array}}\frac{n^{\sigma m}}{k^\sigma}=n^{\sigma m} \prod_{p\leq n}\left(1-\frac{1}{p^\sigma}\right)^{-1}.$$ Since $1-p^{-\sigma}\geq\frac{\sigma\log p}{2}$, it follows that $$\prod_{p\leq n}\left(1-p^{-\sigma}\right)^{-1}\leq2^{\pi(n)}\sigma^{-\pi(n)}\prod_{p\leq n}\frac{1}{\log p}\leq2^{\pi(n)}\sigma^{-\pi(n)}. $$
Choosing $\sigma=\pi(n)/m$, it follows that $$P(n,m)\leq m^{\pi(n)}n^{\pi(n)}2^{\pi(n)}\pi(n)^{-\pi(n)}.$$ Applying the Brun-Titchmarsh theorem, we obtain equation $(1)$ for all $m,n$ with $n\geq 3$.