|
%I #31 May 01 2023 12:58:36
%S 1,1,1,0,2,1,1,1,3,1,0,2,3,4,1,0,2,4,6,5,1,0,0,6,8,10,6,1,1,1,3,13,15,
%T 15,7,1,0,2,3,12,25,26,21,8,1,0,2,6,10,31,45,42,28,9,1,0,0,6,16,30,66,
%U 77,64,36,10,1,0,2,4,18,40,76,126,126,93,45,11,1,0,0,6,16,50,96,168,224,198,130,55,12,1
%N Triangle read by rows: T(n,k) is the number of compositions of n as the sum of k integral powers of 2.
%C Upper triangular region of the table A073265 read by rows. - _Emeric Deutsch_, Feb 04 2005
%C Also the convolution triangle of A209229. - _Peter Luschny_, Oct 07 2022
%H G. C. Greubel, <a href="/A073266/b073266.txt">Rows n = 1..100 of triangle, flattened</a>
%H S. Lehr, J. Shallit and J. Tromp, <a href="https://doi.org/10.1016/0304-3975(95)00234-0">On the vector space of the automatic reals</a>, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.
%F T(n, k) = coefficient of x^n in the formal power series (x + x^2 + x^4 + x^8 + x^16 + ...)^k. - _Emeric Deutsch_, Feb 04 2005
%F T(0, k) = T(n, 0) = 0, T(n, k) = 0 if k > n, T(n, 1) = 1 if n = 2^m, 0 otherwise and in other cases T(n, k) = Sum_{i=0..floor(log_2(n-1))} T(n-(2^i), k-1). - _Emeric Deutsch_, Feb 04 2005
%F Sum_{k=0..n} T(n,k) = A023359(n). - _Philippe Deléham_, Nov 04 2006
%e T(6,3) = 4 because there are four ordered partitions of 6 into 3 powers of 2, namely: 4+1+1, 1+4+1, 1+1+4 and 2+2+2.
%e Triangle begins:
%e 1;
%e 1, 1;
%e 0, 2, 1;
%e 1, 1, 3, 1;
%e 0, 2, 3, 4, 1;
%e 0, 2, 4, 6, 5, 1;
%p b:= proc(n) option remember; expand(`if`(n=0, 1,
%p add(b(n-2^j)*x, j=0..ilog2(n))))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n)):
%p seq(T(n), n=1..14); # _Alois P. Heinz_, Mar 06 2020
%p # Uses function PMatrix from A357368. Adds a row above and a column to the left.
%p PMatrix(10, n -> if n = 2^ilog2(n) then 1 else 0 fi); # _Peter Luschny_, Oct 07 2022
%t m:= 10; T[n_, k_]:= T[n, k]= Coefficient[(Sum[x^(2^j), {j,0,m+1}])^k, x, n]; Table[T[n, k], {n,10}, {k,n}]//Flatten (* _G. C. Greubel_, Mar 06 2020 *)
%Y Cf. A048298, A073265, A023359 (row sums), A089052 (partitions of n).
%Y T(2n,n) gives A333047.
%K nonn,tabl
%O 1,5
%A _Antti Karttunen_, Jun 25 2002
|
