Collar (combinatoria)

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 n cadenas de 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 -ary , 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

${\displaystyle 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 es la función totiente de Euler . ^{[1] Cuando las cuentas están restringidas a} un conjunto múltiple de colores particular , ¿dónde está el número de cuentas de color ? ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {B}}=\{1^{n_{1}},\ldots ,k^{n_{k}}\}}$ ${\displaystyle n_{i}}$ ${\displaystyle i\in \{1,\ldots ,k\}}$

${\displaystyle 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 . ^[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 que actúa sobre el conjunto de todas las funciones . Si se deben utilizar todos los k colores, el recuento es ${\displaystyle {\mathcal {B}}}$ ${\displaystyle |{\mathcal {B}}|:=\sum \limits _{i=1}^{k}n_{i}}$ ${\displaystyle {m \choose m_{1},\ldots ,m_{k}}:={\frac {m!}{m_{1}!\cdots m_{k}!}}}$ ${\displaystyle C_{n}}$ ${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\}}$

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

¿Dónde están los números de Stirling de segunda especie ? ${\displaystyle S(n,k)}$

${\displaystyle N_{k}(n)}$(secuencia A054631 en la OEIS ) y (secuencia A087854 en la OEIS ) están relacionadas mediante los coeficientes binomiales : ${\displaystyle L_{k}(n)}$

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

y

${\displaystyle 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 (secuencia A081720 en el OEIS ) es

${\displaystyle 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 . ${\displaystyle D_{n}}$

Caso de cuentas distintas

Posibles patrones de pulseras de longitud n
correspondientes 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, esnorte !/norte= ( norte  − 1)!. ¡Esto se debe a que las cuentas se pueden ordenar linealmente en n ! formas, y los n cambios circulares de tal orden dan todos el mismo collar. De manera similar, el número de brazaletes distintos, contando los brazaletes girados y reflejados como iguales, es norte !/2 norte, para norte  ≥ 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

${\displaystyle 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: donde la suma es sobre todos los divisores de n , lo que es equivalente por inversión de Möbius a ${\textstyle N_{k}(n)=\sum _{d|n}M_{k}(d),}$ ${\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.

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

Referencias

1. Weisstein, Eric W. "Collar". MundoMatemático .
2. Ruskey, Frank (2006). "Información sobre collares, palabras de Lyndon, secuencias de De Bruijn". Archivado desde el original el 2 de octubre de 2006.

enlaces externos

• Polia, Georg; Leer, RC; Aeppli, Dorothee (1987). Enumeración combinatoria de grupos, gráficas y compuestos químicos . Springer-Verlag. ISBN 9780387964133.
• Ruskey, Frank; Salvaje, Carla; Wang, Terry Min Yih (1992). "Generando collares". Revista de algoritmos . 13 (3): 414–430. doi :10.1016/0196-6774(92)90047-G.