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

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.

Formula

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

Example

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)

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

Prog

(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

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.

Sequence in context: A082553 A331736 A344300 * A195644 A143632 A336455

Adjacent sequences: A323837 A323838 A323839 * A323841 A323842 A323843

Keyword

nonn,tabf

Author

N. J. A. Sloane, Feb 04 2019

Extensions

More terms from James Rayman, Mar 30 2021

Status

approved