login
A073266
Triangle read by rows: T(n,k) is the number of compositions of n as the sum of k integral powers of 2.
5
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, 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, 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
OFFSET
1,5
COMMENTS
Upper triangular region of the table A073265 read by rows. - Emeric Deutsch, Feb 04 2005
Also the convolution triangle of A209229. - Peter Luschny, Oct 07 2022
LINKS
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.
FORMULA
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
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
Sum_{k=0..n} T(n,k) = A023359(n). - Philippe Deléham, Nov 04 2006
EXAMPLE
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.
Triangle begins:
1;
1, 1;
0, 2, 1;
1, 1, 3, 1;
0, 2, 3, 4, 1;
0, 2, 4, 6, 5, 1;
MAPLE
b:= proc(n) option remember; expand(`if`(n=0, 1,
add(b(n-2^j)*x, j=0..ilog2(n))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n)):
seq(T(n), n=1..14); # Alois P. Heinz, Mar 06 2020
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> if n = 2^ilog2(n) then 1 else 0 fi); # Peter Luschny, Oct 07 2022
MATHEMATICA
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 *)
CROSSREFS
Cf. A048298, A073265, A023359 (row sums), A089052 (partitions of n).
T(2n,n) gives A333047.
Sequence in context: A125090 A294880 A212219 * A125692 A128258 A104967
KEYWORD
nonn,tabl
AUTHOR
Antti Karttunen, Jun 25 2002
STATUS
approved