# Combinatorics: Steiner Triple System

1. Apr 26, 2015

### Robben

1. The problem statement, all variables and given/known data

A Steiner Triple System, denoted by $STS(v),$ is a pair $(S,T)$ consisting of a set $S$ with $v$ elements, and a set $T$ consisting of triples of $S$ such that every pair of elements of $S$ appear together in a unique triple of $T$.

2. Relevant equations

None

3. The attempt at a solution

My book goes on to say that the number of triples of a $STS(n)$ disjoint from a given triple is $(n-3)(n-7)/6$ but I am not sure how they got that result?

I know that there are $n(n-1)/6$ triples altogether where each point of a triple lies in $(n-1)/2$ triples but I am not sure how they got that $(n-3)(n-7)/6.$

Last edited: Apr 26, 2015
2. Apr 26, 2015

### certainly

Try subtracting the number of non-disjoint sets from the total.

3. Apr 26, 2015

### Robben

Can you elaborate please? What does it mean when a STS is disjoint from a given triple?

4. Apr 26, 2015

### certainly

say the first triple is (a,b,c), for a triple to be disjoint to this triple it must not contain any of the elements a, b, c i.e. the union of 2 disjoint triples will be the null set.
[EDIT:- so you are to find all triples in the STS that do not contain any of the elements a,b or c.]

5. Apr 26, 2015

### Robben

Oh, I see thank you.

6. Apr 26, 2015

### certainly

Were you able to prove the desired result ?

7. Apr 26, 2015

### Robben

Using your suggestion I got that $n(n−1)/6−3(n−1)/2$ but I am still not sure how they got $(n−3)(n−7)/6?$

8. Apr 26, 2015

### certainly

Let be a set of elements together with a set of 3-subset (triples) of such that every 2-subset of occurs in exactly one triple of [PLAIN]http://mathworld.wolfram.com/images/equations/SteinerTripleSystem/Inline6.gif. [Broken] Then http://mathworld.wolfram.com/images/equations/SteinerTripleSystem/Inline7.gif is called a Steiner triple system.
Let's use this definition henceforth. It is not only much simpler, but also a lot more clear.
You are forgetting to subtract the original set and you are also forgetting that more than one 2-subsets were covered in the original triple. And since every 2-subset has a unique triple you need to take those into account.

Last edited by a moderator: May 7, 2017