

A059966


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


110



1, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Dimensions of the homogeneous parts of the free Lie algebra with one generator in 1,2,3, etc. (Lie analog of the partition numbers).
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).
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
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
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
a(n) is also the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n.  Gus Wiseman, Dec 19 2017


REFERENCES

C. Reutenauer, Free Lie algebras, Clarendon press, Oxford (1993).


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
S. V. Duzhin, D. V. Pasechnik, Groups acting on necklaces and sandpile groups, Journal of Mathematical Sciences, August 2014, Volume 200, Issue 6, pp 690697. See page 85.  N. J. A. Sloane, Jun 30 2014
S. Kang, M. Kim, Free Lie Algebras, Generalized Witt Formula and the Denominator Identity, Journal of Algebra 183, 560594 (1996).
Michael J. Mossinghoff, Timothy S. Trudgian, A tale of two omegas, arXiv:1906.02847 [math.NT], 2019.
G. Niklasch, Some number theoretical constants: 1000digit values [Cached copy]
Jakob Oesinghaus, Quasisymmetric functions and the Chow ring of the stack of expanded pairs, arXiv:1806.10700 [math.AG], 2018.


FORMULA

G.f.: Product_{n>0} (1q^n)^a(n) = 1qq^2q^3q^4... = 21/(1q).
Inverse Euler transform of A011782.  Alois P. Heinz, Jun 23 2018
G.f.: Sum_{k>=1} mu(k)*log((1  x^k)/(1  2*x^k))/k.  Ilya Gutkovskiy, May 19 2019
a(n) ~ 2^n / n.  Vaclav Kotesovec, Aug 10 2019


EXAMPLE

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.
The sequence of Lyndon compositions organized by sum begins:
(1),
(2),
(3),(12),
(4),(13),(112),
(5),(14),(23),(113),(122),(1112),
(6),(15),(24),(114),(132),(123),(1113),(1122),(11112),
(7),(16),(25),(115),(34),(142),(124),(1114),(133),(223),(1213),(1132),(1123),(11113),(1222),(11212),(11122),(111112).  Gus Wiseman, Dec 19 2017


MATHEMATICA

Table[1/n Apply[Plus, Map[(MoebiusMu[n/# ](2^#  1)) &, Divisors[n]]], {n, 20}]
(* Second program: *)
Table[(1/n) DivisorSum[n, MoebiusMu[n/#] (2^#  1) &], {n, 35}] (* Michael De Vlieger, Jul 22 2019 *)


PROG

(Haskell)
a059966 n = sum (map (\x > a008683 (n `div` x) * a000225 x)
[d  d < [1..n], mod n d == 0]) `div` n
 Reinhard Zumkeller, Nov 18 2011


CROSSREFS

Apart from initial terms, same as A001037.
Cf. A000225, A000740, A008683, A008965, A011782, A060223, A185700, A228369, A269134 A281013, A296302, A296373.
Sequence in context: A304912 A018499 A107847 * A095718 A038751 A218543
Adjacent sequences: A059963 A059964 A059965 * A059967 A059968 A059969


KEYWORD

nonn,easy,nice


AUTHOR

Roland Bacher, Mar 05 2001


EXTENSIONS

Explicit formula from Paul D. Hanna, Apr 15 2002
Description corrected by Axel Kleinschmidt, Sep 15 2002


STATUS

approved



