

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.


14



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,9


COMMENTS

The row lengths sequence is A000041(n), n >= 1.
The partitions are ordered like in AbramowitzStegun (ASt 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 (nbracelet) has the dihedral D_n symmetry group of degree n (order 2n). In addition to cyclic C_n operations, also a turnover (in 3space) or a reflection (in 2space) is allowed. In the HararyPalmer reference, p. 44, the term necklace is used instead of bracelet.
a(n,k) gives the number of representative nbracelets, with up to n colors for each bead, belonging to the kth partition of n in ASt order in the following way. Write this partition with nonincreasing parts (this is the reverse of the partition as given by ASt), 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 nmultiset 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 5multiset 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 nmultiset representative (of a repetition class defined by the exponents, also called signature) encodes the representative nbracelet 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 5bracelets with this color assignment is a(5,4) because [3,1,1] is the 4th partition of 5 in ASt order. The a(5,4)=2 nonequivalent 5bracelets 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) nbracelets 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 alltogether 5*binomial(4,2) = 30 such sets, each leading to 2 possible nonequivalent 5bracelet arrangements. Thus one has alltogether 30*2=60 5bracelets 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 jth 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 kth partition of n in ASt order, as explained above, is a(n,k). See the HararyPalmer 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.


REFERENCES

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


LINKS



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 kth partition of n in ASt order. See the comment for more details and the ASt reference.


EXAMPLE

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 nonequivalent 4bracelets (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.


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



