11
$\begingroup$

Here we have a simple, but a very hard problem: How many different figures (or graphs) can be formed with a regular polygon of n vertices and a number d of diagonals of this polygon?

Consider T(n,d) the total number of distinct figures formed by the polygon of n vertices and d diagonals. The question is: how to determine T(n,d)?

The figure below shows some examples for the pentagon (n=5) and hexagon (n=6), to better understand the problem:

enter image description here

OBS: Rotated or reflected figures will also be considered the same!

I thought about using Polya´s Enumeration Theory, but I didn't understand how I can do that. There seems to be a similarity with the method of counting graphs by Polya´s Counting Theory, or still similar to the circular coloring problem solved by Polya.

Does anyone have any ideas or methods to solve this problem?

$\endgroup$
7
$\begingroup$

We can apply the lemma that is not Burnside’s. You want the equivalence classes under the cyclic group $C_n$, so we have to count the figures that are invariant under the elements of $C_n$. The count is similar to the one performed for necklaces, but a bit more complicated.

For each divisor $k\mid n$, there are $\phi(k)$ elements of $C_n$ of order $k$ (where $\phi$ is Euler’s totient function), and they leave invariant all figures with period $p=\frac nk$. Number the vertices with $1$ through $n$, and denote by $[x]$ the remainder of $x$ modulo $p$. A figure with period $p$ is fully specified by a set of pairs $(r,a)$ with $0\le r\lt p$ and $2\le a\le n-2$, where each pair specifies that if $[x]=r$, then $x$ is connected to $x+a$.

But these sets of pairs must fulfil a condition: If $(r,a)$ is included, then $([r+a],n-a)$ must also be included, since this is the same diagonal, viewed from the other side. This is an involution, since $[[r+a]+n-a]=r$ and $n-(n-a)=a$. If $k$ is even, this involution has fixed points at all $(r,\frac n2)$, whereas if $k$ is odd it has no fixed points.

Let’s handle the simpler case where $k$ is odd first. Here the pairs come in pairs and we can freely choose for half of them, that is, for $\frac12p(n-3)$ of them, whether to use them. Each pair of pairs represents $k$ diagonals, so we can choose diagonals in $\binom{\frac12p(n-3)}{\frac dk}$ different ways. Thus, for a figure to have an odd period $k$, $k$ must divide both $n$ and $d$, and thus $\gcd(n,d)$.

If $n$ is odd, $k$ is always odd, so we can now apply the lemma to find that for odd $n$ there are

$$ P(n,d)=\frac1n\sum_{k\mid\gcd(n,d)}\phi(k)\binom{\frac12\frac nk(n-3)}{\frac dk} $$

different figures with $d$ diagonals. We can check this against your examples for $n=5$:

\begin{eqnarray} P(5,0)&=&\frac15\sum_{k\mid5}\phi(k)\binom{\frac12\frac5k(5-3)}{\frac0k}=\frac15\left(1\cdot\binom50+4\cdot\binom10\right)=1\;, \\ P(5,1)&=&\frac15\sum_{k\mid1}\phi(k)\binom{\frac12\frac5k(5-3)}{\frac1k}=\frac15\left(1\cdot\binom51\right)=1\;, \\ P(5,2)&=&\frac15\sum_{k\mid1}\phi(k)\binom{\frac12\frac5k(5-3)}{\frac2k}=\frac15\left(1\cdot\binom52\right)=2\;, \\ P(5,3)&=&\frac15\sum_{k\mid1}\phi(k)\binom{\frac12\frac5k(5-3)}{\frac3k}=\frac15\left(1\cdot\binom53\right)=2\;, \\ P(5,4)&=&\frac15\sum_{k\mid1}\phi(k)\binom{\frac12\frac5k(5-3)}{\frac4k}=\frac15\left(1\cdot\binom54\right)=1\;, \\ P(5,5)&=&\frac15\sum_{k\mid5}\phi(k)\binom{\frac12\frac5k(5-3)}{\frac5k}=\frac15\left(1\cdot\binom55+4\cdot\binom15\right)=1\;, \end{eqnarray}

(There’s a symmetry $P\left(n,\frac{n(n-3)}2-d\right)=P(n,d)$, since including $d$ diagonals is equivalent to not including the remaining $\frac{n(n-3)}2-d$ diagonals.)

For $k$ even, things are slightly complicated by the fixed points of the involution. Each fixed point represents only $\frac k2$ diagonals. Thus in this case we only need $\frac k2\mid d$, and we can mix pairs of pairs that represent $k$ diagonals with fixed points that represent $\frac k2$ diagonals. Thus in this case there are

$$ \sum_{j=0}^{\left\lfloor\frac dk\right\rfloor}\binom{\frac12p(n-4)}j\binom p{\frac{2d}k-2j} $$

different figures with period $\frac nk$. (Here the binomial coefficients are zero when the lower index is greater than the upper index.)

Thus, when $n$ is even, we have

$$ P(n,d)=\frac1n\left(\sum_{k\mid\gcd(n,d)\atop k\text{ odd}}\phi(k)\binom{\frac12\frac nk(n-3)}{\frac dk}+\sum_{k\mid\gcd(n,2d)\atop k\text{ even}}\phi(k)\sum_{j=0}^{\left\lfloor\frac dk\right\rfloor}\binom{\frac12\frac nk(n-4)}j\binom{\frac nk}{\frac{2d}k-2j}\right)\;. $$

Again, we can check this against your examples for $n=6$:

\begin{eqnarray} P(6,0)&=&\frac16\left(\sum_{k\mid6\atop k\text{ odd}}\phi(k)\binom{\frac12\frac6k(6-3)}{\frac 0k}+\sum_{k\mid6\atop k\text{ even}}\phi(k)\sum_{j=0}^{\left\lfloor\frac 0k\right\rfloor}\binom{\frac12\frac6k(6-4)}j\binom{\frac 6k}{\frac0k-2j}\right) \\ &=& \frac16\left(1\cdot\binom90+2\cdot\binom30+1\cdot\binom30+2\cdot\binom10\right) \\ &=&1\;, \\ P(6,1)&=&\frac16\left(\sum_{k\mid1\atop k\text{ odd}}\phi(k)\binom{\frac12\frac6k(6-3)}{\frac 1k}+\sum_{k\mid2\atop k\text{ even}}\phi(k)\sum_{j=0}^{\left\lfloor\frac 1k\right\rfloor}\binom{\frac12\frac6k(6-4)}j\binom{\frac 6k}{\frac2k-2j}\right) \\ &=& \frac16\left(1\cdot\binom91+1\cdot\binom30\binom31\right) \\ &=&2\;, \\ P(6,2)&=&\frac16\left(\sum_{k\mid2\atop k\text{ odd}}\phi(k)\binom{\frac12\frac6k(6-3)}{\frac 2k}+\sum_{k\mid2\atop k\text{ even}}\phi(k)\sum_{j=0}^{\left\lfloor\frac 2k\right\rfloor}\binom{\frac12\frac6k(6-4)}j\binom{\frac 6k}{\frac4k-2j}\right) \\ &=& \frac16\left(1\cdot\binom92+1\cdot\left(\binom30\binom32+\binom31\binom30\right)\right) \\ &=&7\;. \end{eqnarray}

That last one is one more than you counted, and indeed you missed a figure:

enter image description here

This differs from your first figure by a reflection. (Alternatively, you may have forgotten to mention that you want to consider reflected figures as equivalent; that would of course require a slightly different analysis.)

We can now calculate the value $T(6,3)$ for which you left a question mark:

\begin{eqnarray} P(6,3)&=&\frac16\left(\sum_{k\mid3\atop k\text{ odd}}\phi(k)\binom{\frac12\frac6k(6-3)}{\frac 3k}+\sum_{k\mid6\atop k\text{ even}}\phi(k)\sum_{j=0}^{\left\lfloor\frac 3k\right\rfloor}\binom{\frac12\frac6k(6-4)}j\binom{\frac 6k}{\frac6k-2j}\right) \\ &=& \frac16\left(1\cdot\binom93+2\cdot\binom31+1\cdot\left(\binom30\binom33+\binom31\binom31\right)+2\cdot\binom10\binom11\right) \\ &=&17\;. \end{eqnarray}

And there’s one more value for $n=6$:

\begin{eqnarray} P(6,4)&=&\frac16\left(\sum_{k\mid2\atop k\text{ odd}}\phi(k)\binom{\frac12\frac6k(6-3)}{\frac 4k}+\sum_{k\mid2\atop k\text{ even}}\phi(k)\sum_{j=0}^{\left\lfloor\frac 4k\right\rfloor}\binom{\frac12\frac6k(6-4)}j\binom{\frac 6k}{\frac8k-2j}\right) \\ &=& \frac16\left(1\cdot\binom94+1\cdot\left(\binom30\binom34+\binom31\binom32+\binom32\binom30\right)\right) \\ &=&23\;. \end{eqnarray}

The remaining values for $n=6$ are determined by the above symmetry.


So it turns out that the symmetries were meant to include not just rotations but also reflections. So we need to expand the cyclic group $C_n$ of rotational symmetries to the dihedral group $D_n$ that includes the reflections. The count of figures that are left invariant by the elements of $C_n$ stays the same, and we need to additionally count the figures that are left invariant by reflections.

Since this leads to further sums for involutions with fixed points, let’s introduce some notation for these. Let

$$ \left[n_1,n_2\atop k\right]:= \sum_{j=0}^{\left\lfloor\frac k2\right\rfloor}\binom{n_1}{k-2j}\binom{n_2}j $$

denote the number of ways of choosing $k$ elements from $n_1$ fixed points and $n_2$ pairs that need to be chosen together. With this notation, the count above for even $n$ is

$$ P(n,d)=\frac1n\left(\sum_{k\mid\gcd(n,d)\atop k\text{ odd}}\phi(k)\binom{\frac12\frac nk(n-3)}{\frac dk}+\sum_{k\mid\gcd(n,2d)\atop k\text{ even}}\phi(k)\left[p,\frac12p(n-4)\atop\frac{2d}k\right]\right)\;. $$

I’ll leave the $P(n,d)$ notation as originally defined, denoting the number of equivalence classes of figures under rotations, and denote the number of equivalence classes of figures under rotations and reflections by $R(n,d)$.

Again we need to distinguish between odd and even $n$. For odd $n$, there is only one type of reflection, with the axis passing through a vertex on one side of the polygon and through the midpoint of an edge on the other. Each such reflection induces an involution on the diagonals that has $\frac{n-3}2$ fixed points. Thus, for odd $n$ we have

$$ R(n,d)=\frac1{2n}\left(\sum_{k\mid\gcd(n,d)}\phi(k)\binom{\frac12\frac nk(n-3)}{\frac dk}+n\left[\frac{n-3}2,\frac{(n-1)(n-3)}4\atop d\right]\right) $$

For $n=5$, the new term is

$$ 5\left[\frac{5-3}2,\frac{(5-1)(5-3)}4\atop d\right]=5\sum_{j=0}^{\left\lfloor\frac d2\right\rfloor}\binom1{d-2j}\binom2j\;, $$

which comes out to $5,5,10$ for $d=0,1,2$, as expected, so $R(5,d)=P(5,d)$.

For even $n$, there are two different types of reflections, $\frac n2$ of each type. The first type has an axis passing through two vertices and fixes $\frac n2$ diagonals (the axis itself and $\frac n2-1$ diagonals perpendicular to it). The second type has an axis passing through two midpoints and fixes $\frac {n-4}2$ diagonals (all perpendicular to the axis). Thus, for even $n$ we have

\begin{eqnarray} R(n,d) &=& \frac1{2n}\left(\sum_{k\mid\gcd(n,d)\atop k\text{ odd}}\phi(k)\binom{\frac12\frac nk(n-3)}{\frac dk}+\sum_{k\mid\gcd(n,2d)\atop k\text{ even}}\phi(k)\sum_{j=0}^{\left\lfloor\frac dk\right\rfloor}\binom{\frac12\frac nk(n-4)}j\binom{\frac nk}{\frac{2d}k-2j}\right. \\ && \left.+\frac n2\left[\frac n2,\frac{n(n-4)}4\atop d\right]+\frac n2\left[\frac{n-4}2,\frac{(n-2)^2}4\atop d\right]\right)\;. \end{eqnarray}

For $n=6$, the new term is

\begin{eqnarray} \frac 62\left[\frac 62,\frac{6(6-4)}4\atop d\right]+\frac 62\left[\frac{6-4}2,\frac{(6-2)^2}4\atop d\right] &=& 3\left[3,3\atop d\right]+3\left[1,4\atop d\right] \\ &=& 3\sum_{j=0}^{\left\lfloor\frac d2\right\rfloor}\binom3{d-2j}\binom3j+3\sum_{j=0}^{\left\lfloor\frac d2\right\rfloor}\binom1{d-2j}\binom4j\;, \end{eqnarray}

which comes out to $6,12,30,42,54$ for $d=0,1,2,3,4$, so as expected, $R(6,0)=P(6,0)$ and $R(6,1)=P(6,1)$, whereas $R(6,2)=\frac1{2\cdot6}\left(6P(6,2)+30\right)=6$, so we’ve accounted for the extra figure with reflection symmetry. Also $R(6,3)=\frac1{2\cdot6}\left(6P(6,3)+42\right)=12$ and $R(6,4)=\frac1{2\cdot6}\left(6P(6,4)+42\right)=15$.

$\endgroup$
8
  • $\begingroup$ Thank you very very much Joriki! Wonderful explanation and demonstration! You are right about the reflected figure. In fact I forgot to mention that reflected figures are also the same (as well as graphs). Is it possible to consider this in the equation? Congratulations! Thank you!!! $\endgroup$
    – JaberMac
    Jan 30 '20 at 19:07
  • $\begingroup$ Hello joriki. I corrected the statement considering that reflected figures are also the same. Is it possible to find the formula for this consideration as well? thanks again! $\endgroup$
    – JaberMac
    Jan 31 '20 at 2:19
  • $\begingroup$ @JaberMac: Yes, it's absolutely possible -- I've done half of it but I'm not sure when I'll get around to writing down the rest -- hopefully by Sunday. $\endgroup$
    – joriki
    Jan 31 '20 at 5:53
  • 1
    $\begingroup$ @JaberMac: OK, I've expanded the answer to also treat the case with equivalence under reflections. $\endgroup$
    – joriki
    Feb 1 '20 at 13:54
  • $\begingroup$ Thank you very much joriki! again i am impressed with your brilliant solution and explanation. You helped me a lot, I was looking for a solution to this problem for a long time. Great! Thank you thank you!!! $\endgroup$
    – JaberMac
    Feb 1 '20 at 14:24
0
$\begingroup$

A doubt: applying the formula for the case $n = 7$, $d = 2$ (Heptagon with $2$ diagonals), we have $R(7,2) = 10$. But analyzing the possibilities as shown in the figure below, we find $R(7,2) = 9$ ways: enter image description here By the formula, with odd n, we have: $$ R(n,d)=\frac1{2n}\left(\sum_{k\mid\gcd(n,d)}\phi(k)\binom{\frac12\frac nk(n-3)}{\frac dk}+n\left[\frac{n-3}2,\frac{(n-1)(n-3)}4\atop d\right]\right) $$ $$ R(7,2)=\frac1{14}\left(\sum_{k\mid 1}\phi(1)\binom{\frac12\frac 71(7-3)}{\frac 21}+7\left[\frac{7-3}2,\frac{(7-1)(7-3)}4\atop 2\right]\right) $$ So, $$ R(7,2)=\frac1{14}\left(1\binom{14}{2}+7\sum_{j=0}^{\left\lfloor\frac 22\right\rfloor}\binom2{2-2j}\binom6j\right) $$ $$ =\frac{1}{14}\left(1\cdot\binom{14}{2}+7\cdot\left(\binom22\binom60+\binom20\binom61\right)\right) = 10 $$ The doubt: $R(7,2) = 10$ or $9$? Did I misinterpret the formula? Is there another way that I am not seeing in the illustration above? Or is the formula not correct? What's wrong?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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