Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On a regular hendecagon (2 dimensions), how many non-symmetric ways can you draw a maximal set of non-intersecting diagonals?

This puzzle has been driving me crazy! I've been doing it by hand.

-The maximal set is defined as the largest number of diagonals that do not intersect, except at the endpoints

-Please also note reflects and rotations are not valid. (i.e. only counts as one)

Any ideas of how to go about problem solving would be helpful!

share|improve this question
    
Can the diagonals intersect at the vertices? And by "maximal", do you mean that the set has the maximal number of diagonals, or just that it can't be extended by adding another non-intersecting diagonal to it? –  joriki Aug 20 '12 at 21:47
    
Evidently means 11 sides. Who knew? –  Will Jagy Aug 20 '12 at 21:48
    
Dear Nat, on math.SE, the proper way to notify users is to add the symbol @ before their usernames, e.g. @Nat –  user2468 Aug 20 '12 at 22:06
    
@joriki It can intersect only at vertices (end points), but not inside the hendecagon. Maximal for a hendecagon is 8 without intersecting, I believe –  Nat Aug 20 '12 at 22:13
2  
It could also mean a figure bounded by ten hens. –  Will Jagy Aug 20 '12 at 22:23
show 7 more comments

1 Answer 1

I'm not entirely sure about this, but I think you can count them like this:

For $8$ diagonals to fit in, there must be one that connects vertices that are only $2$ apart. Let's number the vertices consecutively such that two such vertices are numbered $2$ and $4$. Then either $2$ must be connected to $5$, or $4$ to $1$. Without loss of generality, assume that $4$ is connected to $1$. From now on, we always have a binary choice of drawing a line from either vertex of the line just drawn to the nearest neighbour of the other vertex. These choices can be associated with the $6$ central diagonals, which are either dead ends or connect two parts of the set. These six choices would yield $2^6$ sets, but the ones without mirror symmetry are counted twice. There are $2^3$ with mirror symmetry, so the total is $(2^6-2^3)/2+2^3=(64-8)/2+8=36$.

share|improve this answer
    
If this method of counting is correct, then OEIS A005418 is the associated sequence, with $n=1$ corresponding to a pentagon. –  joriki Aug 20 '12 at 22:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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