En matemática combinatoria , el polinomio de collar , o la función de conteo de collar de Moreau, introducida por C. Moreau ( 1872 ), cuenta el número de collares distintos de n cuentas de colores elegidos entre α colores disponibles. Se supone que los collares son aperiódicos (no constan de subsecuencias repetidas) y el recuento se realiza "sin voltear" (sin invertir el orden de las cuentas). Esta función de conteo describe, entre otras cosas, el número de álgebras de Lie libres y el número de polinomios irreducibles en un campo finito.
Definición
Los polinomios del collar son una familia de polinomios. en la variable tal que
Por inversión de Möbius están dados por
dónde es la función clásica de Möbius .
Una familia estrechamente relacionada, llamada polinomio general de collares o función general de conteo de collares , es:
dónde es la función totient de Euler .
Aplicaciones
Los polinomios del collar aparece como:
- El número de collares aperiódicos (o equivalentemente palabras de Lyndon ) que se pueden hacer colocando n cuentas de colores que tengan α colores disponibles. Dos de estos collares se consideran iguales si están relacionados por una rotación (pero no un reflejo). Aperiódico se refiere a collares sin simetría rotacional, que tienen n rotaciones distintas. Los polinomiosIndique el número de collares incluidos los periódicos: esto se calcula fácilmente utilizando la teoría de Pólya .
- La dimensión de la pieza de grado n del álgebra de Lie libre en generadores α ("fórmula de Witt" [1] ). Aquídebe ser la dimensión de la pieza de grado n del álgebra de Jordan libre correspondiente .
- El número de palabras distintas de longitud n en un conjunto Hall . Tenga en cuenta que el conjunto de Hall proporciona una base explícita para un álgebra de Lie libre; por lo tanto, esta es la configuración generalizada para lo anterior.
- El número de polinomios mónicos irreducibles de grado n sobre un campo finito con elementos α (cuandoes un poder primordial). Aquí es el número de polinomios que son primarios (una potencia de un irreducible).
- El exponente en la identidad ciclotómica .
A pesar de que los polinomios aparecen en estos diversos entornos, las relaciones precisas entre estos siguen siendo misteriosas o desconocidas. Por ejemplo, no existe una biyección conocida entre los polinomios irreductibles y las palabras de Lyndon. [2]
Relaciones entre M y N
Los polinomios para M y N se relacionan fácilmente en términos de convolución de Dirichlet de funciones aritméticas, con respecto a como una constante.
- La fórmula para M da,
- La fórmula para N da.
- Su relación da o equivalente , ya que n es completamente multiplicativo .
Dos de estos implican el tercero, por ejemplo:
por cancelación en el álgebra de Dirichlet.
Ejemplos de
Para , comenzando con longitud cero, estos forman la secuencia entera
Identidades
Los polinomios obedecen a diversas identidades combinatorias, dadas por Metropolis & Rota:
donde "mcd" es el máximo común divisor y "mcm" es el mínimo común múltiplo . Más generalmente,
lo que también implica:
Identidad ciclotómica
Referencias
- ^ Lothaire, M. (1997). Combinatoria de palabras . Enciclopedia de las matemáticas y sus aplicaciones. 17 . Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, JE; Pirillo, G .; Foata, D .; Sakarovitch, J .; Simon, I .; Schützenberger, diputado; Choffrut, C .; Cori, R .; Lyndon, Roger; Rota, Gian-Carlo. Prólogo de Roger Lyndon (2ª ed.). Prensa de la Universidad de Cambridge . págs. 79, 84. ISBN 978-0-521-59924-5. Señor 1475463 . Zbl 0874.20040 .
- ^ Amy Glen, (2012) Combinatoria de palabras de Lyndon , charla de Melbourne
- Moreau, C. (1872), "Sur les permutations circulaires distinctes (Sobre distintas permutaciones circulares)" , Nouvelles Annales de Mathématiques , Série 2 (en francés), 11 : 309–31, JFM 04.0086.01
- Metropolis, N .; Rota, Gian-Carlo (1983), "Los vectores de Witt y el álgebra de los collares", Advances in Mathematics , 50 (2): 95-125, doi : 10.1016 / 0001-8708 (83) 90035-X , ISSN 0001-8708 , MR 0723197 , Zbl 0.545,05009
- Reutenauer, Christophe (1988). "Mots circulaires et polinomias irreductibles". Ana. Carolina del Sur. Matemáticas. Quebec . 12 (2): 275-285.