Coloring sides of a polygon In how many ways we can color the sides of a $n$-agon with two colors? 
(rotation is indistinguishable!)
 A: It depends on the $n$-gon. If it's a regular $n$-gon, this is the number of binary necklaces of length $n$. This is OEIS sequence A000031; see also Wikipedia. It is given by
$$
\frac1n\sum_{d|n}\phi(d)2^{n/d}\;,
$$
where $\phi$ is Euler's totient function.
A: We can answer the following equivalent and more general question: how many necklaces with $n$ beads can be formed from an unlimited supply of $k$ distinct beads? Here, two necklaces are considered the same if one can be transformed into the other by shifting beads circularly. To formalize this, define a string $S=s_1s_2\ldots s_n$, and define an operation $f$ on $S$ that maps $s_i\mapsto s_{i+1}$, where $s_n\mapsto s_1$. Then, we define the period of a string $S$ to be the minimal number $x$ such that $$\underbrace{f(f(f(\cdots f(S)\cdots )))}_{x \text{ times }} = S.$$ Convince yourself that $x|n$. Now, consider a string of length $n$ with period $d$. Each of the $d$ shifts of this string will yield the same necklace when the leading element is joined with the trailing element of the string, and this particular necklace can be constructed only by these $d$ strings. Thus, if $\text{Neck}(n)$ denotes the number of necklaces of length $n$, and $\text{Str}(d)$ denotes the number of strings with period $d$, we have $$\text{Neck}(n)=\sum_{d|n}\frac{\text{Str}(d)}{d}.$$ The number of strings of length $n$ is obviously $k^n$ since there are $k$ distinct beads to choose from. Note that we can express the number of strings of length $n$ in a different way, namely $\sum_{d|n}\text{Str}(d)$. Thus, $\text{Str}(d) = k^d * \mu$, by Möbius inversion, so we get $$\text{Neck}(n)=\sum_{d|n}\frac{1}{d}\sum_{d'|d}k^{d'}\mu\left(\frac{d}{d'}\right)=\frac{1}{n}\sum_{d|n}\varphi(d)k^{n/d},$$ where the last step follows by Möbius inversion on $n=\sum_{d|n}\varphi(n)$.
Note: $(f*g)(n)=\sum_{d|n}f(d)g(n/d)$ denotes Dirichlet convolution.
