|
| |
|
|
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
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
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).
|
|
|
LINKS
|
|
|
|
FORMULA
|
For n>0, a(n) = (1/2)*( (1/n) * Sum_{d|n} (phi(n/d)*2^(2*d)) + 2^(n+1) ).
|
|
|
EXAMPLE
|
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.
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
