A075900 - OEIS

%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