

A212359


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.


14



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, 1, 3, 5, 6, 15, 20, 30, 30, 60, 90, 120, 180, 360, 720, 1, 1, 4, 7, 10, 7, 21, 35, 54, 70, 42, 105, 140, 210, 318, 210, 420, 630, 840, 1260, 2520, 5040
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


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 necklace with n beads (nnecklace) has here only the cyclic C_n symmetry group. This is in contrast to, e.g., the HararyPalmer reference, p. 44, where a nnecklace 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 3space) or a reflection (in 2space).
The necklace number a(n,k) gives the number of nnecklaces, 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], 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 nmultiset obtained by 'exponentiation'. 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]}. Such an nmultiset representative (of a repetition class defined by the exponents, sometimes called signature) encodes the nnecklace 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 5necklaces 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)=4 nonequivalent 5necklaces 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]).
Such a set of a(n,k) nnecklaces 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 alltogether 5*binomial(4,2) = 30 such sets, each leading to 4 possible nonequivalent 5necklace arrangements. Thus one has, in total, 30*4=120 5necklaces with color signature determined from the partition [3,1,1]. See the partition array A212360 for these numbers.
For the example n=4, k=1..5, see the Stanley reference, last line, where the numbers a(4,k) are, in ASt order, 1, 1, 2, 3, 6, summing to A072605(4).
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 jth 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 kth partition of n in ASt order, as explained above, is a(n,k). See the HararyPalmer 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.
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]


REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 36, (2.2.10).
R. Stanley, Enumerative combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999, p. 392, 7.24.3 Example.


LINKS

Álvar Ibeas, First 25 rows, flattened
Wolfdieter Lang, Rows n=1..15 and color polynomials n=1..10.


FORMULA

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 kth partition of n in ASt order. See the comment for more details and the ASt reference.
From Álvar Ibeas, Dec 12 2020: (Start)
Let L be the kth partition of n in ASt 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.
a(n, L) = n^(1) * Sum_{vd} phi(v) * A036038(n/v, L/v), where L/v is the partwise division of L by v.
a(n, L) = Sum_{vd} A339677(L/v).
(End)


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 2
4 1 1 2 3 6
5 1 1 2 4 6 12 24
6 1 1 3 4 5 10 16 20 30 60 120
7 1 1 3 5 6 15 20 30 30 60 90 120 180 360 720
...
See the link for the rows n=1..15 and the corresponding color polynomials for n=1..10.
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 nonequivalent 4necklaces (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.
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).


CROSSREFS

Cf. A212357 for Z(C_n), A072605 for the row sums. A212360, A213934.
Sequence in context: A169786 A191631 A025259 * A130030 A088022 A284999
Adjacent sequences: A212356 A212357 A212358 * A212360 A212361 A212362


KEYWORD

nonn,tabf


AUTHOR

Wolfdieter Lang, Jun 25 2012


STATUS

approved



