Problem of the Week 956

Counting Nonadjacent Edges

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.