17
$\begingroup$

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$
$\endgroup$
  • 2
    $\begingroup$ If you are at all interested in an easier problem you can visit Sloane's OEIS A251683 and A074206. These sequences count the number of ordered facorizations of n. There are some references that might be beneficial. $\endgroup$ – Geoffrey Critzer May 17 '15 at 21:50
  • 3
    $\begingroup$ If all $e_i = 1$, this is the number of ways to partition an $m$ set into $k$ parts, i.e., Stirling numbers of the second kind. $\endgroup$ – vonbrand Aug 18 '15 at 17:00
  • 2
    $\begingroup$ The number of factorizations of distinct factors that you are interested, is it different from the number $f(n, k)$ of ordered $k$-factorizations of $n$ found by MacMahon, i.e. $$f(n,m) = \sum_{i=0}^{m-1}{(-1)^i \binom{m}{i}\prod_{j=1}^{k}{\binom{e_j+m-i-1}{e_j}}}$$ $\endgroup$ – Ali Aug 24 '15 at 20:02
  • 1
    $\begingroup$ This MSE link may prove useful as regards the theoretical aspects of this question. $\endgroup$ – Marko Riedel Dec 23 '15 at 21:17
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Let me observe that the second special case counts partitions into distinct parts. We immediately obtain the expression $$[z^k][y^q] \prod_{m=0}^k (1+yz^m)$$ which is OEIS A00009. $\endgroup$ – Marko Riedel Jan 8 '16 at 22:28
  • $\begingroup$ @MarkoRiedel brilliant again - thanks :) ... I wonder if the secret to the more complex cases is bound up in this somewhere?... $\endgroup$ – martin Jan 8 '16 at 23:01
  • 1
    $\begingroup$ It gets complicated quickly as seen e.g. at this MSE link. $\endgroup$ – Marko Riedel Jan 8 '16 at 23:10
3
+100
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ this looks great! Thanks for posting the answer - there is loads to learn from it - fantastic :) - Will no doubt award you the bounty , unless in the very unlikely event that someone comes up with a solution to the general case (but I for one can make neither head nor tail of the the sequences that arise when $e^i, i\neq 1$). $\endgroup$ – martin Jan 8 '16 at 22:10
  • 1
    $\begingroup$ Thank you for the kind remark. I enjoyed the Eureka effect when I saw the Stirling numbers. $\endgroup$ – Marko Riedel Jan 8 '16 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.