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, 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
Offset: 1
Examples
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]. From _Marko Riedel_, Jan 23 2025 (Start) The ordering of the partitions used here is graded reflected lexicographic illustrated below with n=5: 1,1,1,1,1 => 12 1,1,1,2 => 6 1,2,2 => 4 1,1,3 => 2 2,3 => 2 1,4 => 1 5 => 1 (End)
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.
- Math StackExchange, Marko Riedel et. al, Free circular permutations.
- Marko Riedel, Maple code for sequence by PET and closed form.
- Frank Ruskey, Combinatorial Generation Algorithm Algorithm 4.24, p. 95.
- Index entries for sequences related to bracelets
Crossrefs
Programs
-
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
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! * ...).
Comments