How many combinations of groups are there where no member of a group has been with another member before

Question

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!

Answer 1

I think there are $5$ ways to do it, not $3$.

Identify each student with one of the $16$ points of the affine plane over the field with $4$ elements. To divide the students into $4$ groups, we can group them according to a pencil of $4$ parallel lines. Then the question becomes, "How many parallel directions are there in the plane?"

Of course, this is just the number of lines through the origin. We can join the origin to any of the other $15$ points, but each line is counted $3$ times, once for every point on it other than the origin, so there are $5$ lines.

In general, this is a problem in combinatorial designs, and there are a lot of open questions, I believe.

EDIT

Here is a python script that computes the answer. I don't know how to draw a comprehensible picture of the plane over $\mathbb{F}_4$. I think of a $4\times4$ array of dots for the points. The problem is that there are $20$ lines, and I don't see how to draw them without making a mess.

Here is my script:

plus = { }

for x in range(4):
    plus[x,0] = plus[0,x] = x
for x in range(4):
    plus[x,x] = 0
plus[1,2]=plus[2,1] =3
plus[1,3]=plus[3,1] = 2
plus[2,3]=plus[3,2] = 1

times = { }
for x in range(4):
    times[x,0]=times[0,x] = 0
    times[x,1]=times[1,x] = x
    times[2,2] = 3
    times[3,3] = 2
    times[2,3]=times[3,2] = 1
    
points = set(range(1,16))  # points that have to be with 0

def add(x,y):
    x0, x1 = divmod(x,4)
    y0, y1 = divmod(y,4)
    a = plus[x0, y0]
    b = plus[x1,y1]
    return 4*a+b
    
def mult(k, x):
    x0, x1 = divmod(x,4)
    a = times[k, x0]
    b = times[k, x1]
    return 4*a+b

def plane(pt):
    answer = 4*[None ]
    answer[0] = sorted([0, pt, mult(2,pt), mult(3,pt)])
    used = set(answer[0])
    for n in range(1,4):
        for x in range(16):
            if x not in used: break
        answer[n] = sorted([add(x, y) for y in answer[0]])
        used |= set(answer[n])
    return answer
    
planes = []    
while points:
    x = points.pop()
    p = plane(x)
    planes.append(p)
    for pt in p[0]:
        points.discard(pt)
        
for plane in planes:
    for line in plane:
        print(line)
    print()
    
for x in range(16):
    for y in range(16):
        if x==y: continue
        found = False
        for plane in planes:
            if found:
                break
            for line in plane:
                if x in line and y in line:
                    found = True
                    break
else: # not found
    print(f'Did not find {x}, {y}')
      

This produced the output

[0, 1, 2, 3]
[4, 5, 6, 7]
[8, 9, 10, 11]
[12, 13, 14, 15]

[0, 4, 8, 12]
[1, 5, 9, 13]
[2, 6, 10, 14]
[3, 7, 11, 15]

[0, 5, 10, 15]
[1, 4, 11, 14]
[2, 7, 8, 13]
[3, 6, 9, 12]

[0, 6, 11, 13]
[1, 7, 10, 12]
[2, 4, 9, 15]
[3, 5, 8, 14]

[0, 7, 9, 14]
[1, 6, 8, 15]
[2, 5, 11, 12]
[3, 4, 10, 13]  

Did not find 15, 15

Where the last line is a spurious error message due to sloppy programming.

EDIT

In response to user's comments.

I thought of a way to present this that might make it a little clearer. In each group, the $16$ numbers represent the points of the plane, and points of the same color lie on the same line. In the first two groupings, this looks pretty dull; the lines are rows or columns. In the last three groupings, the lines don't look like what we normally think of as lines, but they satisfy the same kind of linear equations as the lines you're used to.

This isn't the place to try to explain that. You can search the Web for "finite geometries", but you'll have to learn a little bit about finite fields before it makes sense.