A073776 a(n) = Sum_{k=1..n} -mu(k+1) * a(n-k), with a(0)=1.

1, 1, 2, 3, 6, 9, 17, 28, 50, 83, 147, 249, 435, 742, 1288, 2207, 3819, 6561, 11333, 19497, 33640, 57915, 99874, 172020, 296550, 510886, 880580, 1517226, 2614889, 4505745, 7765094, 13380640, 23059193, 39735969, 68476885, 118001888

Offset

0,3

Comments

Recurrence relation involves the Moebius function.

Radius of convergence of A(x) is r=0.5802946238073267...

Related limits are

lim_{n->infinity} a(n) r^n = 0.6303632342... and

lim_{n->infinity} a(n+1)/a(n) = 1.723262561763844...

From Gary W. Adamson, Aug 11 2016: (Start)

The definition in the heading follows from the INVERTi transform of (1, 2, 3, 6, 9, 17, ...) equals -mu(n) for n >= 2 (cf. A157658).

Then for example, a(6) = 17 = (1, 1, 0, 1, -1, 1) dot (9, 6, 3, 2, 1, 1) = (9 + 6 + 0 + 2 - 1 + 1); in agreement with the first example. (End)

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Yu Hin (Gary) Au, Decompositions of Unit Hypercubes and the Reversion of a Generalized Möbius Series, arXiv:2205.03680 [math.CO], 2022.

Formula

G.f.: A(x) = x / (Sum_{n>=1} mu(n)*x^n), A(0)=1, where mu(n) = Moebius function of n.

G.f. A(x) satisfies: x*A(x) = Sum_{n>=1} x^n*A(x)^n / A( x^n*A(x)^n ). - Paul D. Hanna, Apr 19 2016

Example

a(6) = -mu(2)a(5) - mu(3)a(4) - mu(4)a(3) - mu(5)a(2) - mu(6)a(1) - mu(7)a(0) = 9 + 6 + 0 + 2 - 1 + 1 = 17.
G.f.: A(x) = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 17*x^6 + 28*x^7 + 50*x^8 + 83*x^9 + 147*x^10 + 249*x^11 + 435*x^12 + ...
where
1/A(x) = 1 - x - x^2 - x^4 + x^5 - x^6 + x^9 - x^10 - x^12 + x^13 + x^14 - x^16 - x^18 + x^20 + x^21 - x^22 + x^25 - x^28 - x^29 - x^30 + ... + mu(n)*x^n +...
Also, g.f. A(x) satisfies:
x*A(x) = x*A(x)/A(x*A(x)) + x^2*A(x)^2/A(x^2*A(x)^2) + x^3*A(x)^3/A(x^3*A(x)^3) + x^4*A(x)^4/A(x^4*A(x)^4) + x^5*A(x)^5/A(x^5*A(x)^5) + ...

Mathematica

a[0] = 1; a[n_] := a[n] = Sum[-MoebiusMu[k + 1]*a[n - k], {k, 1, n}]; Array[a, 35, 0] (* Jean-François Alcover, Apr 11 2011 *)

Prog

(Haskell)
a073776 n = a073776_list !! (n-1)
a073776_list = 1 : f [1] where
   f xs = y : f (y : xs) where y = sum $ zipWith (*) xs ms
   ms = map negate $ tail a008683_list
-- Reinhard Zumkeller, Nov 03 2015
(PARI) {a(n) = my(A=[1, 1], F); for(i=1, n, A=concat(A, 0); F=Ser(A); A = Vec(sum(m=1, #A, subst(x/F, x, x^m*F^m))) ); A[n+1]}
for(n=0, 50, print1(a(n), ", ")) \\ Paul D. Hanna, Apr 19 2016

Crossrefs

Cf. A073777, A068341, A070965, A008683, A185694, A157658.

Sequence in context: A048814 A048815 A074045 * A129853 A374686 A095982

Adjacent sequences: A073773 A073774 A073775 * A073777 A073778 A073779

Keyword

easy,nice,nonn

Author

Paul D. Hanna, Aug 10 2002

Status

approved