4
$\begingroup$

Specifically, I am thinking of a cuboid with a given volume ($28\,000$) that has sides of integer length. For example, $20 \cdot 20 \cdot 70 = 28\,000$, but so do $10 \cdot 40 \cdot 70$ and $1 \cdot 1 \cdot 28\,000$. I am interested in finding how many possible integer combinations of side lengths there are that produce this volume.

Its prime factorisation is $2^5 \cdot 5^3 \cdot 7$, so I think that the answer may have something to do with permutations of those.

The order of the three groups does matter because there is a distinction between it being height, width or length.

$\endgroup$

2 Answers 2

11
$\begingroup$

Suppose that $n=p_{1}^{k_1}\cdot p_{2}^{k_2}...p_{m}^{k_m}$. Then what we must do is decide is how to split up each prime power as the sum of $3$ non-negative integers. The way to do that is stars-and-bars and the formula becomes $\binom{k_{i}+2}{2}$. (This gives us the number of ways of splitting up the factor $p_{i}^{k_{i}}$.) All together, this gives us $\prod_{i=1}^{m}\binom{k_{i}+2}{2}$ ways to write $n$ as a product of exactly $3$ of its factors.

To be more explicit in why this works, think of writing your $3$ bins, $\ell, w, h$. $\ell$ will contain $p_{i}^{x_{1}}$, $w$ will contain $p_{i}^{x_2}$ and $h$ will contain $p_{i}^{x_{3}}$. In order for $\ell w h=n$ you need that $p_{i}^{x_1}p_{i}^{x_2}p_{i}^{x_3}=p_{i}^{k_{i}}$ so it must be that $x_1+x_2+x_3=k_i$ and each $x_{1},x_{2},x_{3}\geq 0$. Then, do this for each prime.

$\endgroup$
2
  • $\begingroup$ There could be some repetitions: $$n=2^3 5^3$$ can be written as $$(2^15^1)(2^25^2(2^05^0)$$ or $$(2^05^0)(2^25^2)(2^15^1)$$. These two factorizations are essentially the same but according to your method they are considered different. $\endgroup$
    – luimichael
    Jul 12, 2017 at 13:52
  • $\begingroup$ @luimichael The order of the factors matters (to the OP). $\endgroup$
    – TravisJ
    Jul 13, 2017 at 15:58
4
$\begingroup$

Using the formalism of the following MSE link and the Polya Enumeration Theorem it follows that for $n$ having factorization $$n = \prod_{p|n} p^v$$ applying PET we have almost by inspection that the desired count of factorizations into $k$ factors is given by the term $$H(n, k) = \left[\prod_p X_p^v\right] Z(E_k)\left(\prod_p \frac{1}{1-X_p}\right)$$ where the square bracket denotes coefficient extraction of formal power series and $Z(E_k) = a_1^k$ is the cycle index of the identity group containing the identity permutation. This becomes $$\left[\prod_p X_p^v\right] \left(\prod_p \frac{1}{1-X_p}\right)^k.$$ Doing the coefficient extraction we obtain $$\prod_p {v+k-1\choose k-1}$$ as observed by the first responder.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .