|
%I #23 Dec 22 2017 16:15:55
%S 1,1,1,1,1,1,1,3,2,3,1,3,6,6,12,1,7,20,26,30,60,1,8,40,93,150,180,360,
%T 1,18,106,424,633,1050,1260,2520,1,22,304,1180,3260,5040,8400,10080,
%U 20160,1,46,731,4844,16212,29244,45360,75600,90720,181440
%N Triangle with entry a(n,m) giving the number of bracelets of n beads (dihedral D_n symmetry) with n colors available for each bead, but only m distinct fixed colors, say c[1],...,c[m], are present, with m from {1,...,n} and n>=1.
%C This triangle is obtained from the partition array A213939 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 number of bracelets of n beads (dihedral D_n symmetry) corresponding to the representative color multinomials obtained from all partitions of n with m parts by 'exponentiation', hence only m from the available n colors are present. As a representative multinomial of each of the p(n,m)=A008284(n,m) such m-color classes we take the one where the considered m part partition of n, [p[1],...,p[m]], written in nonincreasing order, is distributed as exponents on the color indices like c[1]^p[1]*...*c[m]^p[m]. That is only the first m colors from the n available ones are involved.
%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 A213939, and they are given by A213943.
%C Number of n-length bracelets w over a k-ary alphabet {a1,a2,...,ak} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 1, where #(w,x) counts the letters x in word w (bracelet analog of A226874). - _Andrew Howroyd_, Sep 26 2017
%H Andrew Howroyd, <a href="/A213940/b213940.txt">Table of n, a(n) for n = 1..1275</a>
%F a(n,m) = Sum_{j=1..p(n,m)}A213939(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) 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)=4, p(5,3)=2.
%e n\m 1 2 3 4 5 6 7 8 9 10 ...
%e 1 1
%e 2 1 1
%e 3 1 1 1
%e 4 1 3 2 3
%e 5 1 3 6 6 12
%e 6 1 7 20 26 30 60
%e 7 1 8 40 93 150 180 360
%e 8 1 18 106 424 633 1050 1260 2520
%e 9 1 22 304 1180 3260 5040 8400 10080 20160
%e 10 1 46 731 4844 16212 29244 45360 75600 90720 181440
%e ...
%e a(5,3) = 2 + 4 = 6, from A213939(5,4) + A213939(5,5), because k(5,3,1) = 4 and p(5,3) = 2.
%e a(2,1) = 1 because the partition [2] of n=2 with part number m=1 corresponds to the representative color multinomial (here monomial) c[1]^2 = c[1]*c[1], and there is one such representative bracelet. There is another bracelet color monomial in this class of n=2 colors where only m=1 color is active: c[2]*c[2]. See the triangle entry A213941(2,1)=2. The same holds for the necklace case.
%e a(3,1) = 1 from the color monomial representative c[1]^3. This class has 2 other members: c[2]^3 and c[3]^3. See A213941(3,1)=3. The same holds for the necklace case.
%e Like in the necklace case one has in general a(n,1)=1 and A213941(n,1) = n from the partition [n] providing the color signature and a representative c[1]^n.
%e a(3,2) = 1 from the representative color multinomial c[1]^2*c[2] (from the m=2 partition [2,1] of n=3) leading to just one representative bracelet (and necklace) cyclic(112) (when one uses j for color c[j]). The whole class consists of A213941(3,2)=6 bracelets (or necklaces): cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).
%e a(3,3) = 1. The representative color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). There is only one bracelet cyclic(1,2,3) which constitutes already the whole class (A213941(3,3)=1). The necklace cyclic(1,3,2) becomes equivalent under D_3.
%e a(4,2) = 3 from two representative color multinomials c[1]^3*c[2] and c[1]^2*c[2]^2 (from the two m=2 partitions of n=4: [3,1] and [2,2]). The first one has one representative bracelet, namely cyclic(1112), the second one leads to the two representative bracelets: cyclic(1122) and cyclic(1212). Together these are the 3 bracelets counted by a(4,2). The first color class c[.]^3*c[.] consists of 4*3=12 bracelets, when all 4 colors are used. The second one consists of 2*6=12 bracelets. Together they sum up to the 24 bracelets counted by A213941(4,2). In this example the necklace case does not differ from the bracelet one.
%o (PARI)
%o Cyc(v)={my(s=vecsum(v)); sumdiv(gcd(v), d, eulerphi(d)*(s/d)!/prod(i=1, #v, (v[i]/d)!))/s}
%o CPal(v)={my(odds=#select(t->t%2,v), s=vecsum(v)); if(odds>2, 0, ((s-odds)/2)!/prod(i=1, #v, (v[i]\2)!))}
%o T(n,k)={my(t=0); forpart(p=n, t+=Cyc(Vec(p))+CPal(Vec(p)), [1,n], [k,k]); t/2}
%o for(n=1, 10, for(k=1,n, print1(T(n,k), ", ")); print); \\ _Andrew Howroyd_, Sep 26 2017
%o (PARI) \\ faster version; here U is A226874 as vector of polynomials.
%o U(n)={Vec(serlaplace(prod(k=1, n, 1/(1-y*x^k/k!) + O(x*x^n))))}
%o T(n)={my(t=U(n)); vector(n, n, vector(n, k, ((1/n)*sumdiv(n, d, eulerphi(n/d) * polcoeff(t[d+1], k)) + if(n%2, sum(d=0, (n-1)/2, binomial((n-1)/2, d)*polcoeff(t[d+1], (k-1))), polcoeff(t[n/2+1], k) + sum(d=0, n/2-1, binomial(n/2-1, d)*(2^d + if(d%2, 0, binomial(d, d/2)))*polcoeff(t[n/2-d], k-2))/2))/2))}
%o { my(t=T(10)); for(n=1, #t, print(t[n])) } \\ _Andrew Howroyd_, Dec 22 2017
%Y Columns k=2..5 are A213942, A214307, A214309, A214311.
%Y Cf. A008284, A213939, A213941, A213943 (row sums), A226874, A152176.
%Y Cf. A213934 (cyclic symmetry).
%K nonn,tabl
%O 1,8
%A _Wolfdieter Lang_, Jul 20 2012
|
