Looking for a formula that counts the number of unique constructions of "coffee tables" that have an n-gon tabletop.

Question

Coffee tables are build by placing legs under vertices of an n-gon in such a way that the table won't tip over. Here are the rules:

1. If n is even we can use (2, ..., n) legs. Every valid table must built either with two of its legs at opposite vertices and any number of extra legs up to n, or so that when you choose any leg you can draw a line from its associated vertex that bisects the n-gon and at least one leg lies on either side.

2. If n is odd we can use (3, ..., n) legs. Every valid table must be built so that when you choose any leg and draw a line from its associated vertex through the center of the n-gon and to the mid-point of the face opposite there is at least one leg on either side of the bisected n-gon.

For n=2, a digon is a degenerate polygon, so I'm not sure if a(2)=0 or a(2)=1. For now I am counting it as valid, so the sequence I get for a(2)-a(8) is {1, 1, 3, 3, 8, 10, 23}.

Here is what a(3)-a(5) look like:

Answer 1

Centroids

Artimis Fowl raised the issue of whether this condition places the centroid of the table inside the footprint (i.e. the convex hull) of the legs, which would be the physical condition required for equilibrium. (Obviously the degenerate case of two legs opposite each other with an even number of sides is not a stable equilibrium, but never mind that). Establishing that the given conditions are equivalent to the centroid condition is actually quite useful, and I would like to thank Artimis for bringing it up.

Since the legs are all on the circumcircle of the n-gon, the convex hull of a set of them is just the polygon which has them as vertices; and by symmetry of the regular n-gon its centroid is the centre of the circumcircle.

A simpler statement of the given condition is

(Every valid table must have at least one leg); when you choose any leg and draw a line from its associated vertex through the centre of the n-gon that line either passes through another leg or has at least one leg on either side.

If the convex hull contains the centroid then this condition certainly holds, because the line from each vertex of the convex hull to the centroid must be entirely inside the convex hull, so if consider the two edges from that vertex to its adjacent vertices in the convex hull then either they coincide and both pass through the centroid to the opposite point (degenerate case) or they enclose the line to the centroid.

Conversely, if the condition holds then either we have the degenerate case and the centroid is on both edges of the convex hull; or we have the non-degenerate case and can proceed by contradiction. Suppose the condition holds but the centroid is outside the convex hull; consider the two vertices which are endpoints of the edge of the convex hull nearest the centroid. Then neither of those satisfies the condition, giving a contradiction.

Counting

A direct count gets quite messy. It is much simpler to count the convex hulls which don't include the centroid, as you yourself hinted in chat.

Let the number of vertices between the endpoints of the chord nearest the centre be $0 \le a \le \left\lfloor\frac{n-3}{2}\right\rfloor$; then there are $2^a$ basic configurations (with two legs or more), of which $2^{\left\lceil\frac{a}{2}\right\rceil}$ are symmetric and the rest are double-counted. There's also one configuration with one leg (assuming $n > 0$), and one with no legs. So we get an exclusion count of $$E(n) = 2 + \frac{1}{2}\sum_{a=0}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\left(2^a + 2^{\left\lceil\frac{a}{2}\right\rceil}\right)$$

We need to subtract that from the total number of convex hulls up to dihedral symmetry. This is equivalent to the number of bracelets over a binary alphabet, which is OEIS A000029 and has formula $$\textrm{A000029}(n) = \frac{1}{2n} \sum_{d \mid n} \varphi(d)2^{\frac{n}{d}} + \begin{cases} 2^{\frac{n}{2}-1}+2^{\frac{n}{2}-2} & \text{if $n$ is even} \\ 2^{\frac{n-1}{2}} & \text{if $n$ is odd} \end{cases}$$

This gives us the answer: $\textrm{A000029}(n) - E(n)$, which I've sanity-checked against brute-force enumeration up to $n=18$.

Tidying up

Since we've got that case split, we might as well case-split $E(n)$ and see what cancels. Assuming $k > 0$, $$\begin{eqnarray*} E(4k) & = & 2 + \frac{1}{2}\sum_{a=0}^{2k-2}\left(2^a + 2^{\left\lceil\frac{a}{2}\right\rceil}\right) \\ & = & 2 + \frac{1}{2}\sum_{b=0}^{k-1}\left(2^{2b} + 2^{\left\lceil\frac{2b}{2}\right\rceil} + 2^{2b+1} + 2^{\left\lceil\frac{2b+1}{2}\right\rceil}\right) - \frac{1}{2}\left(2^{2k-1} + 2^{\left\lceil\frac{2k-1}{2}\right\rceil}\right) \\ & = & 2^k + 2^{2k-2} \\ \end{eqnarray*}$$

For other offsets we don't need to worry about the special case caused by $n = 0$. $$\begin{eqnarray*} E(4k+1) & = & 2 + \frac{1}{2}\sum_{a=0}^{2k-1}\left(2^a + 2^{\left\lceil\frac{a}{2}\right\rceil}\right) \\ & = & 2 + \frac{1}{2}\sum_{b=0}^{k-1}\left(2^{2b} + 2^{\left\lceil\frac{2b}{2}\right\rceil} + 2^{2b+1} + 2^{\left\lceil\frac{2b+1}{2}\right\rceil}\right) \\ & = & 3 \cdot 2^{k-1} + 2^{2k-1} \end{eqnarray*}$$

$$\begin{eqnarray*} E(4k+2) & = & 2 + \frac{1}{2}\sum_{a=0}^{2k-1}\left(2^a + 2^{\left\lceil\frac{a}{2}\right\rceil}\right) = E(4k+1) \end{eqnarray*}$$

$$\begin{eqnarray*} E(4k+3) & = & 2 + \frac{1}{2}\sum_{a=0}^{2k}\left(2^a + 2^{\left\lceil\frac{a}{2}\right\rceil}\right) = E(4k+4) \end{eqnarray*}$$

So we get a final formula of

$$ %\frac{1}{2n} \sum_{d \mid n} \varphi(d)2^{\frac{n}{d}} + %\begin{cases} %2^{2k-1}+2^{2k-2} - (2^k + 2^{2k-2}) & \text{if $n = 4k$} \\ %2^{2k} - (3 \cdot 2^{k-1} + 2^{2k-1}) & \text{if $n = 4k+1$} \\ %2^{2k}+2^{2k-1} - (3 \cdot 2^{k-1} + 2^{2k-1}) & \text{if $n = 4k+2$} \\ %2^{2k+1} - (2^{k+1} + 2^{2k}) & \text{if $n = 4k+3$} %\end{cases} \frac{1}{2n} \sum_{d \mid n} \varphi(d)2^{\frac{n}{d}} + \begin{cases} 2^{2k-1} - 2^k & \text{if $n = 4k$} \\ 2^{2k-1} - 3 \cdot 2^{k-1} & \text{if $n = 4k+1$} \\ 2^{2k} - 3 \cdot 2^{k-1} & \text{if $n = 4k+2$} \\ 2^{2k} - 2^{k+1} & \text{if $n = 4k+3$} \end{cases} $$