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, 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

Offset

1,7

Links

Washington Bomfim, Rows 1..25, flattened

Harold S. Grant, On a Formula for Circular Permutations, Mathematics Magazine, Vol. 23, No. 3 (Jan. - Feb., 1950), pp. 133-136.

Hiroshi Kajimoto and Mai Osabe, Circular and Necklace Permutations, Bulletin of the Faculty of Education, Nagasaki University. Natural Sciences 2006; v.74, 1-14.

S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, Generating bracelets with fixed content, (2011).

S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.

Frank Ruskey, Combinatorial Generation Algorithm Algorithm 4.24, p. 95.

Index entries for sequences related to bracelets

Formula

With S = Sum_( d | GCD of the parts of P ) { phi(d) * F(n/d, P/d) },

| (S+n*F((n-1)/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((n-2)/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((N-1)/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((N-2)/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, n-k), Part(n-k, j, t+1) ) )}
for(n = 1, max_n, N = n; Part(2*n, n, 1) );  \\ b-file format

Crossrefs

Cf. A000041 (row lengths), A213939 (another version with partitions found in a different order), A005654, A005656, A141783, A000010.

Sequence in context: A016558 A154395 A371671 * A152159 A341941 A090341

Adjacent sequences: A214606 A214607 A214608 * A214610 A214611 A214612

Keyword

nonn,tabf

Author

Washington Bomfim, Jul 22 2012

Status

approved