Collar (combinatoria)

En combinatoria , un collar de longitud de color es una clase de equivalencia de cadenas de caracteres sobre un alfabeto de tamaño , donde las cadenas obtenidas entre sí por una rotación o un cambio cíclico se consideran equivalentes. Por ejemplo, para , el collar será el conjunto . El collar se puede representar visualmente como una estructura de cuentas conectadas en un anillo, que tiene colores posibles (los colores corresponden a los símbolos del alfabeto): para hacer esto, debe tomar una de las palabras de esta clase de equivalencia, enhebrar mentalmente un hilo a través de sus símbolos y conecta su principio y fin. $k$ $norte$ $norte$ $k$ $n=5$ $k=3$ $\{ababc,babca,abcab,bcaba,cabab\}$ $norte$ $k$

$k$ Una pulsera de color de longitud , que se conoce como un collar reversible (o libre ) , se define de manera similar como la clase de equivalencia de cadenas de longitud en el alfabeto de caracteres, sin embargo, en este caso, cadenas obtenidas entre sí por rotación, la simetría especular o una combinación de estas transformaciones se consideran equivalentes. Si se recurre a la representación visual de pulseras en forma de cuentas, su diferencia con los collares será que está prohibido dar la vuelta a los collares, pero sí a las pulseras. Por este motivo, a un collar también se le puede llamar collar fijo . Por ejemplo, el collar correspondiente a la cuerda es diferente del collar correspondiente a la cuerda , pero de estas dos cuerdas se obtiene el mismo brazalete (después de todo, estas dos cuerdas se obtienen una de la otra por simetría especular). $norte$ $norte$ $k$ $ababc$ $cbaba$

Desde el punto de vista del álgebra, el collar puede representarse como la órbita del grupo cíclico de acción sobre cadenas de caracteres -, y el brazalete como la órbita del grupo diédrico . Uno puede contar estas órbitas, y por lo tanto el número de tales collares y pulseras, utilizando el teorema de enumeración de Poya . $norte$

Clases de equivalencia

Número de collares

Disponible

N_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{\frac {n}{d}}

collares de diferentes colores de longitud , donde es la función de Euler [1] [2] . Esto se deriva directamente del teorema de enumeración de Polya , aplicado a la acción de un grupo cíclico que actúa sobre el conjunto de todas las funciones . $k$ $norte$ $\varphi$ $C_{n}$ ${\displaystyle f:\{1,\ldots,n\}\to \{1,\ldots,k\))$

Número de pulseras

Sí [3] [4]

B_{k}(n)={\begin{casos}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1) k^{\frac {n}{2}}&n\equiv 0{\pmod {2}},\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{\frac {n+1}{2}}&n\equiv 1{\pmod {2}}\end{casos}}

diferentes pulseras de k colores de longitud n , donde es igual al número de collares de k colores de longitud n . Esto se sigue del método de Poya aplicado a la acción del grupo diédrico . ${\ estilo de visualización N_ {k} (n)}$ $D_{n}$

Estuche de diferentes cuentas

Para un conjunto dado de n cuentas (diferentes), el número de collares distintos hechos con estas cuentas, suponiendo que los collares rotados sean iguales, es n !norte= ( norte − 1)!. Esto se deduce del hecho de que las cuentas pueden disponerse linealmente n ! formas y n desplazamientos cíclicos de cada uno de esos órdenes lineales dan el mismo collar. De manera similar, el número de pulseras diferentes, suponiendo que las rotaciones y reflexiones sean las mismas, es n !2n_ _ para _ $n\geqslant 3$

Si las cuentas no son diferentes, es decir, hay una repetición de colores, entonces la cantidad de collares (y pulseras) será menor. Los polinomios de conteo de collares anteriores dan el número de collares hechos de todos los conjuntos posibles de cuentas. El polinomio de enumeración de configuración de Poya mejora el polinomio de conteo con una variable para cada color de cuenta, de modo que el coeficiente de cada monomio contará el número de collares en un determinado conjunto de cuentas.

Collares aperiódicos

Un collar aperiódico de longitud n es una clase de equivalencia de rotaciones de tamaño n , es decir, no hay dos rotaciones diferentes del collar de esta clase que sean equivalentes.

De acuerdo con la función de conteo de collares de Moro , hay

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

diferentes collares aperídicos de color k 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 a la inversión de Möbius para $\mu$ $N_{k}(n)\ =\ \sum \nolimits _{d|n}M_{k}(d),$ $M_{k}(n)\ =\ \sum \nolimits _{d|n}N_{k}(d)\,\mu ({\tfrac {n}{d))).$

Cualquier collar aperiódico contiene una palabra Lindon , por lo que las palabras de Lindon forman representantes de collares aperiódicos.

Véase también

La palabra de Lindon
Inversión (Matemáticas Discretas)
Problema de restauración de cuentas
Problema de corte de collar
permutación
Demostración del pequeño teorema de Fermat

Notas

↑ Weisstein, Eric W. Collar en el sitio web de Wolfram MathWorld .
↑ Himach, Filipenko, 2016 , pág. 93.
↑ Yakovenko, 1998 .
↑ Himach, Filipenko, 2016 , pág. 94-95.

Literatura

Khimach R.A., Filipenko A.A. Foro científico juvenil: Ciencias técnicas y matemáticas: electr. Se sentó. Arte. por estera XXXIV Pasante. semental. científico-práctico. conferencia Nº 5(34). . - 2016. - S. 90-98 .

Kaluzhin L.A., Sushchansky V.I. 13. Problemas combinatorios // Transformaciones y permutaciones. - M. : "Nauka", 1985. - (Problemas de la ciencia y el progreso técnico).
Yakovenko D. I. Problema sobre collares // Boletín de la Universidad de Omsk. - 1998. - S. 21-24 .

Enlaces

Weisstein, Eric W. Necklace (inglés) en el sitio web de Wolfram MathWorld .
Información sobre collares, palabras de Lyndon, secuencias de De Bruijn