StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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.</p> <p>So think about this recursively. Given <em>n</em> 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).</p> <p>OK, the above will generate all possible <em>ordered</em> sequences of triangles. If you don't care about order, you have to eliminate it somehow. One possibility would be dividing each count by <em>n!</em> where <em>n</em> 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 <em>smaller</em> than the ones chosen before.</p> <p>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 <a href="http://oeis.org/" rel="nofollow noreferrer">the On-Line Encyclopedia of Integer Sequences™</a> and see whether they have a formula for you. Or find one yourself, possibly with the help of a <a href="http://en.wikipedia.org/wiki/Generating_function" rel="nofollow noreferrer">generating function</a>. If everything else fails, you might want to take this to the <a href="https://math.stackexchange.com/">Math SE</a>.</p> <p><strong>EDIT:</strong><br> Unless I made a mistake implementing my own small script, the sequence you ask for, including the “no triangles at all” instance, is <a href="https://oeis.org/A071879" rel="nofollow noreferrer">OEIS A071879</a>. There is a formula as well. I generated that sequence using the following piece of python code:</p> <pre class="lang-python prettyprint-override"><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) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload