Number of equivalence relations splitting set into sets with exactly 3 elements

Another way of counting that more easily leads to a closed formula for the product is like this:

First choose a class of $3$; there are $\binom{3k}3$ ways of doing this. Then choose another class of $3$ from the remaining $3k-3$ people; there are $\binom{3k-3}3$ ways of doing this, and so on. The product of all these binomial coefficients is the multinomial coefficient

$$\binom{3k}{3,\dotsc,3}=\frac{(3k)!}{3!^k}\;,$$

where there are $k$ threes on the left-hand side. Now we have $k$ equivalence classes, but we could have chosen these in $k!$ different orders to get the same equivalence relation, so the number of different equivalence relations is

$$\frac{(3k)!}{3!^kk!}\;,$$

which is the same as what André's approach yields when you form the product and insert the factors in $(3k)!$ that are missing in the numerator.


We have $3k$ people. Unimaginatively, let us name them $1$, $2$, $3$, and so on. Line them up in the order $1$, $2$, $3$, and so on. (This is very important for the analysis.)

We want to divide the people $1$ to $3k$ into equivalence classes (teams) of $3$ each.

Who shall be on $1$'s team? They can be chosen in $\binom{3k-1}{2}$ ways.

Look at the first person in the lineup who has not yet been chosen. Who shall be on her team? They can be chosen in $\binom{3k-4}{2}$ ways. Continue.

The number of ways to to divide the people into teams of $3$ each is $$\binom{3k-1}{2}\binom{3k-4}{2}\binom{3k-7}{2}\dots\binom{5}{2}\binom{2}{2}.$$

Comment: There are other ways to do the analysis, which yield different-looking but equivalent expressions. In particular, one can get expressions that look very like the one of the OP. For example, we can multiply and divide the term $\binom{3k-3i-1}{2}$ in our product by $3k-3i$.

Simplification The expression as a product can be simplified. The product is $$(3k-1)(3k-2)(3k-4)(3k-5)(3k-7)(3k-8)\cdots (5)(4)(2)(1)$$ divided by a power of $2$. Multiply and divide by the "missing" numbers $3k$, $3k-3$, $3k-6$, and so on down to $3$. We get a simple "product-free" expression (the quotation marks are because after all the factorial is a product that happens to have been given a compact name.)