Necklace polynomial

In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by C. Moreau (1872), is the family of polynomials in the variable such that

By Möbius inversion they are given by

where is the classic Möbius function.

A closely related family, called the general necklace polynomial or general necklace-counting function, is:

where is Euler's totient function.

Relations between M and N

The above formulas are easily related in terms of Dirichlet convolution of arithmetic functions , regarding as a constant.

  • The formula for M gives ,
  • The formula for N gives .
  • Their relation gives or equivalently , since n is completely multiplicative.

Any two of these imply the third, for example:

by cancellation in the Dirichlet algebra.

Examples

Identities

The polynomials obey various combinatorial identities, given by Metropolis & Rota:

where "gcd" is greatest common divisor and "lcm" is least common multiple. More generally,

which also implies:

Cyclotomic identity

Applications

The necklace polynomials appear as:

  • The number of aperiodic necklaces (or equivalently Lyndon words) which can be made by arranging n colored beads having α available colors. Two such necklaces are considered equal if they are related by a rotation (but not a reflection). Aperiodic refers to necklaces without rotational symmetry, having n distinct rotations. The polynomials give the number of necklaces including the periodic ones: this is easily computed using Pólya theory.
  • The dimension of the degree n piece of the free Lie algebra on α generators ("Witt's formula"[1]). Here should be the dimension of the degree n piece of the corresponding free Jordan algebra.
  • The number of monic irreducible polynomials of degree n over a finite field with α elements (when is a prime power). Here is the number of polynomials which are primary (a power of an irreducible).
  • The exponent in the cyclotomic identity.
gollark: > <@!258639553357676545>> If you really want a good example, how about the JS you run when you access this site? How about the JS that is run when accessing other sites? A lot of them could use static or server side dynamically generated pages as opposed to JS.<@474726021652807680> A lot of time that's for development convenience as opposed to anything else. Or so it can actually respond in reasonable time to input and stuff.
gollark: DRM is inherently broken, it'll always run into this if people are dedicated enough.
gollark: https://en.wikipedia.org/wiki/AACS_encryption_key_controversy
gollark: Like the AACS master key thing a while ago.
gollark: Encryption keys of some sort for DRM? Those are subject to some bits of the DMCA IIRC.

References

  1. Lothaire, M. (1997). Combinatorics on words. Encyclopedia of Mathematics and Its Applications. 17. Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.). Cambridge University Press. pp. 79, 84. ISBN 978-0-521-59924-5. MR 1475463. Zbl 0874.20040.
  • Reutenauer, Christophe (1988). "Mots circulaires et polynomies irreductibles". Ann. Sc. Math. Quebec. 12 (2): 275–285.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.