A323840 Irregular triangle read by rows: T(n,k) is the number of compositions of 2^n into k powers of 2.

1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 13, 15, 15, 7, 1, 1, 1, 3, 13, 75, 165, 357, 645, 927, 1095, 957, 627, 299, 91, 15, 1, 1, 1, 3, 13, 75, 525, 1827, 5965, 18315, 51885, 130977, 304953, 646373, 1238601, 2143065, 3331429, 4663967, 5867703

Offset: 0

Author

N. J. A. Sloane, Feb 04 2019

Keywords

• nonn
• tabf

Examples

			The first few rows are:
  1;
  1, 1;
  1, 1, 3,  1;
  1, 1, 3, 13, 15,  15,   7,   1;
  1, 1, 3, 13, 75, 165, 357, 645, 927, 1095, 957, 627, 299, 91, 15, 1;
  ...
The counts for row 3 arise as follows:
  8 (1)
  = 4+4 (1)
  = 4+2+2 (3)
  = 4+2+1+1 or 2+2+2+2 (12+1=13)
  = 4+1+1+1+1 or 2+2+2+1+1 (5+10=15)
  = 2+2+1+1+1+1 (15)
  = 2+1+1+1+1+1+1 (7)
  = 1+1+1+1+1+1+1+1 (1)
		

Links

• James Rayman, Rows n = 0..10, 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. See Table 2.

Crossrefs

The rows are a subset of the rows of A073266.

Row sums give A248377.

T(n,n) gives A007178 (for n>=1).

Cf. A023359.

Programs

Maple

b:= proc(n) option remember; expand(`if`(n=0, 1,
      add(x*b(n-2^j), j=0..ilog2(n))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..2^n))(b(2^n)):
seq(T(n), n=0..5);  # Alois P. Heinz, Mar 31 2021

Mathematica

b[n_] := b[n] = Expand[If[n == 0, 1,
     Sum[x*b[n - 2^j], {j, 0, Length@IntegerDigits[n, 2]-1}]]];
T[n_] := With[{p = b[2^n]}, Table[Coefficient[p, x, i], {i, 1, 2^n}]];
Table[T[n], {n, 0, 5}] // Flatten (* Jean-François Alcover, Jul 07 2021, after Alois P. Heinz *)

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def t(n, k):
    if n < k: return 0
    if k == 0: return 1 if n == 0 else 0
    r = 0
    i = 1
    while True:
        if i > n: break
        r += t(n - i, k-1)
        i *= 2
    return r
def T(n, k): return t(2**n, k) # James Rayman, Mar 30 2021

Formula

T(n, k) = A073266(2^n, k). - James Rayman, Mar 30 2021

Extensions

More terms from James Rayman, Mar 30 2021