3

I stumbled upon entry OEIS-A208535 on the enumeration of certain kinds of colored necklaces and noticed that the integers for the odd prime rows of the table there seem to be given by the Moreau necklace polynomials

$$a(p,n)=\frac{n^p-n}{p}.$$

(This is reminiscent of the cyclotomic polynomials, $\Phi_p(x)=\frac{x^p-1}{x-1}$ for the prime indices, and indeed they are related.)

The primes and colored necklaces are both well plumbed but vast waters, so maybe formulas for the non-prime rows are well-known to number theorists / combinatorialists, but it's hard to track them down. Familiar to anyone? Any references?

Tom Copeland
  • 9,937
  • http://oeis.org/A001037 is another related sequence, although a – Dima Pasechnik Oct 23 '14 at 08:38
  • although I don't see an immediate connection. – Dima Pasechnik Oct 23 '14 at 08:38
  • @Dima, the Mobius and totient functions pop up in many sequences in the OEIS, especially those concerning necklaces, Lyndon words, and other similar permutation problems (see A051168, draft edits, another example where the simplicity of the rows matches that of the index/degree for the cyclotomic polynoms with prime indices). Check the cyclotomic identity on Wikipedia to see a relation between the Mobius and the free Lie algebra and compare A001037 with A059966. Thanks, interesting relation to another question of mine, maybe. – Tom Copeland Oct 23 '14 at 23:56
  • A059966 features a reference to a paper by me, and in fact I am well-aware of this relation. :-) – Dima Pasechnik Oct 24 '14 at 08:43
  • Ahh, I see--I usually don't look closely at references that aren't linked. Why don't you link to it? And good hunting for more connections on the OEIS. – Tom Copeland Oct 24 '14 at 08:53

1 Answers1

7

By Burnside's lemma applied to the cyclic group of order $m$, the number of $m$-bead necklaces colored in $n$ colors in which adjacent bead have different colors, which is what A208535 counts, is $$\frac{1}{m}\sum _{d|m} P_d(n) \phi(m/d),$$ where $\phi$ is Euler's totient function and $P_d(n)=(n-1)^d +(-1)^d (n-1)\ \ $ is the chromatic polynomial of a $d$-cycle for $d\ge2$, where for $d=2\ $ we interpret a 2-cycle as the connected graph on two vertices, and $P_1(n)=0$.

If $m$ is an odd prime, this is $$\frac{1}{m} P_m(n) = \frac{1}m\left((n-1)^m - (n-1)\right).$$

Since $\sum_{d|m} \phi(m/d)=m\ $ and $\sum_{d|m}(-1)^d \phi(m/d) = 0\ $ for $m$ even, the sum can be simplified to $$\frac{1}{m}\sum _{d|m} (n-1)^d \phi(m/d)\tag{$*$}$$ for $m\ $ even and $$\frac{1}{m}\sum _{d|m} (n-1)^d \phi(m/d) -(n-1)$$ for $m\ $ odd.

Note that $(*)$ is the number of $m$-bead necklaces colored in $n-1$ colors (with no restrictions on adjacent beads).

Ira Gessel
  • 16,246
  • Very neat. These little arithmetics are like hummingbirds to me--they don't visit my garden often, but when they do, I'm enchanted. – Tom Copeland Oct 21 '14 at 22:18
  • Yep. Thanks. For me, it's important to note that the totient gives the degree of the cyclotomic polynomials and that's why I was able to notice the regularity for the prime rows in analogy with that of the cyclotomic polynoms. – Tom Copeland Oct 22 '14 at 01:01