En combinatoria , un collar k -ary de longitud n es una clase de equivalencia (una agrupación para la que existe una relación 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.
A k ary pulsera , también se refiere como un volumen de negocios (o libre ) de collar , es un collar de tal manera que las cuerdas pueden también ser equivalente en virtud de la 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 llamarse collar fijo para distinguirlo de un collar volteado.
Formalmente, se puede representar un collar como una órbita del grupo cíclico que actúa sobre cadenas de n caracteres, y una pulsera como una órbita del grupo diedro . Uno puede contar estas órbitas, y por lo tanto collares y brazaletes, usando el teorema de enumeración de Pólya .
Clases de equivalencia
Numero de collares
Existen
diferentes collares k -ary de longitud n , dondees la función totient de Euler . [1] Esto se sigue 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 . Tambien hay
diferentes collares de longitud n con exactamente k cuentas de diferentes colores, dondeson el número de Stirling del segundo tipo . (La variable k está sobrecargada y no está claro si k se refiere al tamaño del alfabeto o al número de elementos distintos en el collar).
(secuencia A054631 en la OEIS ) y(secuencia A087854 en el OEIS ) se relacionan mediante los coeficientes binomiales :
y
Numero de pulseras
Hay total
diferentes pulseras k -ary de longitud n , donde N k ( n ) es el número de collares k -ary de longitud n . Esto se sigue del método de Pólya aplicado a la acción del grupo diedro .
Estuche de cuentas distintas
Para un conjunto dado de n cuentas, todas distintas, el número de collares distintos hechos con estas cuentas, contando los collares rotados como iguales, esn !/norte= ( 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 el mismo collar. De manera similar, el número de brazaletes distintos, contando los brazaletes rotados y reflejados como los mismos, es n !/2 n, para n ≥ 3.
Si las cuentas no son todas distintas y tienen colores repetidos, entonces hay menos collares (y pulseras). Los polinomios de collar-contando anteriores dan los collares número a partir de todos los posibles conjuntos múltiples de perlas. El polinomio de inventario de patrones de Polya refina el polinomio de conteo, utilizando una variable para cada color de cuenta, de modo que el coeficiente de cada monomio cuente el número de collares en un conjunto múltiple de cuentas dado.
Collares aperiódicos
Un collar aperiódico de longitud n es una clase de equivalencia de rotación que tiene un 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 -ary 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 está sobre todos los divisores de n , que es equivalente por la inversión de Möbius a
Cada collar aperiódico contiene una sola palabra Lyndon de modo que las palabras Lyndon forman representantes de los collares aperiódicos.
Ver también
- Palabra Lyndon
- Inversión (matemáticas discretas)
- Problema del collar
- Problema de división del collar
- Permutación
- Pruebas del pequeño teorema de Fermat # Prueba contando collares
- Número Forte , una representación de brazaletes binarios de longitud 12 utilizados en música atonal .
Referencias
enlaces externos
- Weisstein, Eric W. "Collar" . MathWorld .
- Información sobre collares, palabras de Lyndon, secuencias de De Bruijn