|
%I #25 Oct 08 2017 12:37:24
%S 1,2,1,3,6,1,4,24,24,3,5,60,180,120,12,6,165,1120,2040,900,60,7,336,
%T 5145,21420,25200,7560,360,8,784,23016,183330,442680,335160,70560,
%U 2520,9,1584,91056,1320480,5846400,8890560,4656960,725760,20160,10
%N 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.
%C 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.
%C 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.
%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. See a link in A213938 for representative multisets for given signature used to define color multinomials.
%C The row sums of this triangle coincide with the ones of array A213941, and they are given by A081721.
%H Andrew Howroyd, <a href="/A214306/b214306.txt">Table of n, a(n) for n = 1..1275</a>
%F 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.
%F a(n,m) = binomial(n,m) * A273891(n,m). - _Andrew Howroyd_, Mar 25 2017
%e n\m 1 2 3 4 5 8 7 8 9
%e 1 1
%e 2 2 1
%e 3 3 6 1
%e 4 4 24 24 3
%e 5 5 60 180 120 12
%e 6 6 165 1120 2040 900 60
%e 7 7 336 5145 21420 25200 7560 360
%e 8 8 784 23016 183330 442680 33516 70560 2520
%e 9 9 1584 91056 1320480 5846400 8890560 4656960 725760 20160
%e ...
%e Row n=10: 10, 3420, 357480, 8691480, 64420272, 172609920, 177811200, 68040000, 8164800, 181440;
%e Row n=11: 11, 6820, 1327095, 52727400, 622175400, 2714009760, 4837417200, 3592512000, 1047816000, 99792000, 1814400.
%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 bracelet in question is cyclic(12) (we use j for color c[j] in these examples). The same holds for the necklace case.
%e 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.
%e 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.
%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 bracelets are cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332). The same holds for the necklace case.
%e 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.
%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 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.
%e 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.
%t (* 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 T[n_, k_] := Binomial[n, k]*Sum[(-1)^i * Binomial[k, i]*t[n, k - i], {i, 0, k - 1}];
%t Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Oct 08 2017, after _Andrew Howroyd_ *)
%Y Cf. A081721, A212360 (necklaces), A213941, A273891.
%K nonn,tabl
%O 1,2
%A _Wolfdieter Lang_, Jul 20 2012
|
