4
$\begingroup$

The question I initially thought of that prompted this was "How many distinct integer-sided cuboids are there with a volume of $60^3$?".

A small example to clarify: There are $3$ integer-sided cuboids with a volume of $8$, namely $8\times 1\times 1$, $4\times 2\times 1$, $2\times 2\times 2$.

I realised that since the prime-factorisation of $60^3$ is

$60^3=(2^2\times 3\times 5)^3=2^6\times 3^3\times 5^3$

Then the problem is equivalent to "How many ways can we distribute $6$ identical objects (i.e. the $2$s), and $3$ identical objects of a different kind (i.e. the $3$s), and $3$ identical objects of a different kind again (i.e. the $5$s) into $3$ identical groups?"

For example, $60^3=(2^4\times 3)\times (2\times 5^2)\times (2\times 3^2\times 5)$ would be one possible cuboid.

Note that any of the $3$ identical groups are allowed to be empty (this would mean a side length of $1$ in the cuboid).

To put the problem another way, how many ways can we distribute the letters of the word "AAAAAABBBCCC" into $3$ identical groups?

I have actually come up with a solution, $475$, by a sort of recursive method that I devised. I have copied my solution below. It feels very long and involved, so I would like to know if there a quicker way that relies on more standard recursively-defined functions, and is more easily generalisable. I am aware that related problems can be solved using Sterling numbers of the second kind, for example, or Bell numbers. But I have not been able to find any example of a problem like this, where the objects are a mixture of identical and distinct (what should I call this? Categorised?) and the groups are identical.

Feel free NOT to read on, but here is my long-winded solution:

Firstly, how many ways are there to distribute the 6 2s across the 3 groups? We can enumerate them:
0,0,6
0,1,5
0,2,4
0,3,3
1,1,4
1,2,3
2,2,2
Total: 7 ways

Ok now how many ways are there to distribute the 3 3s?
0,0,3
0,1,2
1,1,1
Total: 3 ways

Does this mean that there are 7 x 3 = 21 ways to distribute the 6 2s and the 3 3s? No! Since, it matters which of the 7 distributions of 2s we combine with which of the 3 distributions of 3s.

The important feature of a distribution, for seeing how it combines with a set of possible distributions “overlaid” onto it, is which groups (if any) have been made distinguishable from each other by the first distribution. There are 3 possible patterns:

All groups indistinguishable (call this A)
Two groups indistinguishable, the other distinguishable (call this B)
All groups distinguishable (call this C)

Going back to the 7 possible distributions of 2s and labelling them A, B or C accordingly:
0,0,6 B
0,1,5 C
0,2,4 C
0,3,3 B
1,1,4 B
1,2,3 C
2,2,2 A

So overall we have 1 A, 3 Bs and 3 Cs. At this point we can create our own “algebra” and use an algebraic-style shorthand (bearing in mind that A, B and C don’t represent numbers but patterns):
A + 3B + 3C

And for the 3 3s, we have:
0,0,3 B
0,1,2 C
1,1,1 A
Making A + B + C

Similarly, for the 3 5s we would have A + B + C

Now, how do these all combine? First let’s consider overlaying the 3 possible distributions of 3s onto the 7 possible distributions of 2s. And let’s suppose that we overlay a C-distribution (all 3 containers distinguishable) onto another C-distribution. How many combined distributions does that give us? It gives us 3 x 2 x 1 = 6. And what are the patterns (A, B or C) for these distributions? They are all Cs. And so, in our homemade algebra, we can introduce a * symbol for overlaying distributions of given patterns, and say:
C * C = 6C

So, how many distributions do we get, and with what patterns, by overlaying the 1 C-distribution of 3s onto the 3 C-distributions of 2s?
C * 3C = 18C

Now we can go through a similar process for combining B with C, B with B etc.

Note that, since an A-pattern is equivalent to the blank slate we started with, “multiplying” by A has no effect:
A * C = C
A * B = B
A * A = A

Note also that this form of “multiplication” is commutative, i.e. B * C = C * B etc, since we’ll get the same number of combined distributions whichever distribution we “put there first”.

Some thought tells us that B * C = 3C, since if we begin with a C, there are 3 possible places to overlay the distinguishable container of the B.

And by similar sorts of reasoning, B * B = B + C

Now combining everything together,

(A + 3B + 3C) * (A + B + C) = (A * A) + (A * B) + (A * C) + 3(B * A) + 3(B * B) + 3(B * C) + 3(C * A) + 3(C * B) + 3(C * C)

(Interesting to note that the distributive rule for “multiplication” in this sense is valid, since we are combining every possible distribution of 2s with every possible distribution of 3s)

= A + B + C + 3B + 3(B + C) + 9C + 3C + 9C + 18C
= A + 7B + 43C

All that is left to do now is overlay the possible distributions of 5s: (A + 7B + 43C) * (A + B + C)
= A + B + C + 7B + 43C + 7(B * B) + 50(B * C) + 43(C * C)
= A + B + C + 7B + 43C + 7B + 7C + 150C + 258C
= A + 15B + 459C

Making a total of 475 distinct cuboids.

$\endgroup$
1
+50
$\begingroup$

This problem can be solved by an application of Burnside's lemma.

Let $X = \{(x,y,z) \in \mathbb N^3 : xyz = 60^3\}$ be the set of all ways to specify the cuboid where the order of the sides does matter. The group $G = S_3$ acts on the elements of $X$ by permuting the ordered triple $(x,y,z)$. We are looking for the number of orbits $|X/G|$.

To do this, we compute the number of elements of $X$ fixed by each element of $G$ and average them:

  • $X^e$, the set of elements fixed by the identity element $e$, is just $X$. We have $|X| = |X^e| = \binom82 \binom52 \binom52$ by applying stars and bars to each of the prime factors.
  • $X^{(1\;2)}$, the set of elements fixed by the transposition $(1\;2)$. There are $4$ possibilities for the powers of $2$: $(2^3,2^3,1)$, $(2^2,2^2,2^2)$, $(2^1,2^1,2^4)$, and $(1,1,2^6)$. There are $2$ possibilities for the powers of $3$ and $5$. So $|X^{(1\;2)}| = 16$.
  • Similarly, $|X^{(1\;3)}|=|X^{(2\;3)}|=16$.
  • $X^{(1\;2\;3)}$, the set of elements fixed by the $3$-cycle $(1\;2\;3)$. This means $x=y=z$ in the triple $(x,y,z)$, so there is only one such element: $(60,60,60)$. So $|X^{(1\;2\;3)}| = 1$.
  • Similarly, $|X^{(1\;3\;2)}| = 1$.

So by Burnside's lemma, $$ |X/G| = \frac{2800 + 16 + 16 + 16 + 1 + 1}{6} = 475. $$

This approach is easy to generalize to counting factorizations of $xyz=n$. It generalizes to factorization with more factors as well, but then the group action is more complicated, so there are more cases to deal with, and they're individually harder to count.

$\endgroup$
  • $\begingroup$ Thank you, that is certainly much more direct for the 3-container case! It is beyond my current theoretical knowledge but I will research Burnside's lemma. $\endgroup$ – alcana Aug 27 '18 at 19:26
  • $\begingroup$ Intuitively, it is just an inclusion-exclusion type correction to the naive argument "there's $2800$ ordered triples, so we divide by $3!$ to get unordered ones" which fails due to symmetry. The group theory is there as a shortcut to find the inclusion-exclusion coefficients. $\endgroup$ – Misha Lavrov Aug 27 '18 at 19:44
  • $\begingroup$ That makes sense. I can see now a relatively direct but still intuitive way to solve my specific problem: of the 2800 ordered triples there is 1 with all three elements equal, and (I can show fairly easily) 15 x 3 = 45 with exactly 2 elements equal. Therefore there are 2800 - 45 - 1 = 2754 with no two elements equal. This latter subset, for the unordered triples, is overcounted by a factor of 6; the 45 triples with exactly 2 elements equal are overcounted by a factor of 3; and the 1 triple with all 3 elements equal is not overcounted at all. So we have (2754 / 6) + (45 / 3) + 1 = 475. $\endgroup$ – alcana Aug 27 '18 at 21:29
  • $\begingroup$ in the 3-factor case, you have used Stars and Bars for the whole set X but a more ad-hoc counting method for the sets of elements fixed by the different permutations. Do you know whether a Stars-and-Bars-type method can be modified to count distributions of objects with certain symmetry properties? For example: "how many ways are there to distribute $n$ identical objects among $5$ distinct containers such that containers $1$ and $2$ have the same number of objects, and containers $3$ and $4$ also have the same number of objects?" $\endgroup$ – alcana Aug 31 '18 at 16:11
  • $\begingroup$ @alcana We can replace $k$ containers that all have the same number of objects, by a single container that holds a multiple of $k$ objects. Then this is a problem that can be done using generating functions, with $\frac{1}{1-x^k}$ being the generating function for such a combined container. (E.g., in your example, we'd take the coefficient of $x^n$ in $\frac{1}{(1-x^2)^2(1-x)}$.) There's no nice general way to turn that into a formula, though special cases can be nice. $\endgroup$ – Misha Lavrov Aug 31 '18 at 17:53
2
$\begingroup$

Using the notation from the following MSE link I we start with the source multiset

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \prod_{k=1}^l A_k^{\tau_k}$$

where we have $l$ different values and their multiplicities are the $\tau_k.$ We ask about the distinct partitions of this multiset into $N$ factors including one as a factor, where distinct refers to permutations of the $N$ factors by the symmetric group. The case where one is not admitted as a factor was discussed at the following MSE link II.

If we have a CAS like Maple, $N$ is reasonable and we seek fairly instant computation of these values then we may just use the cycle index $Z(S_N)$ of the symmetric group which implements the unlabeled operator $\textsc{MSET}_{=N}.$ This yields the formula

$$\left[\prod_{k=1}^l A_k^{\tau_k}\right] Z\left(S_N; \prod_{k=1}^l \frac{1}{1-A_k}\right).$$

Here we use the recurrence by Lovasz for the cycle index $Z(S_N)$, which is

$$Z(S_N) = \frac{1}{N} \sum_{l=1}^N a_l Z(S_{N-l}) \quad\text{where}\quad Z(S_0) = 1.$$

Maple can extract these coefficients by asking for the coefficient of the corresponding Taylor series. We get the following transcript:

> FACTORS(60^3, 3);
                                475

> FACTORS(60^4, 3);
                               1710

> FACTORS(120, 4); 
                                20

> FACTORS(512, 4);
                                18

> FACTORS(729, 5);
                                10

> FACTORS(2^4*3^3*5^2, 6);
                                573

> seq(FACTORS(n,4), n=1..60);
1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2,

    1, 7, 2, 2, 3, 4, 1, 5, 1, 6, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1,

    4, 4, 2, 1, 11, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11

The sequence is OEIS A218320 and looks to have the right values. The Maple code here is quite simple.

with(combinat);
with(numtheory);

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*
           add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;


MSETS :=
proc(src, N)
local msetgf, cind, gf, cf;

    msetgf := mul(1/(1-A[q]), q=1..nops(src));
    cind := pet_cycleind_symm(N);

    gf := pet_varinto_cind(msetgf, cind);

    for cf to nops(src) do
        gf := coeftayl(gf, A[cf] = 0, src[cf]);
    od;

    gf;
end;

FACTORS :=
proc(n, N)
local mults;

    mults := map(el -> el[2], op(2, ifactors(n)));
    MSETS(mults, N);
end;

Remark. An observation. While Burnside and Polya certainly represent an enrichment here we must also take care to include the basics, which in this case consists of a simple recurrence that is given at the OEIS entry and which computes the desired values almost instantly. With the variables renamed to indicate semantics we have an algorithm whose correctness follows by inspection and which is shown below.

FACTREC :=
proc(val, numel, maxfact)
option remember;
local divs;

    if numel = 1 then
        return `if`(val <= maxfact, 1, 0);
    fi;

    divs := select(d -> d <= maxfact, divisors(val));
    add(FACTREC(val/d, numel-1, d), d in divs);
end;

FACTORSX := (n, N) -> FACTREC(n, N, n);
$\endgroup$
  • $\begingroup$ Thanks, this is very interesting! I'm not sure what you mean by the unlabelled operator MSET? I'm also struggling with the notation for the cyclic index - what is the meaning of the part after the semicolon? Is this a standard notation? I'm a beginner when it comes to group theory so it may be simply that I need to do more research... $\endgroup$ – alcana Aug 28 '18 at 14:40
  • $\begingroup$ The labeled and unlabeled set operators are written here in the notation from Analytic Combinatorics. There is Wikipedia on cycle indices. The mechanics of substituting into a cycle index (term after the semicolon) are at Wikipedia on the Polya Enumeration Theorem. $\endgroup$ – Marko Riedel Aug 28 '18 at 17:34
  • $\begingroup$ Thanks, this gives me some good starting points for further research. My aim is indeed to have an algorithmic solution based on recurrence relations, which you have provided, but I'd also like to understand why it works and for this will need to do some study of the topic. $\endgroup$ – alcana Aug 31 '18 at 18:07

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.