1. Limited time only! Sign up for a free 30min personal 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!

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


    User Avatar
    2017 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,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


    User Avatar
    2017 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:


    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


    User Avatar
    2017 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted