cp's OEIS Frontend

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.

%I A339677 #24 Jan 03 2021 21:10:18
%S A339677 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,
%T A339677 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,
%U A339677 105,140,210,312,210,420,630,840,1260,2520,5040,0,1,4,9,14,8,28,56,70,84,140
%N 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.
%C A339677 As in A212359, A072605, and A261600, for each partition, the base set of beads is fixed.
%C A339677 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.
%H A339677 Álvar Ibeas, <a href="/A339677/b339677.txt">First 25 rows, flattened</a>
%F A339677 Let L be a partition of n and d be the gcd of its parts. Then,
%F A339677 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.
%F A339677 T(n, L) = Sum_{v|d} mu(v) * A212359(n/v, L/v).
%F A339677 T(n, L) = n^(-1) * A036038(n, L) - Sum_{1<v|d} v^(-1) * T(n/v, L/v).
%F A339677 T(n,k) = A298941(A036035(n,k)) = A318808(A185974(n,k)). - _Andrew Howroyd_, Dec 14 2020
%e A339677 Array begins:
%e A339677   k:  1 2 3 4 5  6  7  8  9 10  11  12  13  14  15
%e A339677       --------------------------------------------
%e A339677 n=1:  1
%e A339677 n=2:  0 1
%e A339677 n=3:  0 1 2
%e A339677 n=4:  0 1 1 3 6
%e A339677 n=5:  0 1 2 4 6 12 24
%e A339677 n=6:  0 1 2 3 5 10 14 20 30 60 120
%e A339677 n=7:  0 1 3 5 6 15 20 30 30 60  90 120 180 360 720
%e A339677 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.
%e A339677 T(n, (1,...,1)) = A212359(n, (1,...,1)) = (n-1)!, counting necklaces with n beads, each in a different color.
%o A339677 (PARI)
%o A339677 C(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
%o A339677 Row(n)=[C(Vec(p)) | p<-partitions(n)]
%o A339677 for(n=1, 7, print(Row(n))) \\ _Andrew Howroyd_, Dec 14 2020
%Y A339677 Cf. A036035, A036038, A072605, A185974, A212359, A261600 (row sums), A298941, A318808.
%K A339677 nonn,tabf
%O A339677 1,6
%A A339677 _Álvar Ibeas_, Dec 12 2020