|
|
A207816
|
|
Number of distinct necklaces with n red, n green, n blue and n white beads.
|
|
2
|
|
|
1, 6, 318, 30804, 3941598, 586637256, 96197661156, 16875655269948, 3111284141045598, 595909785174057204, 117634021777132574568, 23797087019979071174580, 4912693780461352534397604, 1031629572413246016139181544, 219809927417367534490107035244, 47426945434432859336092700072304
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{d|n} phi(n/d)*(4*d)!/(d!^4*4*n) if n>0 and a(0) = 1. - Alois P. Heinz, Feb 24 2012
|
|
EXAMPLE
|
For n=1, a(1)=6 since for four beads necklaces with each bead from each of the four colors say (R,G,B,W), we can arrange as following, [R,G,B,W], [R,G,W,B], [R,B,G,W], [R,B,W,G], [R,W,G,B] and [R,W,B,G].
|
|
MAPLE
|
with(combinat): with(numtheory):
# This formula comes from Polya Counting Theorem:
# Z(C_n) = add(phi(d)*(a_d)^(n/d), d in divisors(n))/n;
PolyaBrace:= proc(S) option remember; local n, s, d;
n:= add(s, s=S);
add(phi(d) *PolyaCoeff(d, S), d=divisors(n))/n
end:
# Find coeff of prod(a[i]^s[i], i=1..n) of a_d^(n/d) (symmetric function)
PolyaCoeff:= proc(d, S) option remember; local n, pow, s;
n:= add(s, s=S);
pow:= n/d;
if {seq(s mod d, s = S)} = {0}
then multinomial(pow, seq(s/d, s = S))
else 0
fi:
end:
a:= n-> `if`(n=0, 1, PolyaBrace([n$4])):
seq(a(n), n=0..20);
|
|
MATHEMATICA
|
a[n_] := DivisorSum[n, EulerPhi[n/#] (4#)!/(#!^4 * 4n)&]; a[0]=1;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|