4
$\begingroup$

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

  • 0
    Hmm so dividing by (n/3)! my formula does seem to give the correct answer and I see why. Thanks :)2011-08-21

2 Answers 2

7

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

  • 0
    Great answer thanks :)2011-08-21
9

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.

  • 0
    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.2019-04-30