Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
    
Great answer thanks :) –  Jason Aug 21 '11 at 19:41
add comment

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.

share|improve this answer
1  
And you two :) I love seeing different ways Thanks :) –  Jason Aug 21 '11 at 19:41
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.