Suppose that we are given $n$ groups of $m$ people. We want to rearrange these $nm$ people into the same format of $n$ groups of $m$ with that the catch that any two people who were originally in a group together cannot be rearranged in the same group. How many ways can we rearrange the groups? It appears that this question is related to derangements but quite a bit more generalized.

A possibly related problem is the maximum number of times these rearrangements can happen before two previously encountered partners must meet again.

I am not sure if there is an elementary solution to these problems. It would appear that the first problem at least should be quite common in combinatorics and so I wonder if it is the special case of a famous problem.

  • $\begingroup$ "...with the catch that any two people who were originally in a group together can be rearranged in the same group." This does not seem to match the title. Did you mean that no two people who were in the same group of $m$ people cannot be in the same group of $m$ after the rearrangement? $\endgroup$ – Arturo Magidin Aug 22 '11 at 2:13
  • $\begingroup$ @Arturo yes, my mistake. They cannot be in the same group. I've edited the question. $\endgroup$ – EuYu Aug 22 '11 at 2:14

Problems of this sort have been of interest for a long time. Perhaps the earliest was Kirkman's schoolgirl problem from 1850: "Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast."

The general problem, given $mn$ people, how many days can you group them into $n$ groups of $m$ so that no two people are in the same group more than once, is not easy and not completely solved. One search term that may get you somewhere is "combinatorial designs".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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