A075900 Expansion of g.f.: Product_{n>0} 1/(1 - 2^(n-1)*x^n).

1, 1, 3, 7, 19, 43, 115, 259, 659, 1523, 3731, 8531, 20883, 47379, 113043, 259219, 609683, 1385363, 3245459, 7344531, 17028499, 38579603, 88585619, 199845267, 457864595, 1028904339, 2339763603, 5256820115, 11896157587, 26626389395

Offset

0,3

Comments

Number of compositions of partitions of n. a(3) = 7: 3, 21, 12, 111, 2|1, 11|1, 1|1|1. - Alois P. Heinz, Sep 16 2019

Also the number of ways to split an integer composition of n into consecutive subsequences with weakly decreasing (or increasing) sums. - Gus Wiseman, Jul 13 2020

This sequence is obtained from the generalized Euler transform in A266964 by taking f(n) = 1, g(n) = 2^(n-1). - Seiichi Manyama, Aug 22 2020

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..3180 (terms 0..1000 from Alois P. Heinz)

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.

Formula

a(n) = Sum_{ partitions n = c_1 + ... + c_k } 2^(n-k). If p(n, m) = number of partitions of n into m parts, a(n) = Sum_{m=1..n} p(n, m)*2^(n-m).

G.f.: Sum_{n>=0} (a(n)/2^n)*x^n = Product_{n>0} 1/(1-x^n/2). - Vladeta Jovovic, Feb 11 2003

a(n) = 1/n*Sum_{k=1..n} A080267(k)*a(n-k). - Vladeta Jovovic, Feb 11 2003

G.f.: exp( Sum_{n>=1} x^n / (n*(1 - 2^n*x^n)) ). - Paul D. Hanna, Jan 13 2013

a(n) = s(1,n), a(0)=1, where s(m,n) = Sum_{k=m..n/2} 2^(k-1)*s(k, n-k) + 2^(n-1), s(n,n) = 2^(n-1), s(m,n)=0, m>. - Vladimir Kruchinin, Sep 06 2014

a(n) ~ 2^(n-2) * (Pi^2 - 6*log(2)^2)^(1/4) * exp(sqrt((Pi^2 - 6*log(2)^2)*n/3)) / (3^(1/4) * sqrt(Pi) * n^(3/4)). - Vaclav Kotesovec, Mar 09 2018

Example

From Gus Wiseman, Jul 13 2020: (Start)
The a(0) = 1 through a(4) = 19 splittings:
  ()  (1)  (2)      (3)          (4)
           (1,1)    (1,2)        (1,3)
           (1),(1)  (2,1)        (2,2)
                    (1,1,1)      (3,1)
                    (2),(1)      (1,1,2)
                    (1,1),(1)    (1,2,1)
                    (1),(1),(1)  (2,1,1)
                                 (2),(2)
                                 (3),(1)
                                 (1,1,1,1)
                                 (1,1),(2)
                                 (1,2),(1)
                                 (2),(1,1)
                                 (2,1),(1)
                                 (1,1),(1,1)
                                 (1,1,1),(1)
                                 (2),(1),(1)
                                 (1,1),(1),(1)
                                 (1),(1),(1),(1)
(End)

Maple

oo := 101; t1 := mul(1/(1-x^n/2), n=1..oo): t2 := series(t1, x, oo-1): t3 := seriestolist(t2): A075900 := n->2^n*t3[n+1];
with(combinat); A075900 := proc(n) local i, t1, t2, t3; t1 := partition(n); t2 := 0; for i from 1 to nops(t1) do t3 := t1[i]; t2 := t2+2^(n-nops(t3)); od: t2; end;

Mathematica

b[n_]:= b[n]= Sum[d*2^(n - n/d), {d, Divisors[n]}];
a[0]= 1; a[n_]:= a[n]= 1/n*Sum[b[k]*a[n-k], {k, n}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 20 2014, after Vladeta Jovovic, fixed by Vaclav Kotesovec, Mar 08 2018 *)

Prog

(PARI) {a(n)=polcoeff(prod(k=1, n, 1/(1-2^(k-1)*x^k+x*O(x^n))), n)} \\ Paul D. Hanna, Jan 13 2013
(PARI) {a(n)=polcoeff(exp(sum(k=1, n+1, x^k/(k*(1-2^k*x^k)+x*O(x^n)))), n)} \\ Paul D. Hanna, Jan 13 2013
(Maxima)
s(m, n):=if n<m then 0 else if n=m then 2^(n-1) else sum(2^(k-1)*s(k, n-k), k, m, ceiling(n/2))+2^(n-1);
makelist(s(1, n), n, 1, 27); /* Vladimir Kruchinin, Sep 06 2014 */
(Magma)
m:=80;
R<x>:=PowerSeriesRing(Integers(), m);
Coefficients(R!( 1/(&*[1-2^(j-1)*x^j: j in [1..m+2]]) )); // G. C. Greubel, Jan 25 2024
(SageMath)
m=80;
def A075900_list(prec):
    P.<x> = PowerSeriesRing(QQ, prec)
    return P( 1/product(1-2^(j-1)*x^j for j in range(1, m+1)) ).list()
A075900_list(m) # G. C. Greubel, Jan 25 2024

Crossrefs

Row sums of A327549.

The strict case is A304961.

Partitions of partitions are A001970.

Splittings with equal sums are A074854.

Splittings of compositions are A133494.

Splittings of partitions are A323583.

Splittings with distinct sums are A336127.

Starting with a reversed partition gives A316245.

Starting with a partition instead of composition gives A336136.

Cf. A006951, A063834, A300579, A317715, A319794, A323582, A327548, A336135.

Sequence in context: A192301 A350249 A055622 * A176500 A334099 A136041

Adjacent sequences: A075897 A075898 A075899 * A075901 A075902 A075903

Keyword

nonn

Author

N. J. A. Sloane, Oct 15 2002

Extensions

More terms from Vladeta Jovovic, Feb 11 2003

Status

approved