|
%I #63 Jan 25 2024 04:55:55
%S 1,1,3,7,19,43,115,259,659,1523,3731,8531,20883,47379,113043,259219,
%T 609683,1385363,3245459,7344531,17028499,38579603,88585619,199845267,
%U 457864595,1028904339,2339763603,5256820115,11896157587,26626389395
%N Expansion of g.f.: Product_{n>0} 1/(1 - 2^(n-1)*x^n).
%C 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
%C 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
%C 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
%H Vaclav Kotesovec, <a href="/A075900/b075900.txt">Table of n, a(n) for n = 0..3180</a> (terms 0..1000 from Alois P. Heinz)
%H N. J. A. Sloane and Thomas Wieder, <a href="https://arxiv.org/abs/math/0307064">The Number of Hierarchical Orderings</a>, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.
%F 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).
%F G.f.: Sum_{n>=0} (a(n)/2^n)*x^n = Product_{n>0} 1/(1-x^n/2). - _Vladeta Jovovic_, Feb 11 2003
%F a(n) = 1/n*Sum_{k=1..n} A080267(k)*a(n-k). - _Vladeta Jovovic_, Feb 11 2003
%F G.f.: exp( Sum_{n>=1} x^n / (n*(1 - 2^n*x^n)) ). - _Paul D. Hanna_, Jan 13 2013
%F 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
%F 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
%e From _Gus Wiseman_, Jul 13 2020: (Start)
%e The a(0) = 1 through a(4) = 19 splittings:
%e () (1) (2) (3) (4)
%e (1,1) (1,2) (1,3)
%e (1),(1) (2,1) (2,2)
%e (1,1,1) (3,1)
%e (2),(1) (1,1,2)
%e (1,1),(1) (1,2,1)
%e (1),(1),(1) (2,1,1)
%e (2),(2)
%e (3),(1)
%e (1,1,1,1)
%e (1,1),(2)
%e (1,2),(1)
%e (2),(1,1)
%e (2,1),(1)
%e (1,1),(1,1)
%e (1,1,1),(1)
%e (2),(1),(1)
%e (1,1),(1),(1)
%e (1),(1),(1),(1)
%e (End)
%p 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];
%p 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;
%t b[n_]:= b[n]= Sum[d*2^(n - n/d), {d, Divisors[n]}];
%t a[0]= 1; a[n_]:= a[n]= 1/n*Sum[b[k]*a[n-k], {k,n}];
%t Table[a[n], {n,0,30}] (* _Jean-François Alcover_, Mar 20 2014, after _Vladeta Jovovic_, fixed by _Vaclav Kotesovec_, Mar 08 2018 *)
%o (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
%o (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
%o (Maxima)
%o 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);
%o makelist(s(1,n),n,1,27); /* _Vladimir Kruchinin_, Sep 06 2014 */
%o (Magma)
%o m:=80;
%o R<x>:=PowerSeriesRing(Integers(), m);
%o Coefficients(R!( 1/(&*[1-2^(j-1)*x^j: j in [1..m+2]]) )); // _G. C. Greubel_, Jan 25 2024
%o (SageMath)
%o m=80;
%o def A075900_list(prec):
%o P.<x> = PowerSeriesRing(QQ, prec)
%o return P( 1/product(1-2^(j-1)*x^j for j in range(1,m+1)) ).list()
%o A075900_list(m) # _G. C. Greubel_, Jan 25 2024
%Y Row sums of A327549.
%Y The strict case is A304961.
%Y Partitions of partitions are A001970.
%Y Splittings with equal sums are A074854.
%Y Splittings of compositions are A133494.
%Y Splittings of partitions are A323583.
%Y Splittings with distinct sums are A336127.
%Y Starting with a reversed partition gives A316245.
%Y Starting with a partition instead of composition gives A336136.
%Y Cf. A006951, A063834, A300579, A317715, A319794, A323582, A327548, A336135.
%K nonn
%O 0,3
%A _N. J. A. Sloane_, Oct 15 2002
%E More terms from _Vladeta Jovovic_, Feb 11 2003
|
