A212360 -id:A212360 - cp's OEIS frontend

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.

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

Offset: 1

Wolfdieter Lang, Jun 25 2012

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 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).
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]).
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.
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).
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.
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]

			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 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.
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).

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.

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

Cf. A212357 for Z(C_n), A072605 for the row sums.

Cf. A000041 (row lengths), A036036, A185974, A212360, A213934, A318810.

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.
From Álvar Ibeas, Dec 12 2020: (Start)
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.
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.
a(n, L) = Sum_{v|d} A339677(L/v).
(End)
a(n,k) = A318810(A185974(n,k)). - Andrew Howroyd, Jan 23 2025

A214306 Triangle with entry a(n,m) giving the total number of bracelets of n beads (D_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

Original entry on oeis.org

1, 2, 1, 3, 6, 1, 4, 24, 24, 3, 5, 60, 180, 120, 12, 6, 165, 1120, 2040, 900, 60, 7, 336, 5145, 21420, 25200, 7560, 360, 8, 784, 23016, 183330, 442680, 335160, 70560, 2520, 9, 1584, 91056, 1320480, 5846400, 8890560, 4656960, 725760, 20160, 10

Offset: 1

Wolfdieter Lang, Jul 20 2012

This triangle is obtained from the array A213941 by summing in row n, for n >= 1, all entries related to partitions of n with the same number of parts m.
a(n,m) is the total number of necklaces of n beads (dihedral D_n symmetry) corresponding to all the color multinomials obtained from all p(n,m) = A008284(n,m) partitions of n with m parts, written in nonincreasing form, by 'exponentiation'. Therefore only m from the available n colors are present, and a(n,m) gives the number of bracelets with n beads with only m of the n available colors present, for m from 1,2,...,n, and n >= 1. All of the possible color assignments are counted.
See the comments on A212359 for the Abramowitz-Stegun (A-St) order of partitions, and the 'exponentiation' to obtain multisets, used to encode color multinomials, from partitions. See a link in A213938 for representative multisets for given signature used to define color multinomials.
The row sums of this triangle coincide with the ones of array A213941, and they are given by A081721.

			n\m 1    2     3       4       5       8       7      8     9
1   1
2   2    1
3   3    6     1
4   4   24    24       3
5   5   60   180     120      12
6   6  165  1120    2040     900     60
7   7  336  5145   21420   25200   7560      360
8   8  784 23016  183330  442680  33516    70560   2520
9   9 1584 91056 1320480 5846400 8890560 4656960 725760 20160
...
Row n=10:  10, 3420, 357480, 8691480, 64420272, 172609920, 177811200, 68040000, 8164800, 181440;
Row n=11:  11, 6820, 1327095, 52727400, 622175400, 2714009760, 4837417200, 3592512000, 1047816000, 99792000, 1814400.
a(2,2) = 1 from the color monomial c[1]^1*c[2]^1 = c[1]*c[2] (from the m=2 partition [1,1] of n=2). The bracelet in question is cyclic(12) (we use j for color c[j] in these examples). The same holds for the necklace case.
a(5,3) = 60 + 120 = 180, from A213941(5,4) + A213941(5,5), because k(5,3,1) = A214314(5,3) = 4 and p(5,3)=2.
a(3,1) = 3 from the color monomials c[1]^3, c[2]^3 and c[3]^3. The three bracelets are cyclic(111), cyclic(222) and cyclic(333). The same holds for the necklace case.
In general a(n,1)=n from the partition [n] providing the color signature (exponent), and the n color choices.
a(3,2) = 6 from the color signature c[.]^2 c[.]^1, (from the m=2 partition [2,1] of n=3), and there are 6 choices for the color indices. The 6 bracelets are cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332). The same holds for the necklace case.
a(3,3) = 1. The color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). All three available colors are used. There is only one bracelet: cyclic(1,2,3). The necklace cyclic(1,3,2) becomes equivalent under D_3 operation.
a(4,2) = 24 from two color signatures c[.]^3 c[.] and c[.]^2 c[.]^2 (from the two m=2 partitions of n=4: [3,1] and [2,2]). The first one produces 4*3=12 bracelets, namely 1112, 1113, 1114, 2221, 2223, 2224, 3331, 3332, 3334, 4441, 4442 and 4443, all taken cyclically. The second color signature leads to another 6*2=12 bracelets: 1122, 1133, 1144, 2233, 2244, 3344, 1212, 1313, 1414, 2323, 2424 and 3434, all taken cyclically. Together they provide the 24 bracelets counted by a(4,2). The same holds for the necklace case.
a(4,3) = 24 from the color signature c[.]^2 c[.]c[.]. There are 4*3 =12 color choices each with two bracelets: 1123, 1213, 1124, 1214, 1134, 1314, 2213, 2123, 2214, 2124, 2234, 2324, 3312, 3132, 3314, 3134, 3324, 3234, 4412, 4142, 4413, 4143, 4423 and 4243, each taken cyclically.

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Cf. A081721, A212360 (necklaces), A213941, A273891.

(* t = A081720 *) t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1 + k)*k^(n/2))/(2*n), (t1 + n*k^((n + 1)/2))/(2*n)]);
T[n_, k_] := Binomial[n, k]*Sum[(-1)^i * Binomial[k, i]*t[n, k - i], {i, 0, k - 1}];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

a(n,m) = Sum_{j=1..p(n,m)} A213941(n, k(n,m,1)+j-1), with k(n,m,1) = A214314(n,m) the position where in the list of partitions of n in A-St order the first with m parts appears, and p(n,m) is the number of partitions of n with m parts shown in the array A008284. E.g., n=5, m=3: k(5,3,1) = A214314(5,3) = 4, p(5,3) = 2.

a(n,m) = binomial(n,m) * A273891(n,m). - Andrew Howroyd, Mar 25 2017

A213935 Triangle with entry a(n,m) giving the total number of necklaces of n beads (C_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

Original entry on oeis.org

1, 2, 1, 3, 6, 2, 4, 24, 36, 6, 5, 60, 300, 240, 24, 6, 180, 1820, 3900, 1800, 120, 7, 378, 9030, 42000, 50400, 15120, 720, 8, 952, 40824, 357420, 882000, 670320, 141120, 5040, 9, 2088, 169512, 2610720, 11677680, 17781120, 9313920, 1451520, 40320, 10, 4770, 673560, 17193960, 128598624, 345144240, 355622400, 136080000, 16329600, 362880

Offset: 1

Wolfdieter Lang, Jun 27 2012

This triangle is obtained from the array A212360 by summing in the row number n, for n>=1, all entries related to partitions of n with the same number of parts m.
a(n,m) is the total number of necklaces of n beads (C_n symmetry) corresponding to all the color multinomials obtained from all p(n,m)=A008284(n,m) partitions of n with m parts, written in nonincreasing form, by 'exponentiation'. Therefore only m from the available n colors are present, and a(n,m) gives the number of necklaces with n beads with only m of the n available colors present, for m from 1,2,...,n, and n>=1. All of the possible color assignments are counted.
See the comments on A212359 for the Abramowitz-Stegun (A-St) order of partitions, and the 'exponentiation' to obtain multisets, used to encode color multinomials, from partitions.
The row sums of this triangle coincide with the ones of array A212360, and they are given by A056665.

			n\m 1    2      3       4       5       8      7     8 ...
1   1
2   2    1
3   3    6      2
4   4   24     36       6
5   5   60    300     240      24
6   6  180   1820    3900    1800     120
7   7  378   9030   42000   50400   15120     72
8   8  952  40824  357420  882000  670320 141120  5040
...
Row n=9:   9 2088 169512 2610720 11677680 17781120 9313920 1451520 40320.
Row n=10: 10 4770 673560 17193960 128598624 345144240 355622400 136080000 16329600 362880.
a(2,2)=1 from the color monomial c[1]^1*c[2]^1= c[1]*c[2] (from the m=2 partition [1,1] of n=2). The necklace in question is cyclic(12) (we use j for color c[j] in these examples).
a(5,3) = 120 + 180 = 300, from A212360(5,4) + A212360(5,5), because k(5,3,1)=4 and p(5,3)=2.
a(3,1) = 3 from the color monomials c[1]^3, c[2]^3 and c[3]^1. The three necklaces are cyclic(111), cyclic(222) and cyclic(333).
In general a(n,1)=n from the partition [n] providing the color signature (exponent), and the n color choices.
a(3,2) = 6 from the color signature c[.]^2 c[.]^1, (from the m=2 partition [2,1] of n=3), and there are 6 choices for the color indices. The 6 necklaces are cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).
a(3,3) = 2. The color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). All three available colors are used. There are two non-equivalent necklaces: cyclic(1,2,3) and cyclic(1,3,2).
a(4,2) = 24 from two color signatures c[.]^3 c[.] and c[.]^2 c[.]^2 (from the two m=2 partitions of n=4: [3,1] and [2,2]). The first one produces 4*3=12 necklaces, namely 1112, 1113, 1114, 2221, 2223, 2224, 3331, 3332, 3334, 4441, 4442 and 4443 all taken cyclically. The second color signature leads to another 2*6=12 necklaces: 1122, 1133, 1144, 2233, 2244, 3344, 1212, 1313, 1414, 2323, 2424 and 3434, all taken cyclically. Together they provide the 24 necklaces counted by a(4,2).

Cf. A212360, A056665 (row sums). A075195 (another necklace table).

a(n,m) = Sum_{j=1..p(n,m)}A212360(n,k(n,m,1)+j-1), with k(n,m,1) the position where in the list of partitions of n in A-St order the first with m parts appears, and p(n,m) the number of partitions of n with m parts shown in the array A008284. E.g., n=5, m=3: k(5,3,1)=4, p(5,3)=2.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A214306 Triangle with entry a(n,m) giving the total number of bracelets of n beads (D_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A213935 Triangle with entry a(n,m) giving the total number of necklaces of n beads (C_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula