cp's OEIS Frontend

A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).

%I A059966 #97 Jul 16 2025 08:17:31
%S A059966 1,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,14532,27594,
%T A059966 52377,99858,190557,364722,698870,1342176,2580795,4971008,9586395,
%U A059966 18512790,35790267,69273666,134215680,260300986,505286415,981706806
%N A059966 a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).
%C A059966 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 A059966 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 A059966 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 A059966 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 A059966 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 A059966 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 A059966 a(n) is also the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n. - _Gus Wiseman_, Dec 19 2017
%C A059966 Mobius transform of A008965. - _Jianing Song_, Nov 13 2021
%C A059966 a(n) is the number of cycles of length n for the map x->1 - abs(2*x-1) applied on rationals 0<q<1. - _Michel Marcus_, Jul 16 2025
%D A059966 C. Reutenauer, Free Lie algebras, Clarendon press, Oxford (1993).
%H A059966 Reinhard Zumkeller, <a href="/A059966/b059966.txt">Table of n, a(n) for n = 1..1000</a>
%H A059966 Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, <a href="https://arxiv.org/abs/2505.06941">When are Hopf algebras determined by integer sequences?</a>, arXiv:2505.06941 [math.CO], 2025. See p. 17.
%H A059966 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 A059966 Seok-Jin Kang and Myung-Hwan 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 A059966 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 A059966 G. Niklasch, <a href="/A001692/a001692.html">Some number theoretical constants: 1000-digit values</a> [Cached copy]
%H A059966 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.
%H A059966 Robert Schneider, Andrew V. Sills, and Hunter Waldron, <a href="https://arxiv.org/abs/2501.18744">On the q-factorization of power series</a>, arXiv:2501.18744 [math.CO], 2025. See p. 6.
%F A059966 G.f.: Product_{n>0} (1-q^n)^a(n) = 1-q-q^2-q^3-q^4-... = 2-1/(1-q).
%F A059966 Inverse Euler transform of A011782. - _Alois P. Heinz_, Jun 23 2018
%F A059966 G.f.: Sum_{k>=1} mu(k)*log((1 - x^k)/(1 - 2*x^k))/k. - _Ilya Gutkovskiy_, May 19 2019
%F A059966 a(n) ~ 2^n / n. - _Vaclav Kotesovec_, Aug 10 2019
%F A059966 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 A059966 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 A059966 From _Gus Wiseman_, Dec 19 2017: (Start)
%e A059966 The sequence of Lyndon compositions organized by sum begins:
%e A059966   (1),
%e A059966   (2),
%e A059966   (3),(12),
%e A059966   (4),(13),(112),
%e A059966   (5),(14),(23),(113),(122),(1112),
%e A059966   (6),(15),(24),(114),(132),(123),(1113),(1122),(11112),
%e A059966   (7),(16),(25),(115),(34),(142),(124),(1114),(133),(223),(1213),(1132),(1123),(11113),(1222),(11212),(11122),(111112). (End)
%t A059966 Table[1/n Apply[Plus, Map[(MoebiusMu[n/# ](2^# - 1)) &, Divisors[n]]], {n, 20}]
%t A059966 (* Second program: *)
%t A059966 Table[(1/n) DivisorSum[n, MoebiusMu[n/#] (2^# - 1) &], {n, 35}] (* _Michael De Vlieger_, Jul 22 2019 *)
%o A059966 (Haskell)
%o A059966 a059966 n = sum (map (\x -> a008683 (n `div` x) * a000225 x)
%o A059966                      [d | d <- [1..n], mod n d == 0]) `div` n
%o A059966 -- _Reinhard Zumkeller_, Nov 18 2011
%o A059966 (Python)
%o A059966 from sympy import mobius, divisors
%o A059966 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 A059966 Apart from initial terms, same as A001037.
%Y A059966 Cf. A000225, A000740, A008683, A008965, A011782, A060223, A185700, A228369, A269134 A281013, A296302, A296373.
%K A059966 nonn,easy,nice
%O A059966 1,3
%A A059966 _Roland Bacher_, Mar 05 2001
%E A059966 Explicit formula from _Paul D. Hanna_, Apr 15 2002
%E A059966 Description corrected by Axel Kleinschmidt, Sep 15 2002