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