A060165 Number of orbits of length n under the map whose periodic points are counted by A000984.

2, 2, 6, 16, 50, 150, 490, 1600, 5400, 18450, 64130, 225264, 800046, 2865226, 10341150, 37566720, 137270954, 504171432, 1860277042, 6892317200, 25631327190, 95640829922, 357975249026, 1343650040256, 5056424257500, 19073789328750, 72108867614796

Offset: 1

Author

Thomas Ward, Mar 13 2001

Keywords

• easy
• nonn

Comments

The sequence A000984 seems to record the number of points of period n under a map. The number of orbits of length n for this map gives the sequence above.

The number of n-cycles in the graph of overlapping m-permutations where n <= m. - Richard Ehrenborg, Dec 10 2013

a(n) is divisible by n (cf. A268619), 6*a(n) is divisible by n^2 (cf. A268592). - Max Alekseyev, Feb 09 2016

Apparently the number of Lyndon words of length n with a 4-letter alphabet (see A027377) where the first letter of the alphabet appears with the same frequency as the second of the alphabet. E.g a(1)=2 counts the words (2), (3), a(2)= 2 counts (01) (23), a(3)=6 counts (021) (031) (012) (013) (223) (233). R. J. Mathar, Nov 04 2021

Examples

			a(5) = 50 because if a map has A000984 as its periodic points, then it would have 2 fixed points and 252 points of period 5, hence 50 orbits of length 5.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..1669
• R. Ehrenborg, S. Kitaev and E. Steingrimsson, Number of cycles in the graph of 312-avoiding permutations, arXiv:1310.1520 [math.CO], 2013.
• Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
• Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.

Crossrefs

Cf. A000984, A007727, A060164, A060166, A060167, A060168, A060169, A060170, A060171, A060172, A060173.

Programs

Maple

with(numtheory):
a:= n-> add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/n:
seq(a(n), n=1..30); # Alois P. Heinz, Dec 10 2013

Mathematica

a[n_] := (1/n)*Sum[MoebiusMu[d]*Binomial[2*n/d, n/d], {d, Divisors[n]}]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jul 16 2015 *)

PARI

a(n)=sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/n \\ Charles R Greathouse IV, Dec 10 2013

Python

from sympy import mobius, binomial, divisors
def a(n): return sum(mobius(n//d) * binomial(2*d, d) for d in divisors(n))//n
print([a(n) for n in range(1, 31)])  # Indranil Ghosh, Jul 24 2017

Formula

a(n) = (1/n) * Sum_{d|n} mu(d) A000984(n/d) with mu = A008683.

a(n) = 2*A022553(n).

a(n) = A007727(n)/n. - R. J. Mathar, Jul 24 2017

G.f.: 2 * Sum_{k>=1} mu(k)*log((1 - sqrt(1 - 4*x^k))/(2*x^k))/k. - Ilya Gutkovskiy, May 18 2019

a(n) ~ 4^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Aug 04 2022