|
%I #87 Jul 18 2022 19:33:53
%S 1,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,14532,27594,
%T 52377,99858,190557,364722,698870,1342176,2580795,4971008,9586395,
%U 18512790,35790267,69273666,134215680,260300986,505286415,981706806
%N a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).
%C Dimensions of the homogeneous parts of the free Lie algebra with one generator in 1,2,3, etc. (Lie analog of the partition numbers).
%C This sequence is the Lie analog of the partition sequence (which gives the dimensions of the homogeneous polynomials with one generator in each degree) or similarly, of the partitions into distinct (or odd numbers) (which gives the dimensions of the homogeneous parts of the exterior algebra with one generator in each dimension).
%C The number of cycles of length n of rectangle shapes in the process of repeatedly cutting a square off the end of the rectangle. For example, the one cycle of length 1 is the golden rectangle. - David Pasino (davepasino(AT)yahoo.com), Jan 29 2009
%C In music, the number of distinct rhythms, at a given tempo, produced by a continuous repetition of measures with identical patterns of 1's and 0's (where 0 means no beat, and 1 means one beat), where each measure allows for n possible beats of uniform character, and when counted under these two conditions: (i) the starting and ending times for the measure are unknown or irrelevant and (ii) identical rhythms that can be produced by using a measure with fewer than n possible beats are excluded from the count. - _Richard R. Forberg_, Apr 22 2013
%C Richard R. Forberg's comment does not hold for n=1 because a(1)=1 but there are the two possible rhythms: "0" and "1". - _Herbert Kociemba_, Oct 24 2016
%C The comment does hold for n=1 as the rhythm "0" can be produced by using a measure of 0 beats and so is properly excluded from a(1)=1 by condition (ii) of the comment. - _Travis Scott_, May 28 2022
%C a(n) is also the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n. - _Gus Wiseman_, Dec 19 2017
%C Mobius transform of A008965. - _Jianing Song_, Nov 13 2021
%D C. Reutenauer, Free Lie algebras, Clarendon press, Oxford (1993).
%H Reinhard Zumkeller, <a href="/A059966/b059966.txt">Table of n, a(n) for n = 1..1000</a>
%H S. V. Duzhin and D. V. Pasechnik, <a href="ftp://pdmi.ras.ru/pub/publicat/znsl/v421/p081.pdf">Groups acting on necklaces and sandpile groups</a>, Journal of Mathematical Sciences, August 2014, Volume 200, Issue 6, pp 690-697. See page 85. - N. J. A. Sloane, Jun 30 2014
%H S. Kang and M. Kim, <a href="https://doi.org/10.1006/jabr.1996.0233">Free Lie Algebras, Generalized Witt Formula and the Denominator Identity</a>, Journal of Algebra 183, 560-594 (1996).
%H Michael J. Mossinghoff and Timothy S. Trudgian, <a href="https://arxiv.org/abs/1906.02847">A tale of two omegas</a>, arXiv:1906.02847 [math.NT], 2019.
%H G. Niklasch, <a href="/A001692/a001692.html">Some number theoretical constants: 1000-digit values</a> [Cached copy]
%H Jakob Oesinghaus, <a href="https://arxiv.org/abs/1806.10700">Quasi-symmetric functions and the Chow ring of the stack of expanded pairs</a>, arXiv:1806.10700 [math.AG], 2018.
%F G.f.: Product_{n>0} (1-q^n)^a(n) = 1-q-q^2-q^3-q^4-... = 2-1/(1-q).
%F Inverse Euler transform of A011782. - _Alois P. Heinz_, Jun 23 2018
%F G.f.: Sum_{k>=1} mu(k)*log((1 - x^k)/(1 - 2*x^k))/k. - _Ilya Gutkovskiy_, May 19 2019
%F a(n) ~ 2^n / n. - _Vaclav Kotesovec_, Aug 10 2019
%F Dirichlet g.f.: f(s+1)/zeta(s+1) - 1, where f(s) = Sum_{n>=1} 2^n/n^s. - _Jianing Song_, Nov 13 2021
%e a(4)=3: the 3 elements [a,c], [a[a,b]] and d form a basis of all homogeneous elements of degree 4 in the free Lie algebra with generators a of degree 1, b of degree 2, c of degree 3 and d of degree 4.
%e From _Gus Wiseman_, Dec 19 2017: (Start)
%e The sequence of Lyndon compositions organized by sum begins:
%e (1),
%e (2),
%e (3),(12),
%e (4),(13),(112),
%e (5),(14),(23),(113),(122),(1112),
%e (6),(15),(24),(114),(132),(123),(1113),(1122),(11112),
%e (7),(16),(25),(115),(34),(142),(124),(1114),(133),(223),(1213),(1132),(1123), (11113),(1222),(11212),(11122),(111112). (End)
%t Table[1/n Apply[Plus, Map[(MoebiusMu[n/# ](2^# - 1)) &, Divisors[n]]], {n, 20}]
%t (* Second program: *)
%t Table[(1/n) DivisorSum[n, MoebiusMu[n/#] (2^# - 1) &], {n, 35}] (* _Michael De Vlieger_, Jul 22 2019 *)
%o (Haskell)
%o a059966 n = sum (map (\x -> a008683 (n `div` x) * a000225 x)
%o [d | d <- [1..n], mod n d == 0]) `div` n
%o -- _Reinhard Zumkeller_, Nov 18 2011
%o (Python)
%o from sympy import mobius, divisors
%o def A059966(n): return sum(mobius(n//d)*(2**d-1) for d in divisors(n,generator=True))//n # _Chai Wah Wu_, Feb 03 2022
%Y Apart from initial terms, same as A001037.
%Y Cf. A000225, A000740, A008683, A008965, A011782, A060223, A185700, A228369, A269134 A281013, A296302, A296373.
%K nonn,easy,nice
%O 1,3
%A _Roland Bacher_, Mar 05 2001
%E Explicit formula from _Paul D. Hanna_, Apr 15 2002
%E Description corrected by Axel Kleinschmidt, Sep 15 2002
|
