A050354 Number of ordered factorizations of n with one level of parentheses.

1, 1, 1, 3, 1, 5, 1, 9, 3, 5, 1, 21, 1, 5, 5, 27, 1, 21, 1, 21, 5, 5, 1, 81, 3, 5, 9, 21, 1, 37, 1, 81, 5, 5, 5, 111, 1, 5, 5, 81, 1, 37, 1, 21, 21, 5, 1, 297, 3, 21, 5, 21, 1, 81, 5, 81, 5, 5, 1, 201, 1, 5, 21, 243, 5, 37, 1, 21, 5, 37, 1, 513, 1, 5, 21, 21, 5, 37, 1, 297, 27, 5, 1, 201

Offset

1,4

Comments

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).

Dirichlet inverse of (A074206*A153881). - Mats Granvik, Jan 12 2009

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000

Formula

Dirichlet g.f.: (2-zeta(s))/(3-2*zeta(s)).

Recurrence for number of ordered factorizations of n with k-1 levels of parentheses is a(n) = k*Sum_{d|n, d<n} a(d), n>1, a(1)= 1/k. - Vladeta Jovovic, May 25 2005

a(p^k) = 3^(k-1).

a(A002110(n)) = A050351(n).

Sum_{k=1..n} a(k) ~ -n^r / (4*r*Zeta'(r)), where r = 2.185285451787482231198145140899733642292971552057774261555354324536... is the root of the equation Zeta(r) = 3/2. - Vaclav Kotesovec, Feb 02 2019

Example

For n=6, we have (6) = (3*2) = (2*3) = (3)*(2) = (2)*(3), thus a(6) = 5.

Mathematica

A[n_]:=If[n==1, n/2, 2*Sum[If[d<n, A[d], 0], {d, Divisors[n]}]]; Table[If[n==1, n, A[n]], {n, 1, 100}] (* Indranil Ghosh, May 19 2017 *)

Prog

(PARI)
A050354aux(n) = if(1==n, n/2, 2*sumdiv(n, d, if(d<n, A050354aux(d), 0)));
A050354(n) = if(1==n, n, A050354aux(n)); \\ Antti Karttunen, May 19 2017, after Jovovic's general recurrence.
(Sage)
def A(n): return 1/2 if n==1 else 2*sum(A(d) for d in divisors(n) if d<n)
def a(n): return 1 if n==1 else A(n)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, May 19 2017, after Antti Karttunen's PARI program

Crossrefs

Cf. A002033, A050351, A050352, A050353, A050355, A050356, A050357, A050358, A050359.

Sequence in context: A240535 A262397 A155912 * A146434 A126213 A146935

Adjacent sequences: A050351 A050352 A050353 * A050355 A050356 A050357

Keyword

nonn

Author

Christian G. Bower, Oct 15 1999

Extensions

Duplicate comment removed by R. J. Mathar, Jul 15 2010

Status

approved