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
    @Arturo yes, my mista$k$e. 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".