cp's OEIS Frontend

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.

%I A214609 #30 Jan 26 2025 18:54:18
%S A214609 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 A214609 180,90,48,60,30,18,10,15,9,4,3,3,1,1,2520,1260,630,318,171,420,210,
%U A214609 108,70,38,105,54,33,19,8,21,12,5,4,4,1,1,20160,10080,5040,2520,1272,3360,1680,840,432,560,280,94,840,420,216,140,76,38,168,84,48,28,10,28,16,7,4,4,1,1
%N 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.
%H A214609 Washington Bomfim, <a href="/A214609/b214609.txt">Rows 1..25, flattened</a>
%H A214609 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 A214609 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 A214609 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 A214609 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 A214609 Math StackExchange, Marko Riedel et. al, <a href="https://math.stackexchange.com/questions/5025780/">Free circular permutations</a>.
%H A214609 Marko Riedel, <a href="/A214609/a214609.txt">Maple code for sequence by PET and closed form.</a>
%H A214609 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 A214609 <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>
%F A214609 With S = Sum_( d | GCD of the parts of P ) { phi(d) * F(n/d, P/d) },
%F A214609      | (S+n*F((n-1)/2, [P/2]))/(2*n) if odd n, and only 1 odd part in P,
%F A214609      | S/(2*n)                                    if odd n, and other P,
%F A214609      | (S + n * F(n/2, P/2)) / (2*n)            if P has all even parts,
%F A214609 a(n)=| (S + n * F((n-2)/2, [P/2])) / (2*n)
%F A214609      |                       if even n, and P has exactly two odd parts,
%F A214609      | S/(2*n)                                   if even n, and other P.
%F A214609 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 A214609 Table begins
%e A214609    1
%e A214609    1,1
%e A214609    1,1,1
%e A214609    3,2,2,1,1
%e A214609   12,6,4,2,2,1,1
%e A214609    ...
%e A214609 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].
%e A214609 From _Marko Riedel_, Jan 23 2025 (Start)
%e A214609 The ordering of the partitions used here is graded reflected lexicographic illustrated below with n=5:
%e A214609   1,1,1,1,1 => 12
%e A214609   1,1,1,2 => 6
%e A214609   1,2,2 => 4
%e A214609   1,1,3 => 2
%e A214609   2,3 => 2
%e A214609   1,4 => 1
%e A214609   5 => 1 (End)
%o A214609 (PARI)
%o A214609 N; L = 0; max_n = 25;
%o A214609 x = vector(max_n+1); P = vector(max_n+1);          \\ P - partition of n
%o A214609 gcdP(t) = {if(t == 2, return(P[2])); GCD = gcd(P[2], P[3]);
%o A214609 for(J = 4, t, GCD = gcd(GCD, P[J])); return(GCD) }
%o A214609 x_P_div_d(t, d) = for(J = 2, t, x[J] = P[J]/d);
%o A214609 F(a, t)= { b = x[2]!; for(J = 3, t, b *= x[J]!); return(a!/b) }
%o A214609 Sum(t) = { S = 0; GCD = gcdP(t);
%o A214609 fordiv(GCD, d, x_P_div_d(t,d); S+= eulerphi(d) * F(N/d, t)); return(S) }
%o A214609 OneOdd(t) = {K = 0; for(J = 2, t, if(P[J] % 2 == 1, K++)); return(K==1)}
%o A214609 TwoOdd(t) = {K = 0; for(J = 2, t, if(P[J] % 2 == 1, K++)); return(K==2)}
%o A214609 x_floor_P_div_2(t) = for(J = 2, t, x[J] = floor(P[J]/2));
%o A214609 all_even_parts(t) = { for(J = 2, t, if(P[J] % 2 == 1, return(0) ) ); return(1) }
%o A214609 x_P_div_2(t) = for(J = 2, t, x[J] = P[J]/2);
%o A214609 \\
%o A214609 A(t) = {S = Sum(t); L++;
%o A214609 if((N%2==1) && OneOdd(t), x_floor_P_div_2(t);
%o A214609    print(L," ",(S + N * F((N-1)/2, t))/(2*N)); return() );
%o A214609 if(N%2==1, print(L," ", S/(2*N)); return() );
%o A214609 if(all_even_parts(t), x_P_div_2(t);
%o A214609    print(L," ",(S + N * F(N/2, t))/(2*N)); return() );
%o A214609 if((N%2==0) &&  TwoOdd(t), x_floor_P_div_2(t);
%o A214609    print(L," ",(S + N * F((N-2)/2, t))/(2*N)); return() );
%o A214609 print(L," ", S/(2*N)) }
%o A214609                                             \\ F. Ruskey algorithm 4.24
%o A214609 Part(n, k, t) = { P[t] = k;
%o A214609 if(n == k, A(t), for(j = 1, min(k, n-k), Part(n-k, j, t+1) ) )}
%o A214609 for(n = 1, max_n, N = n; Part(2*n, n, 1) );  \\ b-file format
%Y A214609 Cf. A000041 (row lengths), A213939 (another version with partitions found in a different order), A005654, A005656, A141783, A000010, A380401.
%Y A214609 Row sums give A213943.
%Y A214609 Cf. A080576 (graded reflected lexicographic order).
%K A214609 nonn,tabf
%O A214609 1,7
%A A214609 _Washington Bomfim_, Jul 22 2012