This question already has an answer here:

This is a homework problem I have to solve, and I think I might be misunderstanding it. I'm translating it from Polish word for word.

$n$ points are placed on a circle, and all the chords whose endpoints they are are drawn. We assume that no three chords intersect at one point.

a) How many parts do the chords dissect the disk?

b) How many triangles are formed whose sides are the chords or their fragments?

I think the answer to a) is $2^n$. But I couldn't find a way to approach b), so I calculated the values for small $n$ and asked OEIS about them. I got A006600. And it appears that there is no known formula for all $n$. This page says that

$\text{triangles}(n) = P(n) - T(n)$

where $P(n)$ is the number of triangles for a convex n-gon in general position. This means there are no three diagonal through one point (except on the boundary). (There are no degenarate corners.) This number is easy to calculate as:

$$P(n) = {n\choose 3} + 4{n\choose 4} + 5{n\choose5} + {n\choose6} = {n(n-1)(n-2)(n^3 + 18 n^2 - 43 n + 60)\over720}$$

The four terms count the triangles in the following manner [CoE76]:

$n\choose3$: Number of trianges with 3 corners at the border.

$4{n\choose4}$: Number of trianges with 2 corners at the border.

$5{n\choose5}$: Number of trianges with 1 corners at the border.

$n\choose6$: Number of trianges with 0 corners at the border.

$T(n)$ is the number of triple-crossings (this is the number of triples of diagonals which are concurrent) of the regular $n$-gon. It turns out that such concurrences cannot occur for n odd, and, except for obvious cases, can only occur for $n$ divisible by $6$. Among other interesting results, Bol [Bol36] finds values of n for which $4$, $5$, $6$, and $7$ diagonals are concurrent and shows that these are the only possibilities (with the center for exception).

The function $T(n)$ for $n$ not divisible by $6$ is:

$$T(n) = {1\over8}n(n-2)(n-7)[2|n] + {3\over4}n[4|n].$$

where $[k|n]$ is defined as $1$ if $k$ is a divisor of $n$ and otherwise $0$.

The intersection points need not lie an any of lines of symmetry of the $2m$-gon, e. g. for $n=16$ the triple intersection of $(0,7),(1,12),(2,14)$.

If I understand the text correctly, it doesn't give a general formula for $T(n)$. Also I've found a statement somewhere else that some mathematician wasn't able to give a general formula solving this problem. I haven't found a statement that it is still an open problem, but it looks like it to me.

So am I just misunderstanding the problem, or misunderstanding what I've found on the web, or maybe it is indeed a very hard problem? It's the beginning of the semester, our first homework, and it really scares me.


marked as duplicate by MJD, Amzoti, user67258, Dan Rust, user1729 Jul 22 '13 at 18:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ The answer is not $2^{n-1}$. However, this is a wonderful example of a sequence which is not "obvious". That is, when you give me a sequence of, say $n$ numbers, it is possible to give an arbitrary number as the $n+1^{th}$ member of the sequence and back it up with a valid reason. For example, this sequence goes 2, 4, 8, 16, 31... So if a friend gives you the sequence 2, 4, 8, 16 and asks you what comes next you can say "31" and give them a perfectly logical reason as to why! $\endgroup$ – user1729 Jul 22 '13 at 18:53

The answer to a) isn't $2^n$. It isn't even $2^{n-1}$, which is probably what you meant. Draw the case $n=6$, carefully, and count the regions.

As for $T(n)$, the number of triple-crossings, the problem statement specifically says there are no triple-crossings.

  • $\begingroup$ Oh, I misunderstood what "concurrent" meant! Thank you very much! $\endgroup$ – Bartek Feb 25 '13 at 0:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.