|
| |
|
|
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.
|
|
3
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
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
|
|
|
LINKS
|
|
|
|
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.
|
|
|
EXAMPLE
|
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).
|
|
|
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]}];
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
