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

%I

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

%T 180,90,48,60,30,18,10,15,9,4,3,3,1,1,2520,1260,630,318,171,420,210,

%U 108,70,38,105,54,33

%N 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.

%H Washington Bomfim, <a href="/A214609/b214609.txt">Rows 1..25, flattened</a>

%H Harold S. Grant, <a href="http://www.jstor.org/pss/3029277">On a Formula for Circular Permutations</a>, Mathematics Magazine, Vol. 23, No. 3 (Jan. - Feb., 1950), pp. 133-136.

%H Hiroshi Kajimoto and Mai Osabe, <a href="http://naosite.lb.nagasaki-u.ac.jp/dspace/bitstream/10069/7251/1/KJ00004438116.pdf">Circular and Necklace Permutations</a>, Bulletin of the Faculty of Education, Nagasaki University. Natural Sciences 2006; v.74, 1-14.

%H S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, <a href="http://www.socs.uoguelph.ca/~sawada/papers/fix-brace.pdf">Generating bracelets with fixed content</a>, (2011).

%H S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine, <a href="https://doi.org/10.1016/j.tcs.2012.11.024">Generating bracelets with fixed content</a>, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.

%H Frank Ruskey, <a href="https://web.archive.org/web/20171022155546/http://www.1stworks.com/ref/RuskeyCombGen.pdf">Combinatorial Generation Algorithm Algorithm 4.24, p. 95</a>.

%H <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>

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

%F | (S+n*F((n-1)/2, [P/2]))/(2*n) if odd n, and only 1 odd part in P,

%F | S/(2*n) if odd n, and other P,

%F | (S + n * F(n/2, P/2)) / (2*n) if P has all even parts,

%F a(n)=| (S + n * F((n-2)/2, [P/2])) / (2*n)

%F | if even n, and P has exactly two odd parts,

%F | S/(2*n) if even n, and other P.

%F 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! * ...).

%e Table begins

%e . 1

%e . 1,1

%e . 1,1,1

%e . 3,2,2,1,1

%e .12,6,4,2,2,1,1

%e ...

%e 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].

%o (PARI)

%o N; L = 0; max_n = 25;

%o x = vector(max_n+1); P = vector(max_n+1); \\ P - partition of n

%o gcdP(t) = {if(t == 2, return(P[2])); GCD = gcd(P[2], P[3]);

%o for(J = 4, t, GCD = gcd(GCD, P[J])); return(GCD) }

%o x_P_div_d(t, d) = for(J = 2, t, x[J] = P[J]/d);

%o F(a, t)= { b = x[2]!; for(J = 3, t, b *= x[J]!); return(a!/b) }

%o Sum(t) = { S = 0; GCD = gcdP(t);

%o fordiv(GCD, d, x_P_div_d(t,d); S+= eulerphi(d) * F(N/d, t)); return(S) }

%o OneOdd(t) = {K = 0; for(J = 2, t, if(P[J] % 2 == 1, K++)); return(K==1)}

%o TwoOdd(t) = {K = 0; for(J = 2, t, if(P[J] % 2 == 1, K++)); return(K==2)}

%o x_floor_P_div_2(t) = for(J = 2, t, x[J] = floor(P[J]/2));

%o all_even_parts(t) = { for(J = 2, t, if(P[J] % 2 == 1, return(0) ) ); return(1) }

%o x_P_div_2(t) = for(J = 2, t, x[J] = P[J]/2);

%o \\

%o A(t) = {S = Sum(t); L++;

%o if((N%2==1) && OneOdd(t), x_floor_P_div_2(t);

%o print(L," ",(S + N * F((N-1)/2, t))/(2*N)); return() );

%o if(N%2==1, print(L," ", S/(2*N)); return() );

%o if(all_even_parts(t), x_P_div_2(t);

%o print(L," ",(S + N * F(N/2, t))/(2*N)); return() );

%o if((N%2==0) && TwoOdd(t), x_floor_P_div_2(t);

%o print(L," ",(S + N * F((N-2)/2, t))/(2*N)); return() );

%o print(L," ", S/(2*N)) }

%o \\ F. Ruskey algorithm 4.24

%o Part(n, k, t) = { P[t] = k;

%o if(n == k, A(t), for(j = 1, min(k, n-k), Part(n-k, j, t+1) ) )}

%o for(n = 1, max_n, N = n; Part(2*n, n, 1) ); \\ b-file format

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

%K nonn,tabf

%O 1,7

%A _Washington Bomfim_, Jul 22 2012

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 October 14 00:32 EDT 2019. Contains 327991 sequences. (Running on oeis4.)