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.

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.

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.

Hay diferentes collares k -arios de longitud n, donde

es la función totiente de Euler.

[1]​ Cuando las cuentas están restringidas a un conjunto múltiple de colores en particular

, hay diferentes collares hechos de todas las cuentas de

Estas dos fórmulas se derivan directamente del teorema de enumeración de Pólya aplicado a la acción del grupo cíclico.

actuando sobre el conjunto de todas las funciones

Si se deben utilizar todos los k colores, el recuento es dónde

(sucesión A054631 en OEIS) y

(sucesión A087854 en OEIS) se relacionan mediante los coeficientes binomiales: y El número de pulseras k-arias diferentes de longitud n (sucesión A081720 en OEIS) es donde Nk(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

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).

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 diferentes collares aperiódicos k -arios de longitud n, donde μ es la función de Möbius.

donde la suma es sobre todos los divisores de n, lo que es equivalente por inversión de Möbius a

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