A213934 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.

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, 720, 1, 22, 187, 815, 1260, 2100, 2520, 5040, 1, 29, 574, 2324, 6496, 10080, 16800, 20160, 40320, 1, 66, 1373, 9570, 32268, 58464, 90720, 151200, 181440, 362880

Offset: 1

Author

Wolfdieter Lang, Jun 27 2012

Keywords

• nonn
• tabl

Comments

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.

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.

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.

The row sums of this triangle coincide with the ones of array A212359, and they are given by A072605.

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

Examples

			n\m  1  2    3    4     5     6     7      8      9     10 ...
1    1
2    1  1
3    1  1    2
4    1  3    3    6
5    1  3   10   12    24
6    1  8   31   50    60   120
7    1  9   71  180   300   360   720
8    1 22  187  815  1260  2100  2520   5040
9    1 29  574 2324  6496 10080 16800  20160  40320
10   1 66 1373 9570 32268 58464 90720 151200 181440 362880
...
a(5,3) = 4 + 6 = 10, from A212359(5,4) + A212359(5,5), because k(5,3,1) = 4 and p(5,3) = 2.
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.
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.
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.
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).
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).
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).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275

Crossrefs

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

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

Programs

Mathematica

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}]];
a226874[n_, k_] := If[n k == 0, If[n == k, 1, 0], n! b[n, 1, k]];
T[n_, k_] := (1/n) Sum[EulerPhi[n/d] a226874[d, k], {d, Divisors[n]}];
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 *)

PARI

\\ here U is A226874 as vector of polynomials.
U(n)={Vec(serlaplace(prod(k=1, n, 1/(1-y*x^k/k!) + O(x*x^n))))}
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))))}
{ my(t=C(10)); for(n=1, #t, print(t[n])) } \\ Andrew Howroyd, Dec 20 2017

Formula

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.

T(n,k) = (1/n)*Sum_{d|n} phi(n/d)*A226874(d, k). - Andrew Howroyd, Dec 20 2017