|
|
A059966
|
|
a(n) = (1/n) * Sum_{ d divides n } mu(n/d) * (2^d - 1).
|
|
143
|
|
|
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
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
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
|
Michael J. Mossinghoff and Timothy S. Trudgian, A tale of two omegas, arXiv:1906.02847 [math.NT], 2019.
|
|
FORMULA
|
G.f.: Product_{n>0} (1-q^n)^a(n) = 1-q-q^2-q^3-q^4-... = 2-1/(1-q).
G.f.: Sum_{k>=1} mu(k)*log((1 - x^k)/(1 - 2*x^k))/k. - Ilya Gutkovskiy, May 19 2019
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
|
|
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). (End)
|
|
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
(Python)
from sympy import mobius, divisors
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
|
|
CROSSREFS
|
Apart from initial terms, same as A001037.
Cf. A000225, A000740, A008683, A008965, A011782, A060223, A185700, A228369, A269134 A281013, A296302, A296373.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Description corrected by Axel Kleinschmidt, Sep 15 2002
|
|
STATUS
|
approved
|
|
|
|