|
%I #23 Dec 12 2020 20:18:35
%S 1,1,1,1,1,2,1,1,2,3,6,1,1,2,4,6,12,24,1,1,3,4,5,10,16,20,30,60,120,1,
%T 1,3,5,6,15,20,30,30,60,90,120,180,360,720,1,1,4,7,10,7,21,35,54,70,
%U 42,105,140,210,318,210,420,630,840,1260,2520,5040
%N Partition array for the number of representative necklaces (only cyclic symmetry) with n beads, each available in n colors. Only the color type (signature) matters.
%C The row lengths sequence is A000041(n), n>=1.
%C 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.
%C A necklace with n beads (n-necklace) has here only the cyclic C_n symmetry group. This is in contrast to, e.g., the Harary-Palmer reference, p. 44, where a n-necklace has the symmetry group D_n, the dihedral group of degree n (order 2n), which allows, in addition to C_n operations, also a turnover (in 3-space) or a reflection (in 2-space).
%C The necklace number a(n,k) gives the number of n-necklaces, 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], is written as [3,1,1], a partition of n=5. In general [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 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]}. Such an n-multiset representative (of a repetition class defined by the exponents, sometimes called signature) encodes the n-necklace 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-necklaces 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)=4 non-equivalent 5-necklaces with this color assignment are cyclic(c[1]c[1]c[1]c[2]c[3]), cyclic(c[1]c[1]c[1]c[3]c[2]), cyclic(c[1]c[1]c[2]c[1]c[3]) and cyclic(c[1]c[1]c[3]c[1]c[2]).
%C Such a set of a(n,k) n-necklaces for the given color assignment stands for other sets of the same order where 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 4 possible non-equivalent 5-necklace arrangements. Thus one has, in total, 30*4=120 5-necklaces with color signature determined from the partition [3,1,1]. See the partition array A212360 for these numbers.
%C For the example n=4, k=1..5, see the Stanley reference, last line, where the numbers a(4,k) are, in A-St order, 1, 1, 2, 3, 6, summing to A072605(4).
%C a(n,k) is computed from the cycle index Z(C_n) for the cyclic group (see A212357 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(C_n,c_n) with c_n:=sum(c[i],i=1..n), n>=1. The coefficient of the color assignment representative 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=C_n and p. 36 eq. (2.2.10) for the cycle index polynomial Z(C_n). See the W. Lang link for more details.
%C The corresponding triangle with summed entries of row n which belong to partitions of n with the same number of parts is A213934. [_Wolfdieter Lang_, Jul 12 2012]
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 36, (2.2.10).
%D R. Stanley, Enumerative combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999, p. 392, 7.24.3 Example.
%H Álvar Ibeas, <a href="/A212359/b212359.txt">First 25 rows, flattened</a>
%H Wolfdieter Lang, <a href="/A212359/a212359_1.pdf">Rows n=1..15 and color polynomials n=1..10.</a>
%F a(n,k) is the number of necklace arrangements with n beads (respecting the cyclic C_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.
%F From _Álvar Ibeas_, Dec 12 2020: (Start)
%F Let L be the k-th partition of n in A-St and d be the gcd of its parts. Abusing the notation, we write a(n, L) for a(n, k) and accordingly for other partition arrays.
%F a(n, L) = n^(-1) * Sum_{v|d} phi(v) * A036038(n/v, L/v), where L/v is the partwise division of L by v.
%F a(n, L) = Sum_{v|d} A339677(L/v).
%F (End)
%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
%e 1 1
%e 2 1 1
%e 3 1 1 2
%e 4 1 1 2 3 6
%e 5 1 1 2 4 6 12 24
%e 6 1 1 3 4 5 10 16 20 30 60 120
%e 7 1 1 3 5 6 15 20 30 30 60 90 120 180 360 720
%e ...
%e See the link for the rows n=1..15 and the corresponding color polynomials for n=1..10.
%e a(4,5)=6 because the partition in question is 1^4, the corresponding color type representative multinomial is c[1]*c[2]*c[3]*c[4] (all four colors are involved), and there are the 6 C_4 non-equivalent 4-necklaces (we use here j for color c[j]): 1234, 1243, 1324, 1342, 1423 and 1432 (all taken as cyclically). For this partition there is only one color choice.
%e a(4,4)=3 because the partition is [2,1^2]=[2,1,1], the color representative monomial is c[1]^2*c[2]*c[3], and the arrangements are 1123, 1132 and 1213 (all taken cyclically). There are, in total, 4*binomial(3,2)=12 color multinomials of this signature (color type) in Z(C_4,c_4).
%Y Cf. A212357 for Z(C_n), A072605 for the row sums. A212360, A213934.
%K nonn,tabf
%O 1,6
%A _Wolfdieter Lang_, Jun 25 2012
|
