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

Author

Wolfdieter Lang, Jul 20 2012

Keywords

• nonn
• tabf

Comments

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.

Examples

			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.
		

References

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

Links

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

Crossrefs

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

Formula

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.