OFFSET
1,2
COMMENTS
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.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1275
FORMULA
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
EXAMPLE
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.
MATHEMATICA
(* 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 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Wolfdieter Lang, Jul 20 2012
STATUS
approved