login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060223 Number of orbits of length n under the map whose periodic points are counted by A000670. 21
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

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

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

2m(21)+2m(111)+

m(22)+2m(31)+9m(211)+6m(1111)+

4m(32)+2m(41)+18m(221)+12m(311)+48m(2111)+24m(11111)+

3m(33)+4m(42)+2m(51)+14m(222)+60m(321)+15m(411)+180m(2211)+80m(3111)+300m(21111)+120m(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

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

Row sums of A254040.

Sequence in context: A241842 A306003 A214840 * A144085 A003708 A000986

Adjacent sequences:  A060220 A060221 A060222 * A060224 A060225 A060226

KEYWORD

easy,nonn

AUTHOR

Thomas Ward (t.ward(AT)uea.ac.uk), Mar 21 2001

EXTENSIONS

More terms from Alois P. Heinz, Jan 23 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 02:28 EST 2018. Contains 317120 sequences. (Running on oeis4.)