3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ oeis.org/A001037 is another related sequence, although a $\endgroup$
    – Dima Pasechnik
    Commented Oct 23, 2014 at 8:38
  • $\begingroup$ although I don't see an immediate connection. $\endgroup$
    – Dima Pasechnik
    Commented Oct 23, 2014 at 8:38
  • $\begingroup$ @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. $\endgroup$
    – Tom Copeland
    Commented Oct 23, 2014 at 23:56
  • $\begingroup$ A059966 features a reference to a paper by me, and in fact I am well-aware of this relation. :-) $\endgroup$
    – Dima Pasechnik
    Commented Oct 24, 2014 at 8:43
  • $\begingroup$ 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. $\endgroup$
    – Tom Copeland
    Commented Oct 24, 2014 at 8:53

1 Answer 1

Reset to default
7
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very neat. These little arithmetics are like hummingbirds to me--they don't visit my garden often, but when they do, I'm enchanted. $\endgroup$
    – Tom Copeland
    Commented Oct 21, 2014 at 22:18
  • $\begingroup$ 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. $\endgroup$
    – Tom Copeland
    Commented Oct 22, 2014 at 1:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .