Colorear los lados de un polígono

Question

De cuántas maneras podemos colorear los lados de un $n$ -¿agón con dos colores? (¡la rotación es indistinguible!)

Answer 1

Depende del $n$ -gon. Si se trata de un $n$ -gon, es el número de collares binarios de longitud $n$ . Esto es Secuencia OEIS A000031 ; véase también Wikipedia . Viene dado por

$$ \frac1n\sum_{d|n}\phi(d)2^{n/d}\;, $$

donde $\phi$ es Función totiente de Euler .

Answer 2

Podemos responder a las siguientes equivalente y la pregunta más general: ¿cuántos collares con $n$ perlas pueden ser formados a partir de un suministro ilimitado de $k$ distintas cuentas? Aquí, dos collares son considerados de la misma manera si uno se puede transformar en el otro por el cambio de cuentas de forma circular. Para formalizar esto, definir una cadena $S=s_1s_2\ldots s_n$, y definir una operación $f$ $S$ que se asigna a $s_i\mapsto s_{i+1}$ donde $s_n\mapsto s_1$. A continuación, se define el periodo de tiempo de una cadena de $S$ a ser el número mínimo $x$ tal que $$\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)$.

Nota: $(f*g)(n)=\sum_{d|n}f(d)g(n/d)$ denota Dirichlet de convolución.

Answer 3

El conjunto de potencia de $\{1,\dots,n\}$ consiste en $2^n$ elementos. Teniendo en cuenta $n$ rotaciones y dos simetrías, llegamos a la respuesta $$\frac {2^n} {2n}.$$