|
| |
|
|
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; 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
| Eric Weisstein's World of Mathematics, Wheel Graph
|
|
|
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
| Cf. A000029, A000031, A001868, A161222.
Sequence in context: A109110 A108870 A111587 * A130045 A147971 A197869
Adjacent sequences: A161218 A161219 A161220 * A161222 A161223 A161224
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| H. O. Pollak (hpollak(AT)adsight.com) and N. J. A. Sloane (njas(AT)research.att.com), Nov 21 2009
|
| |
|
|
