A161221 Consider necklaces with n beads, each black or white, where the n segments of cord between the beads are each colored red or green; a(n) is the number of different necklaces under the action of the dihedral group D_{2n}.
1, 4, 9, 20, 51, 136, 414, 1300, 4371, 15084, 53508, 192700, 703346, 2589304, 9603954, 35824240, 134285331, 505421344, 1909144014, 7234153420, 27488865564, 104717491064, 399826699734, 1529763696820, 5864079144466, 22518031691368, 86607753541164
Offset: 0
Keywords
Examples
a(4) = 51: the following table shows the number of such necklaces with b black beads, 4-b white beads, r red chord segments and 4-r green chord segments. The sum of the numbers is 51. b\r 0 1 2 3 4 ------------- 0 | 1 1 2 1 1 1 | 1 2 4 2 1 2 | 2 4 7 4 2 3 | 1 2 4 2 1 4 | 1 1 2 1 1 The number of ways to color the edges of a wheel graph (whose vertices are a 4-cycle and a common hub) so that there are exactly 0,1,2,...8 "red" edges is 1,2,6,10,13,10,6,2,1. This corresponds to the sum of the diagonals in the example above.
Links
- Eric Weisstein's World of Mathematics, Wheel Graph
Programs
-
Maple
with(numtheory); f:= n-> (1/2)*( (1/n) * add( phi(n/d)*2^(2*d), d in divisors(n)) + 2^(n+1) ); # this assumes n>0
-
Mathematica
Join[{1,4,9,20}, Table[CycleIndex[KSubsetGroup[Automorphisms[Wheel[n]], Edges[Wheel[n]]], s] /. Table[s[i]->2, {i,1,2(n)-2}], {n,5,25}]] (* Geoffrey Critzer, Nov 04 2011 *)
Formula
For n>0, a(n) = (1/2)*( (1/n) * Sum_{d|n} (phi(n/d)*2^(2*d)) + 2^(n+1) ).
Comments