A323840 - OEIS

%I #23 Jul 07 2021 11:14:16

%S 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,

%T 957,627,299,91,15,1,1,1,3,13,75,525,1827,5965,18315,51885,130977,

%U 304953,646373,1238601,2143065,3331429,4663967,5867703

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

%H James Rayman, <a href="/A323840/b323840.txt">Rows n = 0..10, flattened</a>

%H S. Lehr, J. Shallit and J. Tromp, <a href="http://dx.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. See Table 2.

%F T(n, k) = A073266(2^n, k). - _James Rayman_, Mar 30 2021

%e The first few rows are:

%e   1;

%e   1, 1;

%e   1, 1, 3,  1;

%e   1, 1, 3, 13, 15,  15,   7,   1;

%e   1, 1, 3, 13, 75, 165, 357, 645, 927, 1095, 957, 627, 299, 91, 15, 1;

%e   ...

%e The counts for row 3 arise as follows:

%e   8 (1)

%e   = 4+4 (1)

%e   = 4+2+2 (3)

%e   = 4+2+1+1 or 2+2+2+2 (12+1=13)

%e   = 4+1+1+1+1 or 2+2+2+1+1 (5+10=15)

%e   = 2+2+1+1+1+1 (15)

%e   = 2+1+1+1+1+1+1 (7)

%e   = 1+1+1+1+1+1+1+1 (1)

%p b:= proc(n) option remember; expand(`if`(n=0, 1,

%p       add(x*b(n-2^j), j=0..ilog2(n))))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..2^n))(b(2^n)):

%p seq(T(n), n=0..5);  # _Alois P. Heinz_, Mar 31 2021

%t b[n_] := b[n] = Expand[If[n == 0, 1,

%t      Sum[x*b[n - 2^j], {j, 0, Length@IntegerDigits[n, 2]-1}]]];

%t T[n_] := With[{p = b[2^n]}, Table[Coefficient[p, x, i], {i, 1, 2^n}]];

%t Table[T[n], {n, 0, 5}] // Flatten (* _Jean-François Alcover_, Jul 07 2021, after _Alois P. Heinz_ *)

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def t(n, k):

%o     if n < k: return 0

%o     if k == 0: return 1 if n == 0 else 0

%o     r = 0

%o     i = 1

%o     while True:

%o         if i > n: break

%o         r += t(n - i, k-1)

%o         i *= 2

%o     return r

%o def T(n, k): return t(2**n, k) # _James Rayman_, Mar 30 2021

%Y The rows are a subset of the rows of A073266.

%Y Row sums give A248377.

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

%Y Cf. A023359.

%K nonn,tabf

%O 0,6

%A _N. J. A. Sloane_, Feb 04 2019

%E More terms from _James Rayman_, Mar 30 2021