|
%I #48 Feb 20 2021 02:38:31
%S 1,1,1,4,18,108,778,6756,68220,787472,10224702,147512052,2340963570,
%T 40527565260,760095923082,15352212731820,332228417589720,
%U 7668868648772700,188085259069430744,4884294069438337428,133884389812214097774,3863086904690670182596
%N Number of orbits of length n under the map whose periodic points are counted by A000670.
%C From _Gus Wiseman_, Oct 14 2016: (Start)
%C 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.
%C 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)
%H Alois P. Heinz, <a href="/A060223/b060223.txt">Table of n, a(n) for n = 0..200</a>
%H Yash Puri and Thomas Ward, <a href="http://www.fq.math.ca/Scanned/39-5/puri.pdf">A dynamical property unique to the Lucas sequence</a>, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.
%H Y. Puri and T. Ward, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
%H T. Ward, <a href="http://web.archive.org/web/20081002082625/http://www.mth.uea.ac.uk/~h720/research/files/integersequences.html">Exactly realizable sequences</a>
%F 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
%F 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
%F a(n) = Sum_{d|n} mu(d) * A019536(n/d) for n >= 1. - _Petros Hadjicostas_, Aug 19 2019
%e 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.
%e From _Gus Wiseman_, Oct 14 2016: (Start)
%e The a(4) = 18 normal prime sequences are the columns:
%e [2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4]
%e [1 2 2 1 1 1 2 2 2 2 3 3 1 1 2 2 3 3]
%e [1 1 2 1 2 2 1 1 2 3 1 2 2 3 1 3 1 2]
%e [1 1 1 2 1 2 1 2 1 1 2 1 3 2 3 1 2 1].
%e 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:
%e A = m(1) +
%e m(11) +
%e (2*m(21) + 2*m(111) +
%e (m(22) + 2*m(31) + 9*m(211) + 6*m(1111)) +
%e (4*m(32) + 2*m(41) + 18*m(221) + 12*m(311) + 48*m(2111) + 24*m(11111)) +
%e (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)
%t 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 *)
%t thufbin[{},b_List]:=b;thufbin[a_List,{}]:=a;thufbin[a_List]:=a;
%t 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]];
%t thufbin[a_List,b_List,c__List]:=thufbin[a,thufbin[b,c]];
%t 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]==={}]}];
%t Table[Length[priseqs[n]],{n,1,7}] (* _Gus Wiseman_, Oct 14 2016 *)
%o (PARI) \\ here b(n) is A000670
%o b(n)={polcoeff(serlaplace(1/(2-exp(x+O(x*x^n)))), n)}
%o a(n)={if(n<1, n==0, sumdiv(n, d, moebius(d)*b(n/d))/n)} \\ _Andrew Howroyd_, Dec 12 2017
%Y Cf. A000670, A034691 (multisets of compositions), A269134, A007716, A277427, A215474, A255906.
%Y Row sums of A254040.
%K easy,nonn
%O 0,4
%A _Thomas Ward_, Mar 21 2001
%E More terms from _Alois P. Heinz_, Jan 23 2015
|
