

A214609


Table of numbers of distinct bracelets (reversible necklaces) with n beads corresponding to one partition P of n. Each part p of P corresponds to p beads of a distinct color.


1



1, 1, 1, 1, 1, 1, 3, 2, 2, 1, 1, 12, 6, 4, 2, 2, 1, 1, 60, 30, 16, 11, 10, 6, 3, 3, 3, 1, 1, 360, 180, 90, 48, 60, 30, 18, 10, 15, 9, 4, 3, 3, 1, 1, 2520, 1260, 630, 318, 171, 420, 210, 108, 70, 38, 105, 54, 33
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,7


LINKS



FORMULA

With S = Sum_( d  GCD of the parts of P ) { phi(d) * F(n/d, P/d) },
 (S+n*F((n1)/2, [P/2]))/(2*n) if odd n, and only 1 odd part in P,
 S/(2*n) if odd n, and other P,
 (S + n * F(n/2, P/2)) / (2*n) if P has all even parts,
a(n)= (S + n * F((n2)/2, [P/2])) / (2*n)
 if even n, and P has exactly two odd parts,
 S/(2*n) if even n, and other P.
Where P is a partition of n, P/d is a vector of all the parts of P divided by d. Each element of vector [P/2] is equal to floor(p/2), p one part of P, and F(x,Y) = x! / (Y_1! * Y_2! * ...).


EXAMPLE

Table begins
. 1
. 1,1
. 1,1,1
. 3,2,2,1,1
.12,6,4,2,2,1,1
...
Line number 4 is 3,2,2,1,1 because three bracelets, (0 1 2 3), (0 1 3 2), and (0 2 1 3) correspond to partition [1 1 1 1]. (The colors are denoted by 0,1,2, and 3.) Bracelets (0 0 1 2), and (0 1 0 2) which have two beads of color 0, one of color 1, and one of color 2, correspond to [2 1 1]. (0 0 1 1), and (0 1 0 1) => [2 2]; (0 0 0 1) => [3 1], and (0 0 0 0) => [4].


PROG

(PARI)
N; L = 0; max_n = 25;
x = vector(max_n+1); P = vector(max_n+1); \\ P  partition of n
gcdP(t) = {if(t == 2, return(P[2])); GCD = gcd(P[2], P[3]);
for(J = 4, t, GCD = gcd(GCD, P[J])); return(GCD) }
x_P_div_d(t, d) = for(J = 2, t, x[J] = P[J]/d);
F(a, t)= { b = x[2]!; for(J = 3, t, b *= x[J]!); return(a!/b) }
Sum(t) = { S = 0; GCD = gcdP(t);
fordiv(GCD, d, x_P_div_d(t, d); S+= eulerphi(d) * F(N/d, t)); return(S) }
OneOdd(t) = {K = 0; for(J = 2, t, if(P[J] % 2 == 1, K++)); return(K==1)}
TwoOdd(t) = {K = 0; for(J = 2, t, if(P[J] % 2 == 1, K++)); return(K==2)}
x_floor_P_div_2(t) = for(J = 2, t, x[J] = floor(P[J]/2));
all_even_parts(t) = { for(J = 2, t, if(P[J] % 2 == 1, return(0) ) ); return(1) }
x_P_div_2(t) = for(J = 2, t, x[J] = P[J]/2);
\\
A(t) = {S = Sum(t); L++;
if((N%2==1) && OneOdd(t), x_floor_P_div_2(t);
print(L, " ", (S + N * F((N1)/2, t))/(2*N)); return() );
if(N%2==1, print(L, " ", S/(2*N)); return() );
if(all_even_parts(t), x_P_div_2(t);
print(L, " ", (S + N * F(N/2, t))/(2*N)); return() );
if((N%2==0) && TwoOdd(t), x_floor_P_div_2(t);
print(L, " ", (S + N * F((N2)/2, t))/(2*N)); return() );
print(L, " ", S/(2*N)) }
\\ F. Ruskey algorithm 4.24
Part(n, k, t) = { P[t] = k;
if(n == k, A(t), for(j = 1, min(k, nk), Part(nk, j, t+1) ) )}
for(n = 1, max_n, N = n; Part(2*n, n, 1) ); \\ bfile format


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



