|
|
A075900
|
|
Expansion of g.f.: Product_{n>0} 1/(1 - 2^(n-1)*x^n).
|
|
46
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
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
|
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}];
|
|
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);
(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;
P.<x> = PowerSeriesRing(QQ, prec)
return P( 1/product(1-2^(j-1)*x^j for j in range(1, m+1)) ).list()
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|