cp's OEIS Frontend

Also dimensions of free Lie algebras - see A059966, which is essentially the same sequence.

This sequence also represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1. This number does not depend on q and L is any divisor of q-1. See Theorem 5 and Corollary 3 of the Shallit and Vasiga paper: N=sum(eulerphi(d)/order(d,2)) where d is a divisor of 2^(q-1)-1 such that order(d,2)=L. - Tony Reix, Nov 17 2005

Except for a(0) = 1, Bau-Sen Du's [1985/2007] Table 1, p. 6, has this sequence as the 7th (rightmost) column. Other columns of the table include (but are not identified as) A006206-A006208. - Jonathan Vos Post, Jun 18 2007

"Number of binary Lyndon words" means: number of binary strings inequivalent modulo rotation (cyclic permutation) of the digits and not having a period smaller than n. This provides a link to A103314, since these strings correspond to the inequivalent zero-sum subsets of U_m (m-th roots of unity) obtained by taking the union of U_n (n|m) with 0 or more U_d (n | d, d | m) multiplied by some power of exp(i 2Pi/n) to make them mutually disjoint. (But not all zero-sum subsets of U_m are of that form.) - M. F. Hasler, Jan 14 2007

Also the number of dynamical cycles of period n of a threshold Boolean automata network which is a quasi-minimal positive circuit of size a multiple of n and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009

Also, the number of periodic points with (minimal) period n in the iteration of the tent map f(x):=2min{x,1-x} on the unit interval. - Pietro Majer, Sep 22 2009

Number of distinct cycles of minimal period n in a shift dynamical system associated with a totally disconnected hyperbolic iterated function system (see Barnsley link). - Michel Marcus, Oct 06 2013

From Jean-Christophe Hervé, Oct 26 2014: (Start)

For n > 0, a(n) is also the number of orbits of size n of the transform associated to the Kolakoski sequence A000002 (and this is true for any map with 2^n periodic points of period n). The Kolakoski transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the periodic points of the orbit of size 2. A027375(n) = n*a(n) gives the number of periodic points of minimal period n.

For n > 1, this sequence is equal to A059966 and to A060477, and for n = 1, a(1) = A059966(1)+1 = A060477(1)-1; this because the n-th term of all 3 sequences is equal to (1/n)*sum_{d|n} mu(n/d)*(2^d+e), with e = -1/0/1 for resp. A059966/this sequence/A060477, and sum_{d|n} mu(n/d) equals 1 for n = 1 and 0 for all n > 1. (End)

Warning: A000031 and A001037 are easily confused, since they have similar formulas.

From Petros Hadjicostas, Jul 14 2020: (Start)

Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.

Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) = A001221(N) being the number of distinct primes of N).

For N = 3, a = phi(3)/2 + omega(3) = 2/2 + 1 = 2 and b = omega(3) - 1 = 0. It follows that D(w, N=3) = A000079(w) = 2^w.

For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.

For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w.

He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)

Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).

For N = 3, we saw that a = 2 and b = 0, and hence d*(w, N=3) = a(w) = Sum_{k | w} (mu(k)/k) * 2^(w/k) / (w/k) = (1/w) * Sum_{k | w} mu(k) * 2^(w/k) for w >= 1. See Table 1 on p. 6 in Kam Cheong Au (2020). (End)

Bau-Sen Du (1985/1989)'s Table 1 has this sequence, denoted A_{n,1}, as the second column. - Jonathan Vos Post, Jun 18 2007

Apparently, for n > 2, the same as A072337. - Ralf Stephan, Feb 01 2004

a(n) is the number of prime period-n periodic orbits of Arnold's cat map. - Bruce Boghosian, Apr 26 2009

From Petros Hadjicostas, Nov 17 2017: (Start)

A first proof of the g.f., given below, can be obtained using the first of Vladeta Jovovic's formulae. If b(n) = A004146(n), then B(x) = Sum_{n >= 1} b(n)*x^n = x*(1 + x)/((1 - x)*(1 - 3*x + x^2)) (see the documentation for sequence A004146). From Jovovich's first formula, A(x) = Sum_{n >= 1} a(n)*x^n = Sum_{n >= 1} (1/n)*Sum_{d | n} mu(d)*b(n/d)*x^n. Letting m = n/d, we get A(x) = Sum_{d >= 1} (mu(d)/d)*Sum_{m >= 1} b(m)*(x^d)^m/m = Sum_{d >= 1} (mu(d)/d)*f(x^d), where f(y) = Sum_{m >= 1} b(m)*y^m/m = int(B(w)/w, w = 0..y) = int((1 + w)/((1 - w)*(1 - 3*w + w^2)), w = 0..y) = log((1 - y)^2/(1 - 3*y + y^2)) for |y| < (3 - sqrt(5))/2.

A second proof of the g.f. can be obtained using C. G. Bower's definition of the CHK transform of a sequence (e(n): n>=1) with g.f. E(x) (see the links below). If (c_k(n): n >= 1) = CHK_k(e(n): n >= 1), then (c_k(n): n >= 1) = (1/k)*(MOEBIUS*AIK)k (e_n: n >= 1) = (1/k)*Sum{d | gcd(n,k)} mu(d)*AIK_{k/d}(e(n/d): n multiple of d), where the * between MOEBIUS and AIK denotes Dirichlet convolution and (d_k(n): n >= 1) = AIK_k(e(n): n >= 1) has g.f. E(x)^k. (There is a typo in the given definition of CHK in the link.)

If C(x) is the g.f. of CHK(e(n): n >= 1) = Sum_{k = 1..n} CHK_k(e(n): n >= 1), then C(x) = Sum_{n>=1} Sum_{k = 1..n} c_k(n)*x^n = Sum_{k >= 1} (1/k) Sum_{n >= k} Sum_{d | gcd(n,k)} mu(d)*d_{k/d}(n/d)*x^n. Letting m = n/d and s = k/d and using the fact that E(0) = 0, we get C(x) = Sum_{d >= 1} (mu(d)/d)*Sum_{s >= 1} (1/s)*Sum_{m >= s} d_s(m)*(x^d)^m = Sum_{d >= 1} (mu(d)/d)*Sum_{s >= 1} E(x^d)^s. Thus, C(x) = -Sum_{d >= 1} (mu(d)/d)*log(1 - E(x^d)).

For the sequence (e(n): n >= 1) = (n: n >= 1), we have E(x) = Sum_{n>=1} n*x^n = x/(1 - x)^2, and thus A(x) = C(x) = -Sum_{d >= 1} (mu(d)/d)*log(1 - x/(1-x)^2), from which we can easily get the g.f. given in the formula section.

Apparently, for this sequence and for sequences A032165, A032166, A032167, the author assumes that C(0) = 0 (i.e., he assumes the CHK transform has no constant term), while for sequences A032164, A108529, and possibly others, he assumes that the CHK transform starts with the constant term 1 (i.e., he assumes C(x) = 1 - Sum_{d >= 1} (mu(d)/d)*log(1 - E(x^d))). (End)

From Petros Hadjicostas, Jul 13 2020: (Start)

We elaborate further on Michel Marcus's claim below. Consider his sequence (b(n): n >= 1) with b(1) = 3 and b(n) = a(n) for n >= 2.

Using the identity -Sum_{k >= 1} (mu(k)/k)*log(1 - x^k) = x for |x| < 1 and the g.f. of (a(n): n >= 1) below, we see that Sum_{n >= 1} b(n)*x^n = 3*x - a(1)*x + Sum_{n >= 1} a(n)*x^n = 2*x + Sum_{k >= 1} (mu(k)/k)*(2*log(1 - x^k) - log(1 - 3*x^k + x^(2*k))) = -Sum_{k >= 1} (mu(k)/k)*log(1 - 3*x^k + x^(2*k)).

Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.

Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) being the number of distinct primes of N).

For N = 6, a = phi(6)/2 + omega(6) = 2/2 + 2 = 3 and b = omega(6) - 1 = 1. It follows that D(w, N=6) = A001906(w+1) = Fibonacci(2*(w+1)).

For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.

For N = 6, we get that c(w, N=6) = A005248(w)/w.

He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)

Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).

For N = 6, we saw that a = 3 and b = 1, and hence d*(w, N=6) = b(w) for w >= 1 (as claimed by Michel Marcus below). See Table 1 on p. 6 in Kam Cheong Au (2020). (End)

Number of unlabeled (i.e., defined up to a rotation) maximal independent sets in the n-cycle graph. Also: Number of cyclic compositions of n in which each term is either 2 or 3.

(a(n)*n - A001608(n)) mod 2 is a binary sequence of period 14: [0,0,0,0,0,1,0,0,0,1,0,1,0,1]. - Richard Turk, Aug 25 2017

Let w = z + z^2 + z^3. Then 1 - z - z^2 - z^3 = 1 - 1w = (by the cyclotomic identity) Product_{n>=1} (1-w^n)^P(1,n), where P is the necklace polynomial. P is a counting function. Is f also a counting function?