Welcome to MindCipher, a social repository of the world's greatest brain teasers, logic puzzles and mental challenges.

## Partitioning a set 6

In how many ways can a set of r objects be partitioned into subsets of k objects such that:

• all subsets are mutually exclusive

• each of k-object subset appears in exactly one of the partitions [Partition wiki]

given that k divides r.

Possible Applications: Baranyai's Theorem

rCk*(k/r) [r choose k * (k/r)]

EDIT: Thanks Stephen for pointing out a flaw in my original question after which I have modified the question

Let the indexed set {1,2,3....r} represent the r objects. Note that the size of each partition is r/k. By definition, a partition's subsets are mutually exclusive. So if we simply place all subsets made by keeping one element constant in the subset in separate partitions, we have the number of partitions possible. The problem then reduces to finding the number of subsets of size k made from r elements in which one element has been fixed. This can be done in (r-1)C(k-1) which is equivalent to the answer.

Illustration Let's try with r = 8 and k = 2. The number of partitions is:

• {1,2} {3.4} {5,6} {7,8}
• {1.3} {2,8} {4,6} {5,7}
• {1,4} {2,5} {3,8} {4,5}
• {1,5} {2,7} {3,6} {4,8}
• {1,6} {2,3} {4,7} {5,8}
• {1,7} {2,6} {3,8} {4,5}
• {1,8} {2,4} {3,5} {4,7}

As can be seen there are 7 partitions and no two partitions have the same subsets.

Aakash

Could you explain why, in your illustration, the answer is 3? Doesn't the question say that all the subsets have to be mutually exclusive (i.e. disjoint)?

Then, with r=4 and k=2, you have only the sets {1,2} and {3,4}. Introducing any of the other sets you mentioned will violate the "disjointness among subsets" requirement. Am I misunderstanding the question?

Salutarius

The solution {1, 2} and {3,4} is one way to generate a set of disjoint sets. The question asks in how many ways. Similarly, {1,3}, {2,4} and {1,4},{2,3} also satisfy the conditions of being mutually exclusive. So we have three ways in which we could make partitions such that the said conditions are satisfied namely, 1. {1,2} {3,4} 2. {1,3} {2,4} 3. {1,4} {2,3}

Please let me know if the wording of the question is confusing because this was the problem I wanted to share i.e. the number of ways in which such groups are mutually exclusive sets could be made.

Aakash

Ahh, got it! I think the question is clear, but like this one helps a lot. Thanks, cool question!

Stephen

I don't think the answer you've given is correct. Suppose r = 6, k = 2. Then (6c2) * 2 / 6 = 5. But you can have: { {1,2}{3,4}{5,6} } { {1,2}{3,5}{4,6} } { {1,2}{3,6}{4,5} } { {1,3}{2,4}{5,6} } { {1,3}{2,5}{4,6} } { {1,3}{2,6}{4,5} } which isn't exhaustive but is already more than 5.

Here's another solution. There are r! permutations of the original set. Convert a permutation to a partition by treating the subsets as the first k elements, the next k elements, etc. But then there are (r/k)! * (k!)^(r/k) permutations that generate each partition -- each of the r/k subsets can be ordered in k! ways, and then the r/k subsets can be ordered in (r/k)! ways. So the number of partitions is r! / [ (r/k)! * (k!)^(r/k) ]

In the example of r = 6, k = 2, this revised formula gives 6! / (3! * (2!)^3) = 15.

Salutarius

Hey Stephen,

`````` Thanks for pointing out a flaw which was obvious and I totally overlooked. I have re-worded the question which has added additional constraints to the problem and thus reduced your solution to mine.
And again, thanks for pointing out the flaw.
``````

it'sSarah

Hey, I'm afraid the new solution isn't right either. Let's take a look at your own example: you divided those numbers like: {1,2}, {3,4}, {5,6}, {7,8} at the first line. What I say is, imagine we have {1,2} and {3,4}. this way, we can have these combinations for other sets: (1.) {5.6}, {7.8} (2.) {5.7},{6.8} (3.) {5.8},{6.7}. You didn't put all the examples there. it's true for all other lines... and other combinations! Now, we know that k divides r. let q = r/k to make it simple. We want to put r distinct objects into q indistinct groups, k objects in each. to make our work easier, we also take the groups distinct. so we take k objects for group#1, k for #2, and so on, which will be: C( qk , k ) * C( (q-1)k , k ) * ... * C ( k , k ) Since the groups are actually indistinct, we should now divide this by q! cause we have counted each combination q! times. well that's the way I think the problem should be solved

leilei3915

2018529 leilei3915

# polo ralph lauren outlet

Check out other puzzles:

Like this? You might also like:
Time To Fuse
The Price Is Right
All the King's Wine
Submitted by
Salutarius
over 7 years ago
Likes
Difficulty 8.7 ?

Tags