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
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
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
Comments