login
Triangle with entry a(n,m) giving the number of necklaces of n beads (C_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.
3

%I #22 Jul 06 2018 17:10:16

%S 1,1,1,1,1,2,1,3,3,6,1,3,10,12,24,1,8,31,50,60,120,1,9,71,180,300,360,

%T 720,1,22,187,815,1260,2100,2520,5040,1,29,574,2324,6496,10080,16800,

%U 20160,40320,1,66,1373,9570,32268,58464,90720,151200,181440,362880

%N Triangle with entry a(n,m) giving the number of necklaces of n beads (C_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 A212359 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 number of necklaces of n beads (C_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 a nonincreasing way, is distributed as exponents over 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 A212359, and they are given by A072605.

%C Number of necklaces with n beads 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 (necklace analog of A226874). - _Andrew Howroyd_, Dec 20 2017

%H Andrew Howroyd, <a href="/A213934/b213934.txt">Table of n, a(n) for n = 1..1275</a>

%F a(n,m) = Sum_{j=1..p(n,m)}A212359(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.

%F T(n,k) = (1/n)*Sum_{d|n} phi(n/d)*A226874(d, k). - _Andrew Howroyd_, Dec 20 2017

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

%e 1 1

%e 2 1 1

%e 3 1 1 2

%e 4 1 3 3 6

%e 5 1 3 10 12 24

%e 6 1 8 31 50 60 120

%e 7 1 9 71 180 300 360 720

%e 8 1 22 187 815 1260 2100 2520 5040

%e 9 1 29 574 2324 6496 10080 16800 20160 40320

%e 10 1 66 1373 9570 32268 58464 90720 151200 181440 362880

%e ...

%e a(5,3) = 4 + 6 = 10, from A212359(5,4) + A212359(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 necklace. There is another necklace color monomial in this class of n=2 colors where only m=1 color is active: c[2]*c[2]. See the triangle entry A213935(2,1)=2.

%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 A213935(3,1)=3.

%e In general a(n,1)=1 and A213935(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 necklace cyclic(112) (when one uses j for color c[j]). The whole class consists of A213935(3,2)=6 necklaces: cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).

%e a(3,3)=2. The representative color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). There are the two non-equivalent representative necklaces cyclic(1,2,3) and cyclic(1,3,2) which constitute already the whole class (A213935(3,3)=2).

%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 necklace, namely cyclic(1112), the second one originates from two representative necklaces: cyclic(1122) and cyclic(1212). Together these are the 3 necklaces counted by a(4,2). The class with the first representative consists of 4*3=12 necklaces, when all 4 colors are used. The class of the second representative consists of 2*6=12 necklaces. Together they sum up to the 24 necklaces counted by A213935(4,2).

%t b[n_, i_, t_] := b[n, i, t] = If[t == 1, 1/n!, Sum[b[n - j, j, t - 1]/j!, {j, i, n/t}]];

%t a226874[n_, k_] := If[n k == 0, If[n == k, 1, 0], n! b[n, 1, k]];

%t T[n_, k_] := (1/n) Sum[EulerPhi[n/d] a226874[d, k], {d, Divisors[n]}];

%t Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 06 2018, after _Alois P. Heinz_ and _Andrew Howroyd_ *)

%o (PARI) \\ 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 C(n)={my(t=U(n)); vector(n, n, vector(n, k, (1/n)*sumdiv(n, d, eulerphi(n/d) * polcoeff(t[d+1], k))))}

%o { my(t=C(10)); for(n=1, #t, print(t[n])) } \\ _Andrew Howroyd_, Dec 20 2017

%Y Cf. A008284, A072605 (row sums), A212359, A213935.

%Y Cf. A213940 (bracelets), A226874 (words).

%K nonn,tabl

%O 1,6

%A _Wolfdieter Lang_, Jun 27 2012