Ir al contenido

Collar (combinatoria)

De Wikipedia, la enciclopedia libre
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.

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

[editar]

Número de collares

[editar]

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 , dónde es el número de cuentas de color , hay

diferentes collares hechos de todas las cuentas de . [2]​ Aquí y 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. actuando sobre el conjunto de todas las funciones . Si se deben utilizar todos los k colores, el recuento es

dónde son el número de Stirling de segunda especie.

(sucesión A054631 en OEIS) y (sucesión A087854 en OEIS) se relacionan mediante los coeficientes binomiales:

y

Número de pulseras

[editar]

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 .

Caso de cuentas distintas

[editar]
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

[editar]

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. Las dos funciones de conteo de collares están relacionadas por: 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.

Véase también

[editar]

Referencias

[editar]
  1. Weisstein, Eric W. «Necklace». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  2. Ruskey, Frank (2006). «Info on necklaces, Lyndon words, De Bruijn sequences». Archivado desde el original el 2 de octubre de 2006. 

Enlaces externos

[editar]