A161221 - OEIS

%I #20 Feb 16 2025 08:33:10

%S 1,4,9,20,51,136,414,1300,4371,15084,53508,192700,703346,2589304,

%T 9603954,35824240,134285331,505421344,1909144014,7234153420,

%U 27488865564,104717491064,399826699734,1529763696820,5864079144466,22518031691368,86607753541164

%N 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}.

%C If the group is changed to C_n we get A001868.

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

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>

%F For n>0, a(n) = (1/2)*( (1/n) * Sum_{d|n} (phi(n/d)*2^(2*d)) + 2^(n+1) ).

%e 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.

%e b\r 0 1 2 3 4

%e -------------

%e 0 | 1 1 2 1 1

%e 1 | 1 2 4 2 1

%e 2 | 2 4 7 4 2

%e 3 | 1 2 4 2 1

%e 4 | 1 1 2 1 1

%e 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.

%p 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

%t 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 *)

%Y Cf. A000029, A000031, A001868, A161222.

%K nonn,changed

%O 0,2

%A H. O. Pollak (hpollak(AT)adsight.com) and _N. J. A. Sloane_, Nov 21 2009