|
| |
|
|
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.
|
|
2
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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.
|
|
|
EXAMPLE
|
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).
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
