Moreau's necklace-counting function
Michael J Hardy
N. Metropolis and G.-C. Rota, reprinted in the book
_Gian-Carlo_Rota_on_Combinatorics_, we find Moreau's
necklace-counting function
M(n,c) = (1/n) * SUM { mu(n/d) c^d : d divides n },
where mu is the classic Moebius function. It is stated that
this is the number of necklaces of n beads when each bead can
be of any of c colors. I think the paper gives a bijective
proof, which it says is more natural than earlier proofs, but
I haven't read that far yet.
Two questions:
(1) Metropolis & Rota attribute this result to "Colonel Moreau
of the French army," but the paper's bibliography lists no one
by that name, and the list of biographical sketches of mathematicians
at <http://www-gap.dcs.st-and.ac.uk/~history/Indexes/M.html>
lists no on by that name. Who was Moreau and on what grounds
can this be attributed this to him?
(2) I hope I'm being temporarily horribly stupid on this one.
Suppose four beads, chosen from among three colors. Then we have
1. All four red.
2. All four blue.
3. All four green.
4. 3 R, 1 G.
5. 3 R, 1 B.
6. 3 B, 1 G.
7. 3 B, 1 R.
8. 3 G, 1 R.
9. 3 G, 1 B.
10. 2 R, 2 G, identical colors adjacent.
11. 2 R, 2 G, identical colors opposite.
12 & 13. Like 10 & 11 above; 2 B.
14 & 15. Like 10 & 11 above; 2 G.
16. 2 R adjacent, 1 B, 1 G.
17. 2 R opposite, 1 B, 1 G.
18 & 19. Like 16 & 17 above, 2 B.
20 & 21. Like 16 & 17 above, 2 G.
In #16-21, I assumed it doesn't matter in which order the
singleton colors appear, since one can pick the necklace up
off the table and turn it over, reversing clockwise and
counterclockwise, and it's still the same necklace.
But Moreau's necklace-counting function gives
(1/4) * ( mu(4/1) 3^1 + mu(4/2) 3^2 + mu(4/4) 3^4)
= (1/4) * ( [0 * 3] + [-1 * 9] + [1 * 81] )
= 18 =/= 21.
Next I found via a Google search a working draft of a book
by Frank Ruskey of the University of Victoria in British
Columbia. I can't tell what the URL is since clicking on
it opens up a postscript viewer rather than a web browser.
One page 213 he says "... a necklace is an equivalence class
of strings under rotation ... [although] we expect to be able
to pick up a necklace and turn it over ... we stick with
mathematical tradition and regard 001101 as a different
necklace than 001011 ..." That makes my count of 21 too small.
But two pages later he gives that same formula, which seems to
lead to 18.
Please tell me I am stupidly missing something.
Mike Hardy
Michael J Hardy
> In _Witt_Vectors_and_the_Algebra_of_Necklaces_, by
> N. Metropolis and G.-C. Rota, reprinted in the book
> _Gian-Carlo_Rota_on_Combinatorics_, we find Moreau's
> necklace-counting function
>
> M(n,c) = (1/n) * SUM { mu(n/d) c^d : d divides n },
>
> where mu is the classic Moebius function. It is stated that
> this is the number of necklaces of n beads when each bead can
> be of any of c colors.
[ ..... ]
> (2) I hope I'm being temporarily horribly stupid on this one.
> Suppose four beads, chosen from among three colors. Then we have
[ ..... ]
> Please tell me I am stupidly missing something.
OK, I was right, in that I was wrong. What it says is
necklaces that are asymetric under rotations. That rules out
six of my 21 necklaces, and then we add three more because
(unnaturally, given the name necklace) we are forbidden to
pick the necklace up off the table and turn it over, and call
it the same necklace (unless it has that kind of symmetry),
so we have to add three more that are reflections of three
that I listed (the others are the same as their reflections).
Once all this is done, Moreau's formula gives the right
answer.
This still leaves my other question: who was Moreau and
what did he write about this? -- Mike Hardy
Mitch Harris
>
> This still leaves my other question: who was Moreau and
> what did he write about this? -- Mike Hardy
I only know what google tells me:
google for "moreau necklace counting" and get
http://www1.informatik.uni-erlangen.de/tree/Research/reports/rep91_5.ps
with the reference (for the necklace formula you gave):
C. Moreau. Sur les permutations circulaires distincts. Nouv. Ann. Math.,
11:309-314, 1872.
Mitch Harris
Dan Luecking
> Michael J Hardy (mjh...@mit.edu) wrote:
>
>> In _Witt_Vectors_and_the_Algebra_of_Necklaces_, by
>> N. Metropolis and G.-C. Rota, reprinted in the book
>> _Gian-Carlo_Rota_on_Combinatorics_, we find Moreau's
>> necklace-counting function
>>
>> M(n,c) = (1/n) * SUM { mu(n/d) c^d : d divides n },
>>
>
> This still leaves my other question: who was Moreau and
>what did he write about this? -- Mike Hardy
Googling for [Moreau necklace counting] I get a postscript file:
Cycle counting for isomorphism types of endofunctions
by Volker Strehl
Informatik I, Universitat Erlangen-Nurnberg, FRG
which includes the following reference:
C. Moreau, Sur les permutations circulaire distinct, Nouv. Ann. Math.,
11:309--311, 1872.
It also references the Metropolis-Rota paper.
There is also a Colonel Moreau mentioned prominantly on chess sites.
Apparently he hosted a tournament in Monte Carlo in 1903.
Dan
--
Dan Luecking Department of Mathematical Sciences
University of Arkansas Fayetteville, Arkansas 72701
luecking at uark dot edu
Michael J Hardy
> 11:309--311, 1872.
[ ..... ]
> There is also a Colonel Moreau mentioned prominantly on chess sites.
> Apparently he hosted a tournament in Monte Carlo in 1903.
Thank you, Dan Luecking and Mitch Harris.
Any idea whether the chess organizer and the mathematician
are the same person, and what his first name is? -- Mike Hardy