3
$\begingroup$

Suppose $P_n$ is the regular polygon with n vertices ($n\geq 5$). Let $V=\{v_1,\ldots,v_n\}$ be the vertex set. I would like to define a labeling function $\ell:V\to \{0,1\}$ so that $\sum_{i=1}^{n}\ell(v_i)$ is even and $\geq 4$. This means that a labeling assigns a 0 or a 1 to each vertex and that this must be done so the number of 1's is even and is at least 4.

Two such labelings are equivalent if there is a automorphism of $P_n$ that sends one labeling to the other. How many equivalence classes of such labelings are there are on $P_n$?

$\endgroup$
  • 1
    $\begingroup$ Do you mean $\{0, 1\}^{*}$ as the codomain? Or are you assigning vertices only ones and zeros? Can you give an example? A regular polygon is a cycle, which has $2n$ automorphisms, defined by the Dihedral group $D_{2n}$. Maybe I'm misunderstanding your question, so would like to clarify. $\endgroup$ – ml0105 Apr 24 '14 at 16:59
  • 2
    $\begingroup$ Polya enumeration should be useful - this is equivalent to the number of bracelets with $n$ beads of two colors so that one of the colors appears at least 4 times. I'm not certain there is an exact formula for this, since the number of colorings should depend on the factorization of $n$. $\endgroup$ – Perry Elliott-Iverson Apr 24 '14 at 18:03
  • $\begingroup$ @ml0105 The pentagon only admits 1 such labeling (4 vertices are 1 and 1 is 0). Written cyclically a hexagon admits 4: (1,1,1,1,1,1), (0,0,1,1,1,1), (0,1,0,1,1,1), and (0,1,1,0,1,1). Up to rotation and reflection these are the only ones. As you mention, $D_{2n}$ acts on the set $X$ of all labelings where there are at least 4 1's so I guess I am asking for $|X/D_{2n}|$. For general graphs this question would be pretty intractable but since it is for polygons and $D_{2n}$ is not too complicated, there should be a decent answer. $\endgroup$ – J.K.T. Apr 24 '14 at 18:39
  • $\begingroup$ So, have you taken the suggestion of @Perry and looked at Polya enumeration? $\endgroup$ – Gerry Myerson Apr 25 '14 at 0:07
  • $\begingroup$ Yes, it looks like the number is $\frac{1}{2n}\sum_{g\in D_{2n}}2^{c(g)}$ where $c(g)$ is the number of cycles of $g$ as a permutation of $X$. I'm not exactly sure what this last part about $c(g)$ means. $\endgroup$ – J.K.T. Apr 25 '14 at 0:32
6
$\begingroup$

What you would want to do is find the Polya inventory polynomial in two colors for the Dihedral group $D_{n}$. Begin with the cycle index of $D_{n}$, $Z(D_{n})$:

$$Z(D_{n}) = \frac{1}{2n} \sum_{d|n} \phi(d) a_d^{n/d} + \left\{ \begin{array}{lr} \frac{1}{2}a_1 a_2^{(n-1)/2} &n \textrm{ odd}\\ \frac{1}{4}\left(a_2^{n/2} + a_1^2 a_2^{(n-2)/2}\right) &n \textrm{ even} \end{array}\right.$$

Where $\phi$ is Euler's phi function. Next replace $a_i$ by $(b^i + w^i)$ to get the Polya inventory polynomial:

$$P(b,w) = \frac{1}{2n} \sum_{d|n} \phi(d) (b^d + w^d)^{n/d} + \left\{ \begin{array}{lr} \frac{1}{2}(b+w)(b^2 + w^2)^{(n-1)/2} &n \textrm{ odd}\\ \frac{1}{4}\left((b^2 + w^2)^{n/2} + (b+w)^2 (b^2+w^2)^{(n-2)/2}\right) &n \textrm{ even} \end{array}\right.$$

The coefficient of $b^i w^j$ in this polynomial counts the number of distinct bracelets with $n$ beads, $i$ of which are black and $j$ of which are white. To relate this to your polygons, let the black beads be the ones labeled with 1, and the white beads labeled 0. Then summing the coefficients of each $b^i w^j$ in $P(b,w)$ with $i$ even and $i\geq 4$ will give you the number of such polygons that you are looking for.

As you can see this value depends on the factorization of $n$. You may be able to get some nice results for certain $n$. For example, if $n=p$, where $p$ is an odd prime, the polynomial will be:

$$\begin{array} \\ P(b,w) &= \frac{1}{2p}\left((b+w)^p + (p-1)(b^p + w^p)\right) + \frac{1}{2}(b+w)(b^2 + w^2)^{(p-1)/2} \\ &= \frac{1}{2p}\left(\sum_{i=0}^p \binom{p}{i}b^i w^{p-1} + (p-1)(b^p + w^p)\right) + \frac{1}{2}(b+w)\sum_{i=0}^{(p-1)/2} \binom{(p-1)/2}{i} b^{2i} w^{p-1+i} \\ \end{array}$$

Taking only coefficients of even powers of $b$ at least 4, we get that the number of labelings is:

$$\begin{array} \\ &= \frac{1}{2p}\sum_{i=2}^{\lfloor p/2 \rfloor} \binom{p}{2i} + \frac{1}{2}\sum_{i=2}^{(p-1)/2} \binom{(p-1)/2}{i} \\ &= \frac{1}{2p}\left(2^{p-1} - 1 - \frac{p(p-1)}{2}\right) + \frac{1}{2}\left(2^{(p-1)/2} - 1 - \frac{p-1}{2}\right) \\ &= \frac{1}{2p}\left(2^{p-1} - 1\right) - \frac{p-1}{4} + 2^{(p-3)/2} - \frac{1}{2} - \frac{p-1}{4} \\ &= \frac{1}{2p}\left(2^{p-1} - 1\right) + 2^{(p-3)/2} - \frac{p}{2} \end{array}$$

This is a nice quick intro to the topic of Polya enumeration if you're interested in more.

$\endgroup$
  • $\begingroup$ Wow, thanks so much! These polynomials are serious business. I am really surprised this depends on the factorization of n! Unfortunately, I am having a bit of trouble reproducing your calculation for $n=p$. $\endgroup$ – J.K.T. Apr 25 '14 at 17:18
  • $\begingroup$ For $n=p$ it is $P(b,w)=\frac{1}{2p}((p-1)(b+w)^p+(b^p+w^p))+\frac{1}{2}(b+w)(b^2+w^2)^{(p-1)/2}$. Do you just use the binomial theorem to pick out the coefficients of $b^iw^j$? $\endgroup$ – J.K.T. Apr 25 '14 at 17:22
  • $\begingroup$ That's right. I'll add some details. $\endgroup$ – Perry Elliott-Iverson Apr 25 '14 at 19:06
  • $\begingroup$ Thanks for the details. I see it all now except for one part. I hope you don't mind me asking one last thing: how do you get $2^{p-1}-1-\frac{p(p-1)}{2}$ from $\sum_{i=2}^{\lfloor p/2\rfloor}{{p}\choose{2i}}$? $\endgroup$ – J.K.T. Apr 25 '14 at 20:35
  • 1
    $\begingroup$ $\sum_{i=0}^{\lfloor n/2 \rfloor} \binom{n}{2i} = 2^{n-1}$ for any $n$, this is just the sum of the even-numbered binomial coefficients. See proofwiki.org/wiki/Sum_of_Even_Index_Binomial_Coefficients. We want $\sum_{i=2}^{\lfloor p/2 \rfloor} \binom{p}{2i} = 2^{p-1} - \binom{p}{0} - \binom{p}{2}$ $= 2^{p-1} - 1 - \frac{p(p-1)}{2}$. $\endgroup$ – Perry Elliott-Iverson Apr 25 '14 at 20:48

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.