A060223 Number of orbits of length n under the map whose periodic points are counted by A000670.

1, 1, 1, 4, 18, 108, 778, 6756, 68220, 787472, 10224702, 147512052, 2340963570, 40527565260, 760095923082, 15352212731820, 332228417589720, 7668868648772700, 188085259069430744, 4884294069438337428, 133884389812214097774, 3863086904690670182596

Offset: 0

Author

Thomas Ward, Mar 21 2001

Keywords

• easy
• nonn

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)

Examples

			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)
		

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

Crossrefs

Cf. A000670, A034691 (multisets of compositions), A269134, A007716, A277427, A215474, A255906.

Row sums of A254040.

Programs

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 *)

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

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

Extensions

More terms from Alois P. Heinz, Jan 23 2015