How many combinations of groups are there where no member of a group has been with another member before? I found this hard to word in the title, so let me give an example.
I have 16 students, and I want to split them up into 4 groups of 4. However, I want to make sure that every time I have a new combination of groups, that a student has never been with any of their new groupmates before.
I found info on how to separate objects into groups, but not in only unique ways as I've described above.
I think I figured this out the rote way, by assigning each student a number and then finding the unique combinations, and got 3. But I'd like to know the math behind it, and how it could be applied to other configurations (20 students w/ 4 groups of 5?).
Thanks for any help you can give!
 A: If you have $n^2$ students being divided into $n$ groups of size $n$, then a solution which works for $d$ ways is equivalent to a set of $d+2$ mutually orthogonal $n\times n$ Latin squares (MOLS). Some partial results:

*

*For any $n$, you can succeed for at most $n+1$ days.


*When $n$ is a prime power, it is possible to achieve the limit of $n+1$ days.


*For $n=6$, three days is the max, as there are no two orthogonal $6\times 6$ Latin squares.


*For $n=10$, four days is possible, but it is an open problem to determine if five days is possible (see Find three $10\times10$ orthogonal Latin squares.).


*There is more data on the maximum known number of MOLS here: http://www.math.stonybrook.edu/~tony/whatsnew/column/latin-squaresII-0901/latinII3.html
In general, if you have $nm$ students to be divided into $n$ groups of size $m$, this is known as the Social Golfer problem. Again, this is a hard open problem in most cases. See
http://www.mathpuzzle.com/MAA/54-Golf%20Tournaments/mathgames_08_14_07.html
for some partial results, and you can find more by searching "Social Golfer problem."
A: There are at least 4 ways to do it for 4 groups of 4. I'm not sure if it's possible to do more, or about how to extend to larger groups.

