From mschoene@math.rwth-aachen.de Wed Dec 7 16:31:35 1994
Return-Path:
Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05994; Wed, 7 Dec 94 16:31:35 EST
Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp
(Smail3.1.28.1 #11) id m0rFSHJ-000MPOC; Wed, 7 Dec 94 20:43 MET
Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19)
id m0rFSHJ-0000PsC; Wed, 7 Dec 94 20:43 PST
Message-Id:
Date: Wed, 7 Dec 94 20:43 PST
From: "Martin Schoenert"
To: cube-lovers@life.ai.mit.edu
Subject: A lemma that is *not* Burnside's
Dan Hoey writes his e-mail message of 1994/11/04
In January of this year, Jerry Bryan and I wrote of counting the
number of M-conjugacy classes of Rubik's cube. In the sense that (for
instance) there is really only one position 1 QT from start, even
though that QT may be applied in twelve different ways, this task
amounts to counting the true number of positions of the cube. The
earlier discussion centered on calculations involving computer
analysis of large numbers of positions. However, a look in Paul B.
Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside
theorem is a tool that allows us to perform this calculation by hand.
The lemma used is indeed often referred to as ``Burnside's lemma'',
or if used to count combinatorical objects as ``Polya-Burnside lemma''.
However Peter M. Neumann in his paper ``A lemma that is not Burnside's''
(1979) pointed out that this lemma was known long befor Burnside
rediscovered it.
The first appearance seems to be Cauchy's work ``Memoire sur diverses
proprietes remarquables des substitutions regulieres ou irregulieres, et
des systemes de substitutiones conjugees (suite)'' of 1845.
But it appears in a rather obscure form.
It appears in more explicit form in Frobenius' paper ``"Uber die
Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul''
in 1887.
This is well befor Burnside's paper ``On some properties of groups of
odd order'' in 1900.
Polya refined it in his paper ``Kombinatorische Anzahlbestimmungen f"ur
Gruppen, Graphen und chemische Verbindungen'' in 1937, for use in the
part of combinatorics which deals with counting problems.
Peter M. Neumann thus proposed to call this lemma ``Cauchy-Frobenius
lemma''. But this was somehow not accepted, and it is now usually called
``A lemma that is not Burnside's''.
Have a nice day.
Martin.
-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .-
Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany