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.
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.
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].
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)
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
KEYWORD
nonn,tabf
AUTHOR
Washington Bomfim, Jul 22 2012
STATUS
approved