1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics: Steiner Triple System

  1. Apr 26, 2015 #1
    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. jcsd
  3. Apr 26, 2015 #2
    Try subtracting the number of non-disjoint sets from the total.
     
  4. Apr 26, 2015 #3
    Can you elaborate please? What does it mean when a STS is disjoint from a given triple?
     
  5. Apr 26, 2015 #4
    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.]
     
  6. Apr 26, 2015 #5
    Oh, I see thank you.
     
  7. Apr 26, 2015 #6
    Were you able to prove the desired result ?
     
  8. Apr 26, 2015 #7
    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?##
     
  9. Apr 26, 2015 #8
    Let Inline1.gif be a set of Inline2.gif elements together with a set Inline3.gif of 3-subset (triples) of Inline4.gif such that every 2-subset of Inline5.gif 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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics: Steiner Triple System
  1. Steiner Triple System (Replies: 1)

  2. Triple integral system (Replies: 1)

Loading...