Number of ways to distribute objects, some identical and others not, into identical groups

Question

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.

Answer 1

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.

Answer 2

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);