Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Function for line segment configuration between dots

  1. Jul 3, 2016 #1
    If I have n dots, how many configurations exist for lines that connect them, including no connections?

    For example, if I have 0, or 1 dots I believe this should be 0 since no connections are possible (or perhaps I should consider the single dot as having a single connection to itself?) If I have 2 dots, there would be two possibilities, one connection between the two, and zero connections.

    To clarify what I mean, for three dots I counted 8: http://i.imgur.com/EHZLcYe.png

    For four dots I counted 65, but I could be wrong as I was drawing them and this is error prone: http://imgur.com/Zw0JM0j
    The final possibility used 6 lines.

    I tried looking through various possibilities and renditions in OEIS, but nothing popped out.

    I'm having trouble coming up with a function that returns such an odd sequence as 0,0,2,8,65. I'm hoping that I goofed, because 0,0,2,8,64 looks a lot more palpable.

    Surely this function is known? Or something very similar?

    Thank you for your time.
     
  2. jcsd
  3. Jul 4, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    0 dots: Well...
    1 dot: There is 1 configuration: no lines.

    4 dots: There are 6 possible lines, they all can be present or not (2 options each), for a total of 26=64 options.
    Do you see the pattern?

    In your image, the "N" pattern has a duplicate: second block, first column third row and second column fourth row.
     
  4. Jul 4, 2016 #3
    I'll just use zero for 0 dots.

    0,1,2,8,64..

    0,20,21, 23, 26..

    I suppose 5 dots would have 8 lines to connect them all, so I should expect 2^8 configurations, if the function is 2^n where n is number of lines to connect all the dots. Now I need a function that gets n from a number of dots.

    For two dots it was one line, three dots, 3 lines, four dots, 6 lines, 5 dots, 8 lines, 6 dots, 14 lines.

    undefined,0,1,3,6,8,14 Ugh.

    Thank goodness!
     
  5. Jul 4, 2016 #4

    jim mcnamara

    User Avatar

    Staff: Mentor

  6. Jul 4, 2016 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Why 8? Compared to 4 dots (6 possible edges), you get 4 additional options for an edge - one for each of the original dots. 6+4=10.
     
  7. Jul 5, 2016 #6
    You are correct. I got the number wrong for 6 dots too, sigh. I believe it is 15.

    So to make a chart:

    dots max lines configurations (assuming 2^(maxlines))

    0 undefined 0
    1 0 1
    2 1 2
    3 3 8
    4 6 64
    5 10 1024
    6 15 32768

    It's hard to believe that 6 dots would have so many configurations.

    So for d dots I get:

    2(d/2)(d-1)

    For zero dots I get one configuration this way, but oh well. Not all that important.

    I came across that link when looking at this, but I didn't understand it and so wasn't even sure if it fit the problem I was trying to solve. Looking at it more carefully I see that it is quite relevant :-)

    Assuming 2(d/2)(d-1) holds, I believe my question has been answered. Thanks for the help.
     
  8. Jul 5, 2016 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That is the right formula.
    I think that is a natural result. Same as for one dot, "no connections" is the unique configuration.
     
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: Function for line segment configuration between dots
  1. Line segment (Replies: 3)

Loading...