Number of discrete "curves" in two dimensions

[Perhaps check it again]

Let n = a positive integer.

 

Suppose you choose n distinct points on a line.  The distance between

any pair of points is irrelevant. 

 

 

A "curve" is either:

 

1) an individual point

 

2) a set of at least two points

 

3) an individual line segment

 

4) a set of at least two line segments

 

5) some combination of the above

 

 

I will label the points with A, B, C, ..., Y, Z, AA, AB, ..., and so on

as needed, consecutively from left to right, as we see them on

the screen.

 

If a line segment contains more than two points (recall that these are

discrete), then they will be labeled with only their endpoints.  Each

"curve" in a list will be separated by a comma.  The ordering in the

list is irrelevant.

 

The topic in this post involves the unordered listing and number of

the total of discrete "curves" in two dimensions for n distinct points,

where n is greater than or equal to one.

 

 

Examples:

--------------

 

 

n = 1

 

 

<----------------- A ---------------->

 

 

List:  {A}

 

Total:  1

 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

 

 

n = 2

 

 

<-------------- A ----------- B ------------->

 

 

List:  {A}, {B}, {A, B}, {AB}

 

Total:  4

 

 

Note:  Here, you cannot have {A, AB}, {B, AB}, or {A, B, AB},

because neither point A nor point B is isolated once you

identify AB as a line segment in the set.

 

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

 

 

n = 3

 

 

<-------- A -------- B -------------- C ----------->

 

 

List of points only:  {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}

 

List of line segments only: {AB}, {BC}, {AC}

 

List of points and line segments mixed:  {A, BC}, {AB, C}

 

Total:  12

 

 

Note:  Here, you cannot have {B, AC}, because point B is not

an isolated point.  It is part of line segment AC, and AC has

already been listed.

 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

 

 

Puzzle:  Compute the total number of "curves" for n = 4.

 

 

 

*** Optional additional question:  If you continue on getting

totals for n = 5, 6, 7, 8, ..., you will get a sequence that might

suggest a pattern to you.

 

As with all sequences, there are an infinite number of pos-

sibilities for a formula.  However, there is a formula that I have

in mind.  Whatever formula you get, do not attempt to

prove it.  Just type the formula in your reply.

 

[bonanova]

2

ⁿ

[Pickett]

(2ⁿ-1) + ((n²-n)/2) + ((3ⁿ⁺¹ - 2ⁿ⁺³ + 6 + (-1)ⁿ⁺¹)/12)

 

Validated out to n=5 so far...I'm pretty sure on the first two parts of that formula...it's the last/third that I'm a little questionable on...and if that's correct, here are the values up to 9:

n=1: 1

n=2: 4

n=3: 12

n=4: 31

n=5: 81

n=6: 218

n=7: 610

n=8: 1753

n=9: 5127

Edited December 15, 2014 by Pickett

[Perhaps check it again]

bonanova,

 

the main puzzle asks for the answer for when n = 4.  Maybe you kept it to yourself.

Did you have the value for n = 4?

 

 

Pickett,

 

you didn't get a confirmation either way for the total for n = 4, before going into more

calculations for the totals for larger n and then working on a formula.

 

The values for n = 4, 5, ... are different.

 

In the following spoiler, I show the listing and the total for n = 4: 

 

 

n = 4

 

<---------- A --------- B ------------ C ---------------- D ------------->

 

 

list of points only:  {A}, {B}, {C}, {D}, {A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}

 

{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D}

 

list of line segments only:  {AB}, {BC}, {CD}, {AB, CD}, {AC}, {BD}, {AD}

 

list of points and line segments mixed:  {A, BC}, {A, CD}, {A, BD}, {B, CD},

 

{AB, C}, {AB, D}, {BC, D}, {AC, D}, {A, B, CD}, {A, BC, D}, {AB, C, D}

 

 

Total:  33

Edited December 15, 2014 by Perhaps check it again

[Perhaps check it again]

To follow up to my prior post, I will show the listing and the total for n = 5:

 

 

n = 5:

 

 

<------ A --------- B ---------- C -------------- D --------- E ------------>

 

 

points only:  {A}, {B}, {C}, {D}, {E}, {A, B}, {A, C}, {A, D}, {A, E}, {B, C}, {B, D}, {B, E},

 

{C, D}, {C, E}, {D, E}, {A, B, C}, {A, B, D}, {A, B, E}, {A, C, D}, {A, C, E}, {A, D, E},

 

{B, C, D}, {B, C, E}, {B, D, E}, {C, D, E},  {A, B, C, D}, {A, B, C, E}, {A, B, D, E},

 

{A, C, D, E}, {B, C, D, E}, {A, B, C, D, E}

 

 

line segments only:  {AB}, {BC}, {CD}, {DE}, {AB, CD}, {AB, DE}, {BC, DE}, {AC},

 

{BD}, {CE}, {AB, CE}, {AC, DE}, {AD}, {BE}, {AE}

 

 

points and line segments mixed:  {A, BC}, {A, CD}, {A, DE}, {B, CD}, {B, DE}, {AB, C},

 

{C, DE}, {AB, D}, {BC, D}, {AB, E}, {BC, E}, {CD, E}, {A, BD}, {A, CE}, {A, BC, DE},

 

{B, CE}, {AB, C, DE}, {AC, D}, {AC, E}, {BD, E}, {AB, CD, E}, {A, BE}, {AD, E},

 

{A, B, CD}, {A, B, DE}, {A, C, DE}, {A, BC, D}, {A, BC, E}, {A, CD, E}, {B, C, DE},

 

{B, CD, E}, {AB, C, D}, {AB, C, E}, {AB, D, E}, {BC, D, E}, {A, B, C, DE},

 

{A, B, CD, E}, {A, BC, D, E}, {AB, C, D, E}, {AC, D, E}, {A, BD, E}, {A, B, CE}

 

 

Total:  88

 

 

 

 

Reminder:  The total for n = 4 is actually:

33.

 

Edited December 15, 2014 by Perhaps check it again

[witzar]

Fibonacci(2n+1)-1

[DejMar]

"curve" sequence [Fibonacci (2n+1)-1 : n ∈ ℤ

⁺ ] 1, 4, 12, 33, 88, ...

n = 4
List of points only:
{A}, {B}, {C}, {D}, {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

List of line segments only:
{AB}, {AC}, {AD}, {BC}, {BD}, {CD}, {AB,CD}

List of points and line segments mixed:
{AB,C}, {AB,D} {A,BC}, {BC,D}, {A,CD}, {B,CD}, {A,BD}, {AC,D), {A,B,CD}, {A,BC,D}, {AB,C,D}

[Perhaps check it again]

witzar, I clicked yours as "Mark Solved," because it's posted before the next poster's,

and you both show the same formula.