A213943 -id:A213943 - cp's OEIS frontend

A213939 Partition array for the number of representative bracelets (dihedral symmetry D_n) with n beads, each available in n colors. Only the color type (signature) matters.

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 1, 1, 2, 2, 4, 6, 12, 1, 1, 3, 3, 3, 6, 11, 10, 16, 30, 60, 1, 1, 3, 4, 3, 9, 10, 18, 15, 30, 48, 60, 90, 180, 360, 1, 1, 4, 5, 8, 4, 12, 19, 33, 38, 21, 54, 70, 108, 171, 105, 210, 318, 420, 630, 1260, 2520, 1, 1, 4, 7, 10, 4, 16, 28, 38, 48, 76, 94

Offset: 1

Wolfdieter Lang, Jul 20 2012

The row lengths sequence is A000041(n), n >= 1.
The partitions are ordered like in Abramowitz-Stegun (A-St order). For the reference see A036036, where also a link to a work by C. F. Hindenburg from 1779 is found where this order has been used.
A bracelet with n beads (n-bracelet) has the dihedral D_n symmetry group of degree n (order 2n). In addition to cyclic C_n operations, also a turnover (in 3-space) or a reflection (in 2-space) is allowed. In the Harary-Palmer reference, p. 44, the term necklace is used instead of bracelet.
a(n,k) gives the number of representative n-bracelets, with up to n colors for each bead, belonging to the k-th partition of n in A-St order in the following way. Write this partition with nonincreasing parts (this is the reverse of the partition as given by A-St), e.g., [3,1^2], not [1^2,3], which is written as [3,1,1], a partition of n=5. In general a (reversed) partition of n is written as [p[1],p[2],...,p[m]], with p[1] >= p[2] >= ... >= p[m] >= 1, with m the number of parts. To each such partition of n corresponds an n-multiset obtained by 'exponentiation'. For more details see the W. Lang link in A213938 with more details as well as a list of multiset signatures and corresponding multiset representatives. For the given example the 5-multiset is {1^3,2^1,3^1}={1,1,1,2,3}. In general, {1^p[1],2^p[2],...,m^p[m]}. We will also use a list notation with square brackets for these multisets. Such an n-multiset representative (of a repetition class defined by the exponents, also called signature) encodes the representative n-bracelet color monomial by c[1]^p[1]*c[2]^p[2]*...*c[m]^p[m]. For the example one has c[1]^3*c[2]*c[3]. The number of 5-bracelets with this color assignment is a(5,4) because [3,1,1] is the 4th partition of 5 in A-St order. The a(5,4)=2 non-equivalent 5-bracelets with this color assignment are cyclic(c[1]c[1]c[1]c[2]c[3]) and cyclic(c[1]c[1]c[2]c[1]c[3]). For the necklace case c[1]c[1]c[1]c[3]c[2] and c[1]c[1]c[3]c[1]c[2] (both taken cyclically) also have to be counted, but due to a turn over (or a reflection) they become equivalent to the two given bracelets, respectively.
Such a set of a(n,k) n-bracelets for the given color signature stands for other sets of the same order when different colors from the repertoire {c[1],...,c[n]} are chosen. In the example, the partition [3,1,1] with the representative multiset [1^3,2,3] stands for all-together 5*binomial(4,2) = 30 such sets, each leading to 2 possible non-equivalent 5-bracelet arrangements. Thus one has all-together 30*2=60 5-bracelets with color signature determined from the partition [3,1,1]. See the partition array A213941 for these total bracelet numbers.
a(n,k) is computed from the cycle index Z(D_n) for the dihedral group (see A212355 and the link given there) after the variables x_j have been replaced by the j-th power sum sum(c[i]^j,i=1..n), abbreviated as Z(D_n,c_n) with c_n:=sum(c[i],i=1..n), n >= 1. The coefficient of the representative color multinomial determined by the k-th partition of n in A-St order, as explained above, is a(n,k). See the Harary-Palmer reference, p. 36, Theorem (PET) with A = D_n and p. 37 eq. (2.2.11) for the cycle index polynomial Z(D_n). See the W. Lang link for more details.
The row sums are given by A213943.

			n\k 1 2 3 4 5 6  7  8  9 10 11 12 13  14  15 ...
1   1
2   1 1
3   1 1 1
4   1 1 2 2 3
5   1 1 2 2 4 6 12
6   1 1 3 3 3 6 11 10 16 30 60
7   1 1 3 4 3 9 10 18 15 30 48 60 90 180 360
...
Row n = 8 is 1 1 4 5 8 4 12 19 33 38 21 54 70 108 171 105 210 318 420 630 1260 2520.
See the link for the rows n=1 to n=15, and the corresponding color polynomials for n=1 to n=10.
a(4,5) = 3 because the partition in question is [1^4]=[1,1,1,1], the corresponding representative color multinomial is c[1]*c[2]*c[3]*c[4] (all four colors are involved), and there are the 3 D_4 non-equivalent 4-bracelets (we use here j for color c[j]): 1234, 1324 and 1423 (all taken as cyclically). For this partition there is only one color choice. The necklace solutions 1243, 1342, 1432, taken cyclically, become equivalent to the given bracelets, respectively (for necklaces see A212359).
a(4,4) = 2 because the partition is [2,1^2]=[2,1,1], the color representative multinomial is c[1]^2*c[2]*c[3], and the bracelet arrangements are 1123 and 1213 (all taken cyclically). The necklace cyclic(1132) becomes equivalent to the first bracelet under reflection. In total, there are 4*binomial(3,2)=12 color multinomials of this signature (color type) in Z(D_4,c_4), each with a coefficient 2.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973

Wolfdieter Lang, Rows n=1..15 and color polynomials n = 1..10.

Cf. A212355 (Z(D_n)), A213943(row sums), A213940 (triangle with entries for fixed m summed).

a(n,k) is the number of representative bracelet arrangements with n beads (respecting the dihedral D_n symmetry) with color assignment given by the multiset representative obtained uniquely from the k-th partition of n in A-St order. See the comment for more details and the A-St reference.

A213940 Triangle with entry a(n,m) giving the number of bracelets of n beads (dihedral D_n symmetry) with n colors available for each bead, but only m distinct fixed colors, say c[1],...,c[m], are present, with m from {1,...,n} and n>=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 3, 6, 6, 12, 1, 7, 20, 26, 30, 60, 1, 8, 40, 93, 150, 180, 360, 1, 18, 106, 424, 633, 1050, 1260, 2520, 1, 22, 304, 1180, 3260, 5040, 8400, 10080, 20160, 1, 46, 731, 4844, 16212, 29244, 45360, 75600, 90720, 181440

Offset: 1

Wolfdieter Lang, Jul 20 2012

This triangle is obtained from the partition array A213939 by summing in row n, for n>=1, all entries related to partitions of n with the same number of parts m.
a(n,m) is the number of bracelets of n beads (dihedral D_n symmetry) corresponding to the representative color multinomials obtained from all partitions of n with m parts by 'exponentiation', hence only m from the available n colors are present. As a representative multinomial of each of the p(n,m)=A008284(n,m) such m-color classes we take the one where the considered m part partition of n, [p[1],...,p[m]], written in nonincreasing order, is distributed as exponents on the color indices like c[1]^p[1]*...*c[m]^p[m]. That is only the first m colors from the n available ones are involved.
See the comments on A212359 for the Abramowitz-Stegun (A-St) order of partitions, and the 'exponentiation' to obtain multisets, used to encode color multinomials, from partitions.
The row sums of this triangle coincide with the ones of array A213939, and they are given by A213943.
Number of n-length bracelets w over a k-ary alphabet {a1,a2,...,ak} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 1, where #(w,x) counts the letters x in word w (bracelet analog of A226874). - Andrew Howroyd, Sep 26 2017

			n\m  1  2   3    4     5     6     7     8     9     10 ...
1    1
2    1  1
3    1  1   1
4    1  3   2    3
5    1  3   6    6    12
6    1  7  20   26    30    60
7    1  8  40   93   150   180   360
8    1 18 106  424   633  1050  1260  2520
9    1 22 304 1180  3260  5040  8400 10080 20160
10   1 46 731 4844 16212 29244 45360 75600 90720 181440
...
a(5,3) = 2 + 4 = 6, from A213939(5,4) + A213939(5,5), because k(5,3,1) = 4 and p(5,3) = 2.
a(2,1) = 1 because the partition [2] of n=2 with part number m=1 corresponds to the representative color multinomial (here monomial) c[1]^2 = c[1]*c[1], and there is one such representative bracelet. There is another bracelet color monomial in this class of n=2 colors where only m=1 color is active: c[2]*c[2]. See the triangle entry A213941(2,1)=2. The same holds for the necklace case.
a(3,1) = 1 from the color monomial representative c[1]^3. This class has 2 other members: c[2]^3 and c[3]^3. See A213941(3,1)=3. The same holds for the necklace case.
Like in the necklace case one has in general a(n,1)=1 and A213941(n,1) = n from the partition [n] providing the color signature and a representative c[1]^n.
a(3,2) = 1 from the representative color multinomial c[1]^2*c[2] (from the m=2 partition [2,1] of n=3) leading to just one representative bracelet (and necklace) cyclic(112) (when one uses j for color c[j]). The whole class consists of A213941(3,2)=6 bracelets (or necklaces): cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).
a(3,3) = 1. The representative color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). There is only one bracelet cyclic(1,2,3) which constitutes already the whole class (A213941(3,3)=1). The necklace cyclic(1,3,2) becomes equivalent under D_3.
a(4,2) = 3 from two representative color multinomials c[1]^3*c[2] and c[1]^2*c[2]^2 (from the two m=2 partitions of n=4: [3,1] and [2,2]). The first one has one representative bracelet, namely cyclic(1112), the second one leads to the two representative bracelets: cyclic(1122) and cyclic(1212). Together these are the 3 bracelets counted by a(4,2). The first color class c[.]^3*c[.] consists of 4*3=12 bracelets, when all 4 colors are used. The second one consists of 2*6=12 bracelets. Together they sum up to the 24 bracelets counted by A213941(4,2). In this example the necklace case does not differ from the bracelet one.

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns k=2..5 are A213942, A214307, A214309, A214311.
Cf. A008284, A213939, A213941, A213943 (row sums), A226874, A152176.
Cf. A213934 (cyclic symmetry).

Cyc(v)={my(s=vecsum(v)); sumdiv(gcd(v), d, eulerphi(d)*(s/d)!/prod(i=1, #v, (v[i]/d)!))/s}
CPal(v)={my(odds=#select(t->t%2,v), s=vecsum(v));  if(odds>2, 0, ((s-odds)/2)!/prod(i=1, #v, (v[i]\2)!))}
T(n,k)={my(t=0); forpart(p=n, t+=Cyc(Vec(p))+CPal(Vec(p)), [1,n], [k,k]); t/2}
for(n=1, 10, for(k=1,n, print1(T(n,k), ", ")); print); \\ Andrew Howroyd, Sep 26 2017

\\ faster version; here U is A226874 as vector of polynomials.
U(n)={Vec(serlaplace(prod(k=1, n, 1/(1-y*x^k/k!) + O(x*x^n))))}
T(n)={my(t=U(n)); vector(n, n, vector(n, k, ((1/n)*sumdiv(n, d, eulerphi(n/d) * polcoeff(t[d+1], k)) + if(n%2, sum(d=0, (n-1)/2, binomial((n-1)/2, d)*polcoeff(t[d+1], (k-1))), polcoeff(t[n/2+1], k) + sum(d=0, n/2-1, binomial(n/2-1, d)*(2^d + if(d%2, 0, binomial(d, d/2)))*polcoeff(t[n/2-d], k-2))/2))/2))}
{ my(t=T(10)); for(n=1, #t, print(t[n])) } \\ Andrew Howroyd, Dec 22 2017

a(n,m) = Sum_{j=1..p(n,m)}A213939(n,k(n,m,1)+j-1), with k(n,m,1) the position where in the list of partitions of n in A-St order the first with m parts appears, and p(n,m) is the number of partitions of n with m parts shown in the array A008284. E.g., n=5, m=3: k(5,3,1)=4, p(5,3)=2.

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.

Original entry on oeis.org

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

Washington Bomfim, Jul 22 2012

			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)

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

Cf. A000041 (row lengths), A213939 (another version with partitions found in a different order), A005654, A005656, A141783, A000010, A380401.
Row sums give A213943.
Cf. A080576 (graded reflected lexicographic order).

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

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

cp's OEIS Frontend

A213939 Partition array for the number of representative bracelets (dihedral symmetry D_n) with n beads, each available in n colors. Only the color type (signature) matters.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A213940 Triangle with entry a(n,m) giving the number of bracelets of n beads (dihedral D_n symmetry) with n colors available for each bead, but only m distinct fixed colors, say c[1],...,c[m], are present, with m from {1,...,n} and n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula