cp's OEIS Frontend

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.

%I A073265 #21 Jun 27 2021 07:53:06
%S A073265 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,
%T A073265 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,
%U A073265 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
%N 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.
%H A073265 Alois P. Heinz, <a href="/A073265/b073265.txt">Antidiagonals n = 1..141, flattened</a>
%H A073265 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 A073265 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).
%F A073265 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
%e A073265 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.
%p A073265 T:= proc(n, k) option remember; `if`(k>n, 0,
%p A073265       `if`(n=k, 1, add(T(n-2^j, k-1), j=0..ilog2(n))))
%p A073265     end:
%p A073265 seq(seq(T(d-k+1, k), k=1..d), d=1..20);  # _Alois P. Heinz_, Mar 26 2014
%t A073265 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_ *)
%Y A073265 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.
%K A073265 nonn,tabl
%O A073265 1,8
%A A073265 _Antti Karttunen_, Jun 25 2002