login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 690-697. 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, 560-594 (1996).

Michael J. Mossinghoff, Timothy S. Trudgian, A tale of two omegas, arXiv:1906.02847 [math.NT], 2019.

G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]

Jakob Oesinghaus, Quasi-symmetric functions and the Chow ring of the stack of expanded pairs, arXiv:1806.10700 [math.AG], 2018.

FORMULA

G.f.: Product_{n>0} (1-q^n)^a(n) = 1-q-q^2-q^3-q^4-... = 2-1/(1-q).

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 9 17:18 EST 2019. Contains 329879 sequences. (Running on oeis4.)