A073265 Table T(n,k) (listed antidiagonalwise in order T(1,1), T(2,1), T(1,2), T(3,1), T(2,2), ...) giving the number of compositions (ordered partitions) of n into exactly k powers of 2.

1, 1, 0, 0, 1, 0, 1, 2, 0, 0, 0, 1, 1, 0, 0, 0, 2, 3, 0, 0, 0, 0, 2, 3, 1, 0, 0, 0, 1, 0, 4, 4, 0, 0, 0, 0, 0, 1, 6, 6, 1, 0, 0, 0, 0, 0, 2, 3, 8, 5, 0, 0, 0, 0, 0, 0, 2, 3, 13, 10, 1, 0, 0, 0, 0, 0, 0, 0, 6, 12, 15, 6, 0, 0, 0, 0, 0, 0, 0, 2, 6, 10, 25, 15, 1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 16, 31, 26, 7, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Author

Antti Karttunen, Jun 25 2002

Keywords

• nonn
• tabl

Examples

			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 and it is recursively computed from T(5,2)+T(4,2)+T(2,2) = 2+1+1.
		

Links

• Alois P. Heinz, Antidiagonals n = 1..141, 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.

Crossrefs

The first row is equal to the characteristic function of A000079, i.e., A036987 with offset 1 instead of 0 and the second row is A073267. The column sums give A023359. A073266 gives the upper triangular region of this array.

Programs

Maple

T:= proc(n, k) option remember; `if`(k>n, 0,
      `if`(n=k, 1, add(T(n-2^j, k-1), j=0..ilog2(n))))
    end:
seq(seq(T(d-k+1, k), k=1..d), d=1..20);  # Alois P. Heinz, Mar 26 2014

Mathematica

T[n_, k_] := If[k>n, 0, SeriesCoefficient[Sum[x^(2^j), {j, 0, Log[2, n] // Ceiling} ]^k, {x, 0, n}]]; Table[T[n-k+1, k], {n, 1, 20}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Emeric Deutsch *)

Formula

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).

T(n, k) is the coefficient of x^n in the formal power series (x + x^2 + x^4 + x^8 + x^16 + ...)^k. - Emeric Deutsch, Feb 04 2005