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
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. Triangle begins: 1; 1, 1; 0, 2, 1; 1, 1, 3, 1; 0, 2, 3, 4, 1; 0, 2, 4, 6, 5, 1;
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.
Crossrefs
Programs
-
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 *)
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
Comments