OFFSET
0,4
COMMENTS
From Gus Wiseman, Oct 14 2016: (Start)
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
Alois P. Heinz, Table of n, a(n) for n = 0..200
Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
T. Ward, Exactly realizable sequences
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
a(n) = Sum_{d|n} mu(d) * A019536(n/d) for n >= 1. - Petros Hadjicostas, Aug 19 2019
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.
From Gus Wiseman, Oct 14 2016: (Start)
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
(PARI) \\ here b(n) is A000670
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
Thomas Ward, Mar 21 2001
EXTENSIONS
More terms from Alois P. Heinz, Jan 23 2015
STATUS
approved