[Math] Number of factorizations of distinct factors

combinatoricsnumber theory

Let $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ an integer with $p_i$ prime and $e_i \in \mathbb N$. The prime factorization can assumed to be known, i.e., we already know $p_1, \dotsc, p_k$ and $e_1, \dotsc e_k$.

Is it possible to find the number of factorizations of length $m$ of the form

$n = n_1 \cdot n_2 \dotsm n_m$ such that $n_1 < n_2 < \dotsb < n_m$ other than brute forcing?

(That means two factorizations that are just a rearrangement of each other are counted as the same one, e.g. $1 \times 2 \times 3$ is considered the same as $1 \times 3 \times 2$, so we only count those in ascending order.)

Example: For the number $n = 12 = 2^2 \cdot 3$ we have following factorizations with the factors in ascending order:

For $m=1$ we have one:

  • $12$

For $m=2$ we have three:

  • $1 \times 12$
  • $2 \times 6$
  • $3 \times 4$

For $m=3$ we have two:

  • $1 \times 2 \times 6$
  • $1 \times 3 \times 4$

Best Answer

Special cases

For $n = p_i p_2 \cdots p_k$, (all with exponent $1$), the multiplicative partitions $m_1, m_2,\dots, m_{k+1}$ are given by the coefficients of the expanded series $$f(x,k)=\dfrac{1-(k-1) x}{\prod _{n=1}^k (1-n x)}$$ where the $m$th partition of $p_1 p_2 \cdots p_k$ is give by the $(k-m+2)$th coefficient.

f[k_] := (1 - (k - 1) x)/Product[1 - n x, {n, 1, k}]
g[a_, b_] := CoefficientList[Series[f@b, {x, 0, b + a}], x][[a - b + 2]]
h[n_] := g[n, #] & /@ Range[n + 1]

h[#] & /@ Range@6

gives

\begin{array}{c} 1 & 1\\ 1 & 2 & 1\\ 1 & 4 & 4 & 1\\ 1 & 8 & 13 & 7 & 1\\ 1 & 16 & 40 & 35 & 11 & 1\\ 1 & 32 & 121 & 155 & 80 & 16 & 1\\ \end{array}

eg $30$ has partitions of length $m_1=1,\ m_2=4,\ m_3=4,\ m_4=1$:

$m_1=1$:

  • $30$

$m_2=4$:

  • $1 \times 30$
  • $2 \times 15$
  • $3 \times 10$
  • $5 \times 6$

$m_3=4$:

  • $1 \times 2 \times 15$
  • $1 \times 3 \times 10$
  • $1 \times 5 \times 6$
  • $2 \times 3 \times 5$

$m_4=1$:

  • $1 \times 2 \times 3 \times 5$

The multiplicative partitions $m_1,m_2,\dots,m_{\left\lfloor \sqrt{2 (k+1)}+1/2\right\rfloor}$ for $p^k$ (where $p$ is prime) are given by the coefficients of the expanded series $$f_1(x,k)=\dfrac{1}{\prod _{n=1}^k (1-x^n)}$$ where the $m$th partition is give by the $(m+ 1 - k(k- 1)/2)$th coefficient.

f1[k_] := 1/Product[(1 - x^n), {n, 1, k}]
g1[a_, b_] := CoefficientList[Series[f1@b, {x, 0, b + a}], x][[1 - b (b - 1)/2 + a]]
h1[n_] := g1[n, #] & /@ Range@Floor[Sqrt[2 (n + 1)] + 1/2]

h1[#] & /@ Range@6

gives

\begin{array}{c} 1 & 1\\ 1 & 1\\ 1 & 2 & 1\\ 1 & 2 & 1\\ 1 & 3 & 2\\ 1 & 3 & 3 & 1\\ \end{array}

eg $512$ has partitions of length $m_1=1,\ m_2=5,\ m_3=7,\ m_4=3$.

$m_1=1$:

  • $512$

$m_2=5$:

  • $1 \times 512$
  • $2 \times 256$
  • $4 \times 128$
  • $8 \times 64$
  • $16 \times 32$

$m_3=7$:

  • $1 \times 2 \times 256$
  • $1 \times 4 \times 128$
  • $1 \times 8 \times 64$
  • $1 \times 16 \times 32$
  • $2 \times 4 \times 64$
  • $2 \times 8 \times 32$
  • $4 \times 8 \times 16$

$m_4=3$:

  • $1 \times 2 \times 4 \times 64$
  • $1 \times 2 \times 8 \times 32$
  • $1 \times 4 \times 8 \times 16$

It would be nice to find a generalised solution for any $p_i^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, but not sure whether this is easiliy attainable.

Related Question