A339677 - OEIS

%I #24 Jan 03 2021 21:10:18

%S 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 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 105,140,210,312,210,420,630,840,1260,2520,5040,0,1,4,9,14,8,28,56,70,84,140

%N 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 As in A212359, A072605, and A261600, for each partition, the base set of beads is fixed.

%C 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 Álvar Ibeas, <a href="/A339677/b339677.txt">First 25 rows, flattened</a>

%F Let L be a partition of n and d be the gcd of its parts. Then,

%F 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 T(n, L) = Sum_{v|d} mu(v) * A212359(n/v, L/v).

%F T(n, L) = n^(-1) * A036038(n, L) - Sum_{1<v|d} v^(-1) * T(n/v, L/v).

%F T(n,k) = A298941(A036035(n,k)) = A318808(A185974(n,k)). - _Andrew Howroyd_, Dec 14 2020

%e Array begins:

%e   k:  1 2 3 4 5  6  7  8  9 10  11  12  13  14  15

%e       --------------------------------------------

%e n=1:  1

%e n=2:  0 1

%e n=3:  0 1 2

%e n=4:  0 1 1 3 6

%e n=5:  0 1 2 4 6 12 24

%e n=6:  0 1 2 3 5 10 14 20 30 60 120

%e n=7:  0 1 3 5 6 15 20 30 30 60  90 120 180 360 720

%e 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 T(n, (1,...,1)) = A212359(n, (1,...,1)) = (n-1)!, counting necklaces with n beads, each in a different color.

%o (PARI)

%o C(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}

%o Row(n)=[C(Vec(p)) | p<-partitions(n)]

%o for(n=1, 7, print(Row(n))) \\ _Andrew Howroyd_, Dec 14 2020

%Y Cf. A036035, A036038, A072605, A185974, A212359, A261600 (row sums), A298941, A318808.

%K nonn,tabf

%O 1,6

%A _Álvar Ibeas_, Dec 12 2020