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$
9
$\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 '17 at 13:52
  • $\begingroup$ @luimichael The order of the factors matters (to the OP). $\endgroup$ – TravisJ Jul 13 '17 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$

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.