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

Hey as the title says I would like to find the number of equivalence relations splitting set into sets with exactly 3 elements

I have came up with the following formula and believe it is correct but I would like to see if it really is :)

for a set A where |A| = n and n=3k where k is a natural number (This is a given). My formula is:

$$\prod\limits_{k=0}^{(n/3)-1}{\binom{n-(3k)}{3(k+1)}}$$

And maybe there is a more efficient method of writing this :P

Thanks

-
This is too large. – André Nicolas Aug 21 '11 at 19:13
Please Elabarate – Jason Aug 21 '11 at 19:20
Your formula gives an answer of I think $20$ for $n=6$. If you list carefully the divisions into two groups of $3$, you will find there are $10$. The "overcounting factor" is given in @joriki's analysis. – André Nicolas Aug 21 '11 at 19:42
Hmm so dividing by (n/3)! my formula does seem to give the correct answer and I see why. Thanks :) – Jason Aug 21 '11 at 19:51

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

-
Great answer thanks :) – Jason Aug 21 '11 at 19:41

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.

-
And you two :) I love seeing different ways Thanks :) – Jason Aug 21 '11 at 19:41
@Jason: You are very right in liking to see different ideas at play. Too many people just want "the answer." Here is a variant. The people can be lined up in $(3k)!$ ways. For each such way, put together the first $3$, the next $3$, and so on. By what factor have we overcounted? Each division into teams occurs in $k!$ different orders. And for each such order, each "team" occurs in $3!$ different orders, for a total overcount factor of $k!(3!)^k$. – André Nicolas Aug 21 '11 at 21:17
What order is this in $k$? I see an exponential and factorial in the denominator, and factorial in the numerator, so I'm inclined to say 'smaller than $O(k)$', but that seems imprudent. – Trevor Alexander Dec 12 '13 at 9:59