Number of factorizations of distinct factors

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.


Let me present a proof of the first special case (product of $k$ distinct primes) by @martin, which is a nice result that can be proved by Polya enumeration.

I will assume the reader has consulted and understood the material at the following MSE link which I will not duplicate here.

Using the notation from the link with $q$ being the number of factors in the partition we obtain by the Polya Enumeration Theorem the following formula:

$$G(k, q) = \left[\prod_p X_p\right] Z(P_q)\left(\prod_p (1+X_p)\right) \quad\text{where}\quad n=\prod_p p^v$$

with all $v=1$ and we have $k$ distinct primes in the product. Here the square bracket denotes coefficient extraction of formal power series and $Z(P_q)$ is the cycle index of the set operator $\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}_{=q}$ which was also used in the linked-to computation from above.

Now recall the OGF of the set operator which is $$Z(P_q) = [z^q] \exp\left(a_1 z - a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} - a_4 \frac{z^4}{4} +\cdots \right).$$

Observe that on substituting into the cycle index we let $$a_m = \prod_p (1+X_p^m).$$

But the degree of $X_p$ in the coefficient being extracted is one, which means that from the $a_m$ with $m\ge 2$ only the constant term contributes, which is one.

This gives the formula

$$G(k, q) = \left[\prod_p X_p\right] [z^q] \exp\left(z\prod_p (1+X_p) - \frac{z^2}{2} + \frac{z^3}{3} - \frac{z^4}{4} + \cdots\right)$$

which is $$G(k, q) = \left[\prod_p X_p\right] [z^q] \exp\left(z\left(-1+\prod_p (1+X_p)\right) + \log(1+z)\right) \\ = \left[\prod_p X_p\right] [z^q] (1+z) \exp\left(z\left(-1+\prod_p (1+X_p)\right)\right) \\ = \left[\prod_p X_p\right] \left(\frac{1}{q!} \left(-1+\prod_p (1+X_p)\right)^q + \frac{1}{(q-1)!} \left(-1+\prod_p (1+X_p)\right)^{q-1}\right).$$

Doing coefficient extraction on the first term we find $$\left[\prod_p X_p\right] \frac{1}{q!} \sum_{m=0}^q {q\choose m} (-1)^{q-m} \prod_p (1+X_p)^m.$$

Only the terms with $X_p$ raised to the power one contribute and we get for the first term $$\frac{1}{q!} \sum_{m=0}^q {q\choose m} (-1)^{q-m} m^k = {k\brace q}.$$

The second term is similar and therefore the answer to the special case of a product of $k$ primes is

$${k\brace q} + {k\brace q-1}.$$

Now that we have this we can easily give a combinatorial interpretation. The first term represents the case where we divide the $k$ prime factors into $q$ non-empty sets which correspond to the $q$ distinct factors of the multiplicative partition with none of the factors being one. (With the $k$ primes being distinct the products of the elements of these sets are necessarily distinct.) This almost completes the count except we have not accounted for partitions containing one as a factor. That leaves $q-1$ distinct factors to choose according to the same procedure as before, done.

Remark. Using the OGF of the Stirling numbers of the second kind which is $${n\brace k} = [z^n] \prod_{r=1}^k \frac{z}{1-rz}$$

we get the generating function $$\prod_{r=1}^q \frac{z}{1-rz}+ \prod_{r=1}^{q-1} \frac{z}{1-rz} = \left(1+\frac{z}{1-qz}\right) \prod_{r=1}^{q-1} \frac{z}{1-rz} \\ = \frac{1-(q-1)z}{1-qz} \prod_{r=1}^{q-1} \frac{z}{1-rz}.$$

Tags:

Combinatorics

Number Theory

Recent Posts