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

%I #51 Aug 04 2022 05:52:45

%S 2,2,6,16,50,150,490,1600,5400,18450,64130,225264,800046,2865226,

%T 10341150,37566720,137270954,504171432,1860277042,6892317200,

%U 25631327190,95640829922,357975249026,1343650040256,5056424257500,19073789328750,72108867614796

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

%C 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.

%C The number of n-cycles in the graph of overlapping m-permutations where n <= m. - _Richard Ehrenborg_, Dec 10 2013

%C a(n) is divisible by n (cf. A268619), 6*a(n) is divisible by n^2 (cf. A268592). - _Max Alekseyev_, Feb 09 2016

%C 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

%H Charles R Greathouse IV, <a href="/A060165/b060165.txt">Table of n, a(n) for n = 1..1669</a>

%H R. Ehrenborg, S. Kitaev and E. Steingrimsson, <a href="http://arxiv.org/abs/1310.1520">Number of cycles in the graph of 312-avoiding permutations</a>, arXiv:1310.1520 [math.CO], 2013.

%H Y. Puri and T. Ward, <a href="http://www.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 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.

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

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

%F a(n) = A007727(n)/n. - _R. J. Mathar_, Jul 24 2017

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

%F a(n) ~ 4^n / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Aug 04 2022

%e 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.

%p with(numtheory):

%p a:= n-> add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/n:

%p seq(a(n), n=1..30); # _Alois P. Heinz_, Dec 10 2013

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

%o (PARI) a(n)=sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/n \\ _Charles R Greathouse IV_, Dec 10 2013

%o (Python)

%o from sympy import mobius, binomial, divisors

%o def a(n): return sum(mobius(n//d) * binomial(2*d, d) for d in divisors(n))//n

%o print([a(n) for n in range(1, 31)]) # _Indranil Ghosh_, Jul 24 2017

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

%K easy,nonn

%O 1,1

%A _Thomas Ward_, Mar 13 2001