# I Function for line segment configuration between dots

1. Jul 3, 2016

### Labyrinth

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?

2. Jul 4, 2016

### 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.

3. Jul 4, 2016

### Labyrinth

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!

4. Jul 4, 2016

5. Jul 4, 2016

### 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.

6. Jul 5, 2016

### Labyrinth

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.

7. Jul 5, 2016

### 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.