4
$\begingroup$

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.

  • 0
    "...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?2011-08-22
  • 0
    @Arturo yes, my mistake. They **cannot** be in the same group. I've edited the question.2011-08-22

1 Answers 1

7

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