My lovely wife, Ildiko, woke up from a dream and asked: If you have a flower with 7 petals and two colors, how many ways can you color the petals of that flower?
Intriguing, isn’t it.
Such a flower shape obviously has rotational symmetry. Just because the flower is rotated by several times a seventh of a revolution, the resulting pattern should not be counted as distinct. So it is not simply calculating what number theorists call the \(n\)-tuple. It is something more subtle.
We can, of course, start counting the possibilities the brute force way. It’s not that difficult for a smaller number of petals, but it does get a little confusing at 6. At 7 petals, it is still something that can be done, but the use of paper-and-pencil is strongly recommended.
So what about the more general case? What if I have \(n\) petals and \(k\) colors?
Neither of us could easily deduce an answer, so I went to search the available online literature. For a while, other than finding some interesting posts about cyclic, or circular permutations, I was mostly unsuccessful. In fact, I began to wonder if this one was perhaps one of those embarrassing little problems in combinatorial mathematics that has no known solution and about which the literature remains strangely quiet.
But then I had another idea: By this time, we both calculated the sequence, 2, 3, 4, 6, 8, 14, 20, which is the number of ways flowers with 1, 2, …, 7 petals can be colored using only two colors. Surely, this sequence is known to Google?
Indeed it is. It turns out to be a well-known sequence in the online encyclopedia of integer sequences, A000031. Now I was getting somewhere! What was especially helpful is that the encyclopedia mentioned necklaces. So that’s what this problem set is called! Finding the Mathworld page on necklaces was now easy, along with the corresponding Wikipedia page. I also found an attempt, valiant though only half-successful if anyone is interested in my opinion, to explain the intuition behind this known result:
$$N_k(n)=\frac{1}{n}\sum_{d|n}\phi(d)k^{n/d},$$
where the summation is over all the divisors of \(n\), and \(\phi(d)\) is Euler’s totient function, the number of integers between \(1\) and \(d\) that are relative prime to \(d\).
Evil stuff if you asked me. Much as I always liked mathematics, number theory was not my favorite.
In the case of odd primes, such as the number 7 that occurred in Ildiko’s dream, and only two colors, there is, however, a simplified form:
$$N_2(n)=\frac{2^{n-1}-1}{n}+2^{(n-1)/2}+1.$$
Unfortunately, this form is for “free necklaces”, which treats mirror images as equivalent. For \(n<6\) it makes no difference, but substituting \(n=7\), we get 18, not 20.
Finally, a closely related sequence, A000029, characterizes necklaces that can be turned over, that is to say, the case where we do not count mirror images separately.
Oh, this was fun. It’s not like I didn’t have anything useful to do with my time, but it was nonetheless a delightful distraction. And a good thing to chat about while we were eating a wonderful lunch that Ildiko prepared today.