Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Mr. Popular has seven friends. He wants to count the number ways that he can invite a different subset of 3 of his friends for a dinner on 7 straight evenings s.t. each pair of friends are together for just 1 dinner.

I tried to break this problem into smaller ones. Here's what I have so far: I created a table to show one possible collection of his triples s.t. no 2 friends are paired more than once.

$$ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix} $$

It doesn't look like I can use the LaTeX command "\bordermatrix", so please bare with me as I explain what the matrix means. The columns should be labeled 1 through 7 (representing each evening). The rows I have labeled as $a, b, c, d, e, f, g$ (friends). A "$1$" just means they're selected. So the first night (first column), friends $a, b,$ and $c$ are having dinner with Mr. Popular.

So if I could figure out how many collections there are, then I could multiply that by $7!$, where 7! is the arrangements from 1 collection. I don't think I should try to figure out how many different collections there are by hand, but I'm stuck otherwise. So what I think the answer should be is

$$ (\text{number of collections}) \cdot 7! $$

share|improve this question
    
Reminds me of this math.stackexchange.com/q/185386/12952 –  Alexander Gruber Jan 15 '13 at 3:41
    
@AlexanderGruber: Thanks. I wasn't sure how to search for this though. –  AlanH Jan 15 '13 at 5:12
    
It's fine; I don't think it's a duplicate, it just reminded me of that problem. –  Alexander Gruber Jan 15 '13 at 5:16

2 Answers 2

up vote 4 down vote accepted

You are seeking the number of Steiner triple systems on 7 elements in which the vertices are labelled as guests, and the triangles are ordered as evenings.

Up to isomorphism, there is only 1 Steiner triple system of order 7. From this, we can generate $7!^2$ (not necessarily distinct) invitation schemes (by permuting the guests and permuting the order of the evenings). This Steiner triple system has an automorphism group of order 168, so there are $7!^2/168=30 \cdot 7!$ possible invitation schemes.

I generated the 30 inequivalent possible invitation schemes using GAP. Here's the output:

1: 123 145 167 246 257 347 356 
2: 123 145 167 247 256 346 357 
3: 123 146 157 245 267 347 356 
4: 123 146 157 247 256 345 367 
5: 123 147 156 245 267 346 357 
6: 123 147 156 246 257 345 367 
7: 124 135 167 236 257 347 456 
8: 124 135 167 237 256 346 457 
9: 124 136 157 235 267 347 456 
10: 124 136 157 237 256 345 467 
11: 124 137 156 235 267 346 457 
12: 124 137 156 236 257 345 467 
13: 125 134 167 236 247 357 456 
14: 125 134 167 237 246 356 457 
15: 125 136 147 234 267 357 456 
16: 125 136 147 237 246 345 567 
17: 125 137 146 234 267 356 457 
18: 125 137 146 236 247 345 567 
19: 126 134 157 235 247 367 456 
20: 126 134 157 237 245 356 467 
21: 126 135 147 234 257 367 456 
22: 126 135 147 237 245 346 567 
23: 126 137 145 234 257 356 467 
24: 126 137 145 235 247 346 567 
25: 127 134 156 235 246 367 457 
26: 127 134 156 236 245 357 467 
27: 127 135 146 234 256 367 457 
28: 127 135 146 236 245 347 567 
29: 127 136 145 234 256 357 467 
30: 127 136 145 235 246 347 567

The remaining invitation schemes can be generated from these by permuting the order of the evenings.

share|improve this answer
    
Could you solve this just using basic combinatorics? I understand the solution, but I'd prefer to stick to combinatoric methods as I'm still new to the subject. –  AlanH Jan 15 '13 at 4:02
    
I'm not sure how one would do this without knowing showing the STS(7) is unique up to isomorphism. It would be possible to "brute force" it on a computer without much trouble/combinatorial insight. –  Douglas S. Stones Jan 15 '13 at 4:07
    
Could you explain why you permute both the evenings and the triples of guests? –  AlanH Jan 16 '13 at 0:29
    
This is how the question was defined: the order of the evenings is important, as is which guests are invited on which days. –  Douglas S. Stones Jan 16 '13 at 4:22

To supplement to the answer by @DouglasSStones, "the" projective plane of order 7 (seven points and seven "lines" of three points each) is known as the Fano plane:

Fano plane image (author: gunther/public domain)

We can sketch an argument as to why this "block design" is unique up to isomorphism (maps preserving lines and incidence). Given seven points we ask for blocks ("lines") each containing three points, that any pair of points determines a line (there exists a unique block containing that pair), and that any two lines intersect in exactly one point.

It follows that two distinct blocks are either disjoint or share exactly one point. If we sum the count of points over all lines, we get three times the number of lines. But each point belongs to three lines, as removing that point from the lines incident to it partitions the remaining six points into three disjoint pairs. So three times the number of lines also counts each point three times, proving the number of lines equals the number of points: seven.

Since a given point $X$ belongs to just three lines, there are exactly four blocks that miss point $X$. For such a point $X$, fix three lines that each meet $X$ and two more points, say $\{X,A_1,A_2\}$, $\{X,B_1,B_2\}$, $\{X,C_1,C_2\}$. We need to prove the six points other than $X$ can be organized into four blocks in essentially just one way, i.e. up to a relabeling of points.

Each of those four blocks contains one point (not $X$) from each of those three lines. Swap subscripts of labels as necessary so that $\{A_1,B_1,C_1\}$ is one of them. As this latter block must meet each of the other final three blocks in exactly one point, they are forced: $\{A_1,B_2,C_2\}$, $\{A_2,B_1,C_2\}$, $\{A_2,B_2,C_1\}$.

This sketch also accounts for the automorphism group having order 168. We can map point $X$ to a point $Y$ in the Fano plane in seven ways. The three lines meeting $X$ can be mapped to the respective three lines meeting $Y$ in $6 = 3!$ ways. Finally if we pick one of the four lines not meeting $Y$ to be the image of $\{A_1,B_1,C_1\}$, the rest of the correspondence is forced. Hence one gets $7\cdot 6\cdot 4 = 168$ possible automorphisms.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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