Hosted by The Math Forum

Problem of the Week 956

Counting Nonadjacent Edges

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

Given a convex n-gon, with vertices denoted in order by P_1, P_2, ..., P_n, let G_n be the graph obtained as a result of tracing the zig-zag polygonal path from P_1 to P_(n-1) to P_2 to P_(n-2), etc. and eventually to P_m where

m = (n-1)/2 if n is odd

m = (n+2)/2 if n is even

Note the edges and vertices of the original n-gon are included in G_n. For n >= 3 let a(n) be the number of sets of nonadjacent edges from G_n. For example if we start with a convex 4-gon which has four vertices and four edges, we add the edge connecting P_1 to P_3. This graph has a(4) = 8 since in addition to the empty set, G_4 has five sets consisting of a single edge each, and two sets consisting of two nonadjacent edges.

Find a(15).

Source: Emeric Deutsch of Polytechnic University, Brooklyn, NY for MATHEMATICS MAGAZINE. This problem originally appeared in the February 2001 issue.
© Copyright 2002 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


13 March 2002