A212359 - OEIS

%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