Collar (combinatoria)

En combinatoria, un collar k-ario de longitud n es una clase de equivalencia de cadenas de n caracteres sobre un alfabeto de tamaño k, tomando todas las rotaciones como equivalentes. Representa una estructura con n cuentas conectadas circularmente que tienen k colores disponibles.

Las 3 pulseras con 3 cuentas rojas y 3 verdes. El del medio es quiral, por lo que son 4 collares.
Compare el cuadro (6,9) en el triángulo.

Las 11 pulseras con 2 cuentas rojas, 2 amarillas y 2 verdes. El que está más a la izquierda y los cuatro que están más a la derecha son quirales, por lo que hay 16 collares.
Compare el cuadro (6,7) en el triángulo.

16 fichas del juego Tantrix, correspondientes a los 16 collares con 2 cuentas rojas, 2 amarillas y 2 verdes.

Una pulsera k-aria, también conocida como collar de rotación (o libre), es un collar en el que las cuerdas también pueden ser equivalentes bajo reflexión. Es decir, dadas dos cadenas, si cada una es inversa a la otra, pertenecen a la misma clase de equivalencia. Por esta razón, un collar también podría denominarse collar fijo para distinguirlo de un collar giratorio.

Formalmente, se puede representar un collar como una órbita del grupo cíclico que actúa sobre cadenas de n caracteres sobre un alfabeto de tamaño k, y una pulsera como una órbita del grupo diédrico. Se pueden contar estas órbitas y, por tanto, collares y pulseras, utilizando el teorema de enumeración de Pólya.

Clases de equivalencia

Número de collares

Hay

$N_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{n/d}={\frac {1}{n}}\sum _{i=1}^{n}k^{\,{\rm {gcd}}(i,n)}$

diferentes collares k -arios de longitud n, donde $\varphi$ es la función totiente de Euler. ​ Cuando las cuentas están restringidas a un conjunto múltiple de colores en particular ${\mathcal {B}}=\{1^{n_{1}},\ldots ,k^{n_{k}}\}$, dónde $n_{i}$ es el número de cuentas de color $i\in \{1,\ldots ,k\}$, hay

$N({\mathcal {B}})={\frac {1}{|{\mathcal {B}}|}}\sum _{d|{\rm {gcd}}(n_{1},\ldots ,n_{k})}{|{\mathcal {B}}|/d \choose n_{1}/d,\ldots ,n_{k}/d}\phi (d)$

diferentes collares hechos de todas las cuentas de ${\mathcal {B}}$. ​ Aquí $|{\mathcal {B}}|:=\sum \limits _{i=1}^{k}n_{i}$ y ${m \choose m_{1},\ldots ,m_{k}}:={\frac {m!}{m_{1}!\cdots m_{k}!}}$ es el coeficiente multinomial. Estas dos fórmulas se derivan directamente del teorema de enumeración de Pólya aplicado a la acción del grupo cíclico. $C_{n}$ actuando sobre el conjunto de todas las funciones $f:\{1,\ldots ,n\}\to \{1,\ldots ,k\}$ . Si se deben utilizar todos los k colores, el recuento es

$L_{k}(n)={\frac {k!}{n}}\sum _{d\mid n}\varphi (d)S\left({\frac {n}{d}},k\right)\;,$

dónde $S(n,k)$ son el número de Stirling de segunda especie.

$N_{k}(n)$ (sucesión A054631 en OEIS) y $L_{k}(n)$ (sucesión A087854 en OEIS) se relacionan mediante los coeficientes binomiales:

$N_{k}(n)=\sum _{j=1}^{k}{\binom {k}{j}}L_{j}(n)$

y

$L_{k}(n)=\sum _{j=1}^{k}(-1)^{k-j}{\binom {k}{j}}N_{j}(n)$

Número de pulseras

El número de pulseras k-arias diferentes de longitud n (sucesión A081720 en OEIS) es

$B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1)k^{n/2}&{\text{if }}n{\text{ is even}}\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{(n+1)/2}&{\text{if }}n{\text{ is odd}}\end{cases}}\quad ,$

donde N_k(n) es el número de collares k -arios de longitud n. Esto se desprende del método de Pólya aplicado a la acción del grupo diédrico $D_{n}$.

Caso de cuentas distintas

Posibles patrones de pulseras de longitud n.
correspondiente a la k-ésima partición entera
(establecer particiones hasta rotación y reflexión)

Para un conjunto dado de n cuentas, todas distintas, el número de collares distintos hechos con estas cuentas, contando los collares girados como iguales, es / n!n = (n−1)!. ¡Esto se debe a que las cuentas se pueden ordenar linealmente en n! formas, y los n cambios circulares de tal orden dan todo el mismo collar. De manera similar, el número de brazaletes distintos, contando los brazaletes girados y reflejados como iguales, es n!2n, para n≥3.

Si las cuentas no son todas distintas y tienen colores repetidos, entonces hay menos collares (y pulseras). Los polinomios de conteo de collares anteriores dan el número de collares hechos de todos los conjuntos múltiples posibles de cuentas. El polinomio de inventario de patrones de Polya refina el polinomio de conteo, usando variables para cada color de cuentas, de modo que el coeficiente de cada monomio cuente el número de collares en un conjunto múltiple de cuentas determinado.

Collares aperiódicos

Un collar aperiódico de longitud n es una clase de equivalencia de rotación que tiene tamaño n, es decir, no hay dos rotaciones distintas de un collar de dicha clase que sean iguales.

Según la función de conteo de collares de Moreau, hay

$M_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)k^{n/d}$

diferentes collares aperiódicos k -arios de longitud n, donde μ es la función de Möbius. Las dos funciones de conteo de collares están relacionadas por: ${\textstyle N_{k}(n)=\sum _{d|n}M_{k}(d),}$ donde la suma es sobre todos los divisores de n, lo que es equivalente por inversión de Möbius a ${\textstyle M_{k}(n)=\sum _{d|n}N_{k}(d)\,\mu {\bigl (}{\tfrac {n}{d}}{\bigr )}.}$

Cada collar aperiódico contiene una única palabra Lyndon, de modo que las palabras Lyndon forman representantes de collares aperiódicos.

Véase también

• Palabra lyndon
• Inversión (matemáticas discretas)
• Problema con el collar
• Problema de división del collar
• Permutación
• Demostraciones del pequeño teorema de Fermat#Demostración contando collares
• Número fuerte, representación de pulseras binarias de longitud 12 utilizadas en la música atonal.

Enlaces externos

• Polya, Georg; Read, R.C.; Aeppli, Dorothee (1987). Combinatorial enumeration of groups, graphs, and chemical compounds. Springer-Verlag. ISBN 9780387964133. 
• Ruskey, Frank; Savage, Carla; Wang, Terry Min Yih (1992). «Generating necklaces». Journal of Algorithms 13 (3): 414-430. doi:10.1016/0196-6774(92)90047-G. 

• Datos: Q2983383
• Multimedia: Necklace (combinatorics) / Q2983383