Collar (combinatoria)

Las 3 pulseras con 3 cuentas rojas y 3 verdes. La del medio es quiral , por lo que hay 4 collares.
Compara el cuadro (6,9) en el triángulo.

Las 11 pulseras con 2 cuentas rojas, 2 amarillas y 2 verdes. La de más a la izquierda y las cuatro de más a la derecha son quirales, por lo que hay 16 collares.
Compara 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 denominada collar de vueltas (o libre ) , es un collar en el que las cuerdas también pueden ser equivalentes bajo reflexión. Es decir, dadas dos cuerdas, si cada una es el reverso de 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 de vueltas.

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 diedro . Se pueden contar estas órbitas, y por tanto los collares y las 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 totient de Euler . ^[1] Cuando las cuentas están restringidas a un multiconjunto de color particular , donde es el número de cuentas de color , hay ${\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 con 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 del segundo tipo ? ${\displaystyle S(n,k)}$

${\displaystyle N_{k}(n)}$(secuencia A054631 en la OEIS ) y (secuencia A087854 en la OEIS ) están relacionadas a través de 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 diferentes pulseras k -arias de longitud n (secuencia A081720 en la 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 deduce del método de Pólya aplicado a la acción del grupo diedro . ${\displaystyle D_{n}}$

Estuche de cuentas distintas

Posibles patrones de pulseras de longitud n
correspondientes a la partición entera k - ésima ( establecer particiones hasta rotación y reflexión)

Para un conjunto dado de n cuentas, todas distintas, el número de collares distintos hechos a partir de estas cuentas, contando los collares rotados como iguales, es¡no !/norte⁠ = ( n  − 1)!. Esto se debe a que las cuentas se pueden ordenar linealmente de n ! maneras, y los n desplazamientos circulares de tal ordenamiento dan como resultado el mismo collar. De manera similar, la cantidad de pulseras distintas, contando las pulseras rotadas y reflejadas como iguales, es ⁠¡no !/2 n⁠ , para n  ≥ 3.

Si las cuentas no son todas distintas, es decir, tienen colores repetidos, entonces hay menos collares (y pulseras). Los polinomios de conteo de collares anteriores dan la cantidad de collares hechos a partir de todos los posibles multiconjuntos de cuentas. 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 la cantidad de collares en un multiconjunto 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 , 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 sola palabra de Lyndon, de modo que las palabras de Lyndon forman representantes de collares aperiódicos.

Véase también

• Palabra de Lyndon
• Inversión (matemáticas discretas)
• Problema del collar
• Problema de rotura del collar
• Permutación
• Pruebas del pequeño teorema de Fermat#Prueba 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". MathWorld .
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

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