1

How many ways are there to break up the regular 9-gon into triangles by diagonals?

UPD
Guaranteed to be convex - yes.
Intersecting "diagonals" be allowed - yes.

2nd UPD
It is task for programming course, so there is no need deep math.
It is more about combinatorics.

sashaaero
  • 157
  • Is the nonagon regular? – wythagoras May 04 '15 at 17:39
  • @wythagoras Yes it is. – sashaaero May 04 '15 at 17:40
  • 1
    I was wondering the same thing: are intersections of these diagonals allowed? (Edited:) Otherwise you'll probably have to do something using Catalan numbers. – HSN May 04 '15 at 17:52
  • 1
    Are the vertices of the 9-gon distinguishable? That is, if I break the 9-gon up by adding all edges from vertex 1, is that different from breaking it up by adding all edges from vertex 2? – Joffan May 04 '15 at 17:57
  • @Joffan i didn't cut any words from question. There are not any additional comments. Bad for me - but idk. – sashaaero May 04 '15 at 17:58
  • @hardmath does the square of figure make sense? I updated some info. – sashaaero May 04 '15 at 18:09
  • I'm more confused than before. @Aero can you tell us what the answer is for a square (4-gon)? Or, if you can manage it, a pentagon (5-gon)? – Joffan May 04 '15 at 18:15
  • I just meant that if you ask about a square (convex quadrilateral) rather than a nonagon, it will be clear that if intersecting diagonals are allowed, this introduces additional triangulations of the figure. If no intersections, then a square would be triangulated by adding one (of two possible) diagonals, while adding both diagonals would give you another solution (but they would intersect). – hardmath May 04 '15 at 18:17
  • @Joffan For square - answer is 2 I guess. – sashaaero May 04 '15 at 18:19
  • @hardmath For square - answer is 2 I guess. – sashaaero May 04 '15 at 18:20
  • Okay, that means the diagonals are not allowed to intersect? – hardmath May 04 '15 at 18:20
  • @aero look at the top figure on this page(link) - does this look like what you are talking about? – Joffan May 04 '15 at 18:22
  • That sounds like intersections are not allowed. And a lot like what I meant to say about Catalan numbers. – HSN May 04 '15 at 18:24
  • @Joffan add your link as answer pls. It is correct. Thank you. – sashaaero May 04 '15 at 18:27

1 Answers1

0

The number of ways of subdividing a regular polygon into triangles is a well-known property of Catalan numbers. For a $(n+2)$-sided polygon, there are $C_n$ possible subdivisions.

Joffan
  • 39,627