How many ways the number $n$ can be written as a product?

Question

How many ways the number $n$ can be written as a product?

I am only looking for the growth rate of the function. Is this an exponential function (after the number of digits $n$)?

Number $1$ can not be used. The number of factors can be completely arbitrary. We include only positive integers.

Answer 1

I'm going to assume we don't care about the order of the factors.

---

Let's look at an example:

what are the factorisations of 36?

Answer \begin{array}{|c|r|}\hline \text{$1$ part} & 36\\\hline \text{$2$ parts} & 2\cdot 18,\, 3\cdot 12,\, 4\cdot 9,\, 6\cdot 6\\\hline \text{$3$ parts} & 2\cdot 2\cdot 9,\, 2\cdot 3\cdot 6,\, 3\cdot 3\cdot 4\\\hline \text{$4$ parts} & 2\cdot 2\cdot 3\cdot 3\\\hline\end{array}

---

Using the form of the factorisations as a model we can see that a general factorisation of a number $n$ is of the form $2^{k_2}\cdot 3^{k_3}\cdot 4^{k_4}\cdots$. This suggests a dirichlet generating function (dgf)

$$\begin{align}g(z)=&(2^{-0z}+2^{-1z}+2^{-2z}+\cdots)\times\\&(3^{-0z}+3^{-1z}+3^{-2z}+\cdots)\times (4^{-0z}+4^{-1z}+4^{-2z}+\cdots)\cdots\, .\end{align}$$

Or, since $1/(1-u)=u^0+u^1+u^2+\cdots$, we have:

$$g(z)=\prod_{r=2}^{\infty}\frac{1}{1-r^{-z}}\, .\tag{1}$$

The coefficient of $n^{-z}$ is the number of factorisions of $n$.

If we are interested in the number of parts then we can tag each factor with the variable $y$ to give the $2$-variable dirichlet/ordinary generating function

$$f(y,z)=\prod_{r=2}^{\infty}\frac{1}{1-yr^{-z}}\, .\tag{2}$$

So, the coefficient of $n^{-z}y^p$ in $(2)$ is the number of factorisions of $n$ into $p$ parts.

I'm not sure about growth rates but for more on $(1)$ see this Wikipedia link or the oeis sequence A001055.

Answer 2

This is only a partial answer:

If I understand your question correctly, $p^5$, where $p$ is a prime, can be factored as: $$\begin{align}p^5\tag{1}\\p\times p^4\tag{2}\\p^2\times p^3\tag{3}\\p\times p\times p^3\tag{4}\\p\times p^2\times p^2\tag{5}\\p\times p\times p\times p^2\tag{6}\\p\times p\times p\times p\times p\tag{7}\end{align}$$

This is equivalent to solving $$p^{a_1}\times p^{a_2}\times p^{a_3}\times p^{a_4}\times p^{a_5}=p^5$$ or $$a_1+a_2+a_3+a_4+a_5=5$$ with the condition that $0\leq a_1\leq a_2\leq a_3\leq a_4\leq a_5$ (this will ensure that the order doesn't matter). The solution to the above equation is known as the partition function, which I will denote by $\rho$ to distinguish it from $p$ (indeed $\rho(5)=7$ from the example with $n=p^5$).

More generally for $n=p^k$ we need to solve $$a_1+a_2+\dots+a_k=k$$ with the condition $0\leq a_1\leq a_2\leq\dots\leq a_k$, and here the number of solutions is $\rho(k)$.

There is no known closed form for $\rho(k)$ as far as I know.