A318808 -id:A318808 - cp's OEIS frontend

A318810 Number of necklace permutations of a multiset whose multiplicities are the prime indices of n > 1.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 2, 6, 1, 6, 1, 4, 3, 1, 1, 12, 4, 1, 16, 5, 1, 10, 1, 24, 3, 1, 5, 30, 1, 1, 4, 20, 1, 15, 1, 6, 30, 1, 1, 60, 10, 20, 4, 7, 1, 90, 7, 30, 5, 1, 1, 60, 1, 1, 54, 120, 10, 21, 1, 8, 5, 35, 1, 180, 1, 1, 70, 9, 14, 28, 1

Offset: 1

Gus Wiseman, Sep 04 2018

nonn

This multiset is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.
A necklace is a finite sequence that is minimal among its cyclic permutations.
a(1) = 1 by convention.

			The a(21) = 3 necklace permutations of {1,1,1,1,2,2} are: (111122), (111212), (112112). Only the first two are Lyndon words, the third being periodic.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Cf. A000670, A008480, A019536, A056239, A060223, A112798, A298941, A305936, A318762, A318808, A318809.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Permutations[nrmptn[n]],neckQ]],{n,2,100}]

sig(n)={my(f=factor(n)); concat(vector(#f~, i, vector(f[i,2], j, primepi(f[i,1]))))}
count(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, eulerphi(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
a(n)={if(n==1, 1, count(sig(n)))} \\ Andrew Howroyd, Dec 08 2018

a(p) = 1 for prime p. - Andrew Howroyd, Dec 08 2018

a(1) inserted by Andrew Howroyd, Dec 08 2018

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.

Original entry on oeis.org

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

Álvar Ibeas, Dec 12 2020

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.

			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.

Álvar Ibeas, First 25 rows, flattened

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

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

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_{1T(n,k) = A298941(A036035(n,k)) = A318808(A185974(n,k)). - Andrew Howroyd, Dec 14 2020

Showing 1-2 of 2 results.

cp's OEIS Frontend

A318810 Number of necklace permutations of a multiset whose multiplicities are the prime indices of n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions