login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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: A238402 A016558 A154395 * A152159 A090341 A251092

Adjacent sequences:  A214606 A214607 A214608 * A214610 A214611 A214612

KEYWORD

nonn,tabf

AUTHOR

Washington Bomfim, Jul 22 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 05:51 EDT 2019. Contains 327212 sequences. (Running on oeis4.)