CODEWITHSUNDEEP
mathgeometrycombinations
Shashwat Kumar
Shashwat Kumar

Reputation: 5287

Finding the total number of configurations by forming triangles in N clockwise points

There are fixed N points numbered 1 to N, in a circle in clockwise direction. We want to create triangles by choosing any three points.

We can create as many triangles but no two triangles should cross each other and one point can share only one triangle. So how many such configurations are possible?

For example, let there are 10 points:

I could solve partially:

I am unable to solve for higher number of triangles.

Upvotes: 1

Views: 875

Answers (1)

MvG
MvG

Reputation: 60858

For the following considerations, I'd like to treat “no triangle at all” as a valid configuration, too. You can subtract one in the end to get rid of that.

So think about this recursively. Given n points, you have two options: either you choose “no triangle at all” and return, or you select three points to form one triangle, and then recurse. If you have the three corners, they will split your circle into three ranges. All subsequent triangles have to have corners from a single range, as otherwise they would overlap. If you restrict them to one of these ranges, they will not intersect your first triangle. For the recursion, you can treat each of these ranges like a small circle (check for yourself that the statements about intersections are still valid there).

OK, the above will generate all possible ordered sequences of triangles. If you don't care about order, you have to eliminate it somehow. One possibility would be dividing each count by n! where n is the number of triangles eventually generated. Another way would be fixing a complete order for triangles (i.e. order by minimal corner index), and ensuring that recursion will never generate triangles smaller than the ones chosen before.

With these ideas, you should be able to write a small script to enumerate triangle configurations for a few numbers of points. You might even be able to check a few cases manually. Perhaps having that script is enough. If not, you could feed that sequence (with or without the offset due to “no triangles at all”) to the On-Line Encyclopedia of Integer Sequences™ and see whether they have a formula for you. Or find one yourself, possibly with the help of a generating function. If everything else fails, you might want to take this to the Math SE.

EDIT:
Unless I made a mistake implementing my own small script, the sequence you ask for, including the “no triangles at all” instance, is OEIS A071879. There is a formula as well. I generated that sequence using the following piece of python code:

c = [1, 1, 1]
for n in range(3, 30):
    s = 1
    for i1 in range(0, n - 2):
        for i2 in range(i1 + 1, n - 1):
            for i3 in range(i2 + 1, n):
                s += c[i2 - i1 - 1]*c[i3 - i2 - 1]*c[n - i3 - 1]
    assert len(c) == n
    c.append(s)
    print(s)

Upvotes: 2

Related Questions