Permutations and Necklaces

Barry Dayton
Northeastern Illinois University


Here is an elementary exposition of permutation groups written for my Modern Algebra for Elementary Teachers course Summer 2002. Features include Lagrange's theorem for permutations, which gives a more concrete view of this theorem, a short elementary pr oof of Burnside's theorem and a discussion of conjugation. The use of "dynamic arrow diagrams" simplifies much and makes the discussion more concrete. The application of Burnside's theorem is to necklaces with symmetries in the dihedral group.

Download or view (PDF file 220 KB)
(Note: you should be able to view this OK on your Adobe Acrobat Reader but some printers may make a mess.)

Ghosts and Necklaces


The classical Newton's Identities allow one to go back and forth between the standard representation of a polynomial and the sequence of kth power sums of the roots (for negative k). This can be interpreted as a logarithm taking products to sums, especially if one restricts to polynomials (or formal power series) with constant term 1. This can be axiomatized by the notion of Witt vectors and the resulting logarithm is called the ghost map. There is a similar logarithm construction from the Grothendieck - Burnside ring and it has been noted by A.W.M Dress and C. Sibeneicher that this factors through the ghost map. The application is to the counting of necklaces. The observation that there is a connection between Witt vectors and classical formulas on necklaces was originally made by C. Metropolis and G-C. Rota in their 1983 Advances in Math. paper. However it was their point of view that one could use the classical combinatorics to derive the operations on Witt vectors. The point of view of this expository paper is that the construction of Witt vectors is relativity easy and one can then give very elegant proofs of the classical results on necklaces. This paper was written in January 1994 and has not been published. The original is available includes a historical perspective, a shorted 1997 version goes directly to the combinatorics.

Original longer version (111 KB)

Shorter version (79 KB)

Barry Dayton reserves all intellectual property rights to these papers, permission is given for non-commercial use.