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

Author

H. O. Pollak (hpollak(AT)adsight.com) and N. J. A. Sloane, Nov 21 2009

Keywords

• nonn

Comments

If the group is changed to C_n we get A001868.

For n>=4 a(n) is the number of ways to color the edges of a wheel graph using at most 2 colors. A wheel graph is a graph that contains a cycle of order n and every graph vertex is connected to one other graph vertex (which is known as the hub).

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

Crossrefs

Cf. A000029, A000031, A001868, A161222.

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