A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 17, 13, 3, 1, 0, 9, 43, 50, 20, 3, 1, 0, 16, 124, 220, 136, 36, 4, 1, 0, 28, 338, 866, 773, 296, 52, 4, 1, 0, 51, 941, 3435, 4280, 2303, 596, 78, 5, 1, 0, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 0, 170, 7234, 51061
Offset: 1
Examples
T(6, 4) = 13: {aaabcd, aabacd, aabcad, abacad, aabbcd, aabcbd, aabcdb, aacbbd, aacbdb, ababcd, abacbd, acabdb, abcabd}.
From _Andrew Howroyd_, Apr 09 2017 (Start)
Triangle starts:
1
0 1
0 1 1
0 2 2 1
0 3 5 2 1
0 5 17 13 3 1
0 9 43 50 20 3 1
0 16 124 220 136 36 4 1
0 28 338 866 773 296 52 4 1
0 51 941 3435 4280 2303 596 78 5 1
(End)
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
Crossrefs
Programs
-
Mathematica
A[d_, n_] := A[d, n] = Which[n == 0, 1, n == 1, DivisorSum[d, x^# &], d == 1, Sum[StirlingS2[n, k] x^k, {k, 0, n}], True, Expand[A[d, 1] A[d, n-1] + D[A[d, n-1], x] x]]; B[n_, k_] := Coefficient[DivisorSum[n, EulerPhi[#] A[#, n/#]&]/n/x, x, k]; T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] B[#, k]&]; Table[T[n, k], {n, 1, 12}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jun 06 2018, after Andrew Howroyd and Robert A. Russell *) -
PARI
\\ here R(n) is A152175 as square matrix. R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))} T(n) = {my(M=R(n)); matrix(n, n, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))} { my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020
Formula
T(n, k) = Sum_{d|n} mu(n/d) * A152175(d, k). - Andrew Howroyd, Apr 09 2017
Comments