A073266 Triangle read by rows: T(n,k) is the number of compositions of n as the sum of k integral powers of 2.

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

G. C. Greubel, Rows n = 1..100 of triangle, flattened

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

Adjacent sequences: A073263 A073264 A073265 * A073267 A073268 A073269

Keyword

nonn,tabl

Author

Antti Karttunen, Jun 25 2002

Status

approved