|
| |
|
|
A060223
|
|
Number of orbits of length n under the map whose periodic points are counted by A000670.
|
|
84
|
|
|
|
1, 1, 1, 4, 18, 108, 778, 6756, 68220, 787472, 10224702, 147512052, 2340963570, 40527565260, 760095923082, 15352212731820, 332228417589720, 7668868648772700, 188085259069430744, 4884294069438337428, 133884389812214097774, 3863086904690670182596
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
A finite sequence is normal if it spans an initial interval of positive integers. The *-product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, (2 2 1) * (2 1 3) = (2 1 2 2 1 3). If Q is the set of compositions (finite sequences of positive integers) then (Q,*) is an Abelian group freely generated by a set P of prime sequences. The number of normal prime sequences of length n is equal to a(n). See example 2 and Mathematica program 2.
If N is the species (endofunctor over the category of finite sets and permutations) of unlabeled necklaces and N(S) represents the set of all non-isomorphic primitive necklaces of length n=|S|, then the numbers |N(S)| are equal to the numbers a(|S|) for any finite set S. This is because the number of orderless *-factorizations (see A034691 and A269134) of any finite sequence q is equal to the number of multiset partitions (see A007716 and A255906) of the multiset of prime factors of q. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = (1/n)* Sum_{d|n} mu(d)*A000670(n/d) for n > 0, where mu is A008683, the Moebius function. - Edited by Michel Marcus, Mar 30 2016
Let A = Sum_{q in P} Prod_i x_{q_i} = Sum_y c_y m(y) be the symmetric function whose coefficient of m(y) is equal to the number of permutations of the normal multiset [k]^y that belong to P, where the multiplicity of i in [k]^y is defined to be y_i. Then a(n) is the sum of c_y taken over all integer partitions of n. See example 3. - Gus Wiseman, Oct 14 2016
|
|
|
EXAMPLE
|
a(5) = 108 since A000670(5) is 541 and A000670(1) is 1, so there must be (541-1)/5 = 108 orbits of length 5.
The a(4) = 18 normal prime sequences are the columns:
[2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4]
[1 2 2 1 1 1 2 2 2 2 3 3 1 1 2 2 3 3]
[1 1 2 1 2 2 1 1 2 3 1 2 2 3 1 3 1 2]
[1 1 1 2 1 2 1 2 1 1 2 1 3 2 3 1 2 1].
The symmetric function A(x_1,x_2,x_3,...) expanded in terms of monomial symmetric functions m(y) (indexed by integer partitions y) is equal to:
A = m(1) +
m(11) +
(2*m(21) + 2*m(111) +
(m(22) + 2*m(31) + 9*m(211) + 6*m(1111)) +
(4*m(32) + 2*m(41) + 18*m(221) + 12*m(311) + 48*m(2111) + 24*m(11111)) +
(3*m(33) + 4*m(42) + 2*m(51) + 14*m(222) + 60*m(321) + 15*m(411) + 180*m(2211) + 80*m(3111) + 300*m(21111) + 120*m(111111)) + ... (End)
|
|
|
MATHEMATICA
|
a[n_] := DivisorSum[n, MoebiusMu[#] HurwitzLerchPhi[1/2, -n/#, 0]/2 &] / n; a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2016 *)
thufbin[{}, b_List]:=b; thufbin[a_List, {}]:=a; thufbin[a_List]:=a;
thufbin[{x_, a___}, {y_, b___}]:=Switch[Ordering[If[x=!=y, {x, y}, {thufbin[{a}, {x, b}], thufbin[{x, a}, {b}]}]], {1, 2}, Prepend[thufbin[{a}, {y, b}], x], {2, 1}, Prepend[thufbin[{x, a}, {b}], y]];
thufbin[a_List, b_List, c__List]:=thufbin[a, thufbin[b, c]];
priseqs[n_]:=Fold[Select, Tuples[Range[n], n], {Union[#]===Range[First[#]]&, Function[q, Select[Table[List[Take[q, {1, j}], Take[q, {j+1, n}]], {j, 1, n-1}], thufbin@@Sort[#]===q&, 1]==={}]}];
Table[Length[priseqs[n]], {n, 1, 7}] (* Gus Wiseman, Oct 14 2016 *)
|
|
|
PROG
|
b(n)={polcoeff(serlaplace(1/(2-exp(x+O(x*x^n)))), n)}
a(n)={if(n<1, n==0, sumdiv(n, d, moebius(d)*b(n/d))/n)} \\ Andrew Howroyd, Dec 12 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
