Number of diagonals in polygon connecting different vertices

Question

I run into a combinatorics problem recently. Let's imagine we have a n-sided polygon, the number of diagonals is easily $$N=\frac{n(n-3)}{2}$$

However, for my work, I need to group the vertices in pairs, where I cannot group nearest neighbouring vertices, i.e., I need to know the number of ways to draw $n/2$ diagonals in an $n$-sided polygon, where we draw one diagonal from each vertex.

Anybody got some hints for that? For n=4 there is only 1 such case, and for n=6 we have 4. But for larger n it becomes tedious.

Also I need only even number of sides n.

Thank you in advance!!

Answer 1

First, ignore the condition that adjacent vertices cannot be paired up. The number of ways to pair up the vertices into $n/2$ disjoint pairs is $n!!$, the double factorial, defined by $$ (n-1)!!\stackrel{\text{def}}=(n-1)(n-3)(n-5)\cdots=\prod_{i=0}^{\lfloor n/2\rfloor-1}(n-1-2i). $$ To account for the condition that adjacent vertices cannot be paired, we use the principle of inclusion exclusion.

Let $S$ be the set of all vertex pairings, so $|S|=n!!$. For each $i\in \{1,\dots,n\}$, let $E_i$ be the set of vertex pairings where vertex number $i$ is paired with its clockwise neighbor. I assume the vertices so the clockwise neighbor of $i$ is $i+1$ (with addition wrapping modulo $n$). The set of legal pairings is $S\setminus (E_1\cup \dots \cup E_n)$, and PIE tells us that $$ \begin{align} |S\setminus (E_1\cup \dots \cup E_n)| &=\sum_{k=0}^n(-1)^k\sum_{1\le i_1<\dots <i_k\le n}|E_{i_1}\cap \dots \cap E_{i_k}|. \end{align}\tag1 $$ To evaluate $|E_{i_1}\cap \dots \cap E_{i_k}|$, there are two cases.

1. Suppose the list of indices $[i_1,\dots,i_k]$ contains an adjacent pair, meaning that there exists $r\in \{1,\dots,k\}$ such that $i_{r+1}=i_r+1$ (or, $i_1\equiv i_n+1\pmod n$). In this case, $|E_{i_1}\cap \dots \cap E_{i_k}|=0$. This is because it is impossible to simultaneously have vertex number $i_r$ paired with $i_r+1$, and to have vertex $i_{r}+1$ paired with $i_r+2$.

2. Otherwise, the indices represent pairwise nonadjacent vertices. In this case, there are $k$ particular vertices which must be paired with their clockwise neighbors. This leaves $n-2k$ vertices to be paired up arbitrarily, which can be done in $(n-1-2k)!!$ ways.

In summary, the innermost summation in $(1)$ has two types of terms: zeroes, and $(n-1-2k)!!$. Therefore, instead of summing over all ways to choose indices such that $1\le i_1<\dots <i_k\le n$, we can simply count the number of ways to choose these indices which fall in case $2$, and then multiply by $(n-1-2k)!!$. That is, if we let $N(n,k)$ be the number of ways to select $k$ nonadjacent vertices on an $n$-gon, then the final answer is $$ |S\setminus (E_1\cup \dots \cup E_n)|=\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k N(n,k) (n-1-2k)!! $$ Note: When $k=n/2$, the term is $N(n,n/2)· (-1)!!$. By definition, $(-1)!!=1$. This is the convention that makes the most sense, like how we define $0!$ to be $1$.

All that remains is to evaluate $N(n,k)$. There is a simple formula for $N(n,k)$ in terms of $n$ and $k$ that involves a binomial coefficient. It is a nice exercise to try to work it out, so I encourage you to do so. If you get stuck, see this old MSE question.

Answer 2

Let $P_n$ be the $n$-sided polygon.

Let $...-a-b-c-...$ be three consecutive vertices. Contracting vertex $b$ means replacing the previous pattern with the pattern $...-a-c-...$ (so we get a polygon with $n-1$ faces).

Let $...-a-b-c-d-...$ be four consecutive vertices. Contracting face $b-c$ means replacing the previous pattern with the pattern $...-a-d-...$ (so we get a polygon with $n-2$ faces.

Let $T(n)$ be the number of possibilities of grouping vertices of $P_n$ with no two adjacent vertices grouped.

Let $T^*(n)$ be the number of possibilities grouping vertices of $P_n$ with no two adjacent vertices grouped except for one distinguished face, for which extremities may or may not be grouped.

Let $T(n, k)$ be the number of possibilities of grouping vertices of $P_n$ with no two adjacent vertices grouped except for two distinguished faces for which extremities may or may not be grouped. These two pairs of vertices are at distance $k$ (two adjacent faces are at distance $1$). Note that we have $T(n, k) = T(n, n-k)$

We have the following induction:

• Lets pick a valid grouping for $P_n$. Lets pick an arbitrary vertex, and consider the corresponding pair. We contract both vertices from the pair. Let $1 < k < n-1$ the distance between the vertices ($k!\neq 1$ and $k\neq n-1$ since we cannot group adjacent vertices), the number of valid groupings is then $T(n-2, k)$, since for both contracted vertices, the surrounding vertices (that now becomes adjacent) may be grouped. $$T(n) = \sum_{k=2}^{n-2}T(n-2, k-1)$$ It initializes with $T(0) = 1$.
• Lets pick a valid grouping for $P_n$ with two distinguished faces distant of $1 < k < n-1$. Lets pick one of the distinguished faces. If the extremities are not grouped, we have $T^*(n)$ possible groupings. Otherwise, lets contract this face. We get $T(n-2, k-1)$ groupings, since the other face is still distinguished, and the pair of edges surrounding the contracted face is now distinguished. So we have for $1 < k < n-1$: $$T(n, k) = T^*(n) + T(n-2, k-1)$$ It initializes with $T(0, k) = 1$
• For $k=1$ or $k=n-1$, when contracting, we get no distinguished face, so we get: $$T(n, 1) = T(n, n-1) = T^*(n) + T^*(n-2)$$
• Lets pick a valid grouping for $P_n$ with one distinguished face. If the extremities are not grouped, we get $T(n)$ groupings. Otherwise, we contract the face, and we get exactly one distinguished face, so: $$T^*(n) = T(n) + T^*(n-2)$$ It initializes with $T^*(0) = 1$ and $T^*(2) = 0$.

We can use dynamic programming to compute $T(n)$ efficiently.

---

Apparently, $T(n) = nT(n-2)-(n-6)T(n-4)-T(n-6)$ for $n>8$ is a valid induction formula according to https://oeis.org/A003436, but I'm not able to get to such an induction.