login
A339677
Partition array: T(n, k) is the number of aperiodic necklaces (Lyndon words) on a multiset of colored beads (of size n) whose color multiplicities form the k-th partition of n in Abramowitz-Stegun order.
2
1, 0, 1, 0, 1, 2, 0, 1, 1, 3, 6, 0, 1, 2, 4, 6, 12, 24, 0, 1, 2, 3, 5, 10, 14, 20, 30, 60, 120, 0, 1, 3, 5, 6, 15, 20, 30, 30, 60, 90, 120, 180, 360, 720, 0, 1, 3, 7, 8, 7, 21, 35, 51, 70, 42, 105, 140, 210, 312, 210, 420, 630, 840, 1260, 2520, 5040, 0, 1, 4, 9, 14, 8, 28, 56, 70, 84, 140
OFFSET
1,6
COMMENTS
As in A212359, A072605, and A261600, for each partition, the base set of beads is fixed.
Abuse of notation: we write T(n, L) for T(n, k), where L is the k-th partition of n in A-St order. We do accordingly for A036038 and A212359.
LINKS
FORMULA
Let L be a partition of n and d be the gcd of its parts. Then,
T(n, L) = n^(-1) * Sum_{v|d} mu(v) * A036038(n/v, L/v), where L/v is the partition obtained from L after dividing each part by v.
T(n, L) = Sum_{v|d} mu(v) * A212359(n/v, L/v).
T(n, L) = n^(-1) * A036038(n, L) - Sum_{1<v|d} v^(-1) * T(n/v, L/v).
T(n,k) = A298941(A036035(n,k)) = A318808(A185974(n,k)). - Andrew Howroyd, Dec 14 2020
EXAMPLE
Array begins:
k: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
--------------------------------------------
n=1: 1
n=2: 0 1
n=3: 0 1 2
n=4: 0 1 1 3 6
n=5: 0 1 2 4 6 12 24
n=6: 0 1 2 3 5 10 14 20 30 60 120
n=7: 0 1 3 5 6 15 20 30 30 60 90 120 180 360 720
Consider partition L = (4, 2). There are 3 = A212359(6, L) necklaces on the bead set {a^4, b^2}: (aaaabb), (aaabab), and (aabaab). The latter has a period smaller than its size (3 < 6), whereas the other two are aperiodic. Hence, T(6, L) = 2.
T(n, (1,...,1)) = A212359(n, (1,...,1)) = (n-1)!, counting necklaces with n beads, each in a different color.
PROG
(PARI)
C(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
Row(n)=[C(Vec(p)) | p<-partitions(n)]
for(n=1, 7, print(Row(n))) \\ Andrew Howroyd, Dec 14 2020
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Álvar Ibeas, Dec 12 2020
STATUS
approved