A213935 - OEIS

%I #18 Dec 20 2017 21:30:07

%S 1,2,1,3,6,2,4,24,36,6,5,60,300,240,24,6,180,1820,3900,1800,120,7,378,

%T 9030,42000,50400,15120,720,8,952,40824,357420,882000,670320,141120,

%U 5040,9,2088,169512,2610720,11677680,17781120,9313920,1451520,40320,10,4770,673560,17193960,128598624,345144240,355622400,136080000,16329600,362880

%N 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.

%C 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.

%C 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.

%C 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.

%C The row sums of this triangle coincide with the ones of array A212360, and they are given by A056665.

%F 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.

%e n\m 1    2      3       4       5       8      7     8 ...

%e 1   1

%e 2   2    1

%e 3   3    6      2

%e 4   4   24     36       6

%e 5   5   60    300     240      24

%e 6   6  180   1820    3900    1800     120

%e 7   7  378   9030   42000   50400   15120     72

%e 8   8  952  40824  357420  882000  670320 141120  5040

%e ...

%e Row n=9:   9 2088 169512 2610720 11677680 17781120 9313920 1451520 40320.

%e Row n=10: 10 4770 673560 17193960 128598624 345144240 355622400 136080000 16329600 362880.

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

%e a(5,3) = 120 + 180 = 300, from A212360(5,4) + A212360(5,5), because k(5,3,1)=4 and p(5,3)=2.

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

%e In general a(n,1)=n from the partition [n] providing the color signature (exponent), and the n color choices.

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

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

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

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

%K nonn,tabl,nice

%O 1,2

%A _Wolfdieter Lang_, Jun 27 2012