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,8

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.

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

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

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

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.

Sequence in context: A296338 A374216 A133703 * A338326 A347249 A025438

Adjacent sequences: A073262 A073263 A073264 * A073266 A073267 A073268

Keyword

nonn,tabl

Author

Antti Karttunen, Jun 25 2002

Status

approved