Jump to content

Necklace polynomial

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by ArnoldReinhold (talk | contribs) at 00:51, 9 June 2020 (Changing short description from "Number of arrangements on a necklace of n colored beads having α available colors" to "Counts arrangements on a necklace of n colored beads having α available colors" (Shortdesc helper)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

References

  1. ^ Lothaire, M. (1997). Combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 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.