![\"\"](\"https:\/\/spinor.info\/weblog\/wp-content\/uploads\/2020\/05\/petals.png\")
<\/p>\nMy 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?<\/p>\n
<\/p>\n
Intriguing, isn’t it.<\/p>\n
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.<\/p>\n
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.<\/p>\n
So what about the more general case? What if I have \\(n\\) petals and \\(k\\) colors?<\/p>\n
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<\/a> 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.<\/p>\n 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?<\/p>\n Indeed it is. It turns out to be a well-known sequence in the online encyclopedia of integer sequences, A000031<\/a>. 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<\/a> was now easy, along with the corresponding Wikipedia page<\/a>. I also found an attempt, valiant though only half-successful if anyone is interested in my opinion, to explain the intuition<\/a> behind this known result:<\/p>\n $$N_k(n)=\\frac{1}{n}\\sum_{d|n}\\phi(d)k^{n\/d},$$<\/p>\n where the summation is over all the divisors of \\(n\\), and \\(\\phi(d)\\) is Euler’s totient function<\/a>, the number of integers between \\(1\\) and \\(d\\) that are relative prime to \\(d\\).<\/p>\n Evil stuff if you asked me. Much as I always liked mathematics, number theory was not my favorite.<\/p>\n 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:<\/p>\n $$N_2(n)=\\frac{2^{n-1}-1}{n}+2^{(n-1)\/2}+1.$$<\/p>\n 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.<\/p>\n Finally, a closely related sequence, A000029<\/a>, characterizes necklaces that can be turned over, that is to say, the case where we do not count mirror images separately.<\/p>\n 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.<\/p>\n 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 […]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[30,35],"tags":[],"class_list":["post-9946","post","type-post","status-publish","format-standard","hentry","category-mathematics","category-personal","category-30-id","category-35-id","post-seq-1","post-parity-odd","meta-position-corners","fix"],"_links":{"self":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts\/9946","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=9946"}],"version-history":[{"count":10,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts\/9946\/revisions"}],"predecessor-version":[{"id":12362,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=\/wp\/v2\/posts\/9946\/revisions\/12362"}],"wp:attachment":[{"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=9946"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=9946"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/spinor.info\/weblog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=9946"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}