A073266 -id:A073266 - cp's OEIS frontend

A073265 Table T(n,k) (listed antidiagonalwise in order T(1,1), T(2,1), T(1,2), T(3,1), T(2,2), ...) giving the number of compositions (ordered partitions) of n into exactly k powers of 2.

1, 1, 0, 0, 1, 0, 1, 2, 0, 0, 0, 1, 1, 0, 0, 0, 2, 3, 0, 0, 0, 0, 2, 3, 1, 0, 0, 0, 1, 0, 4, 4, 0, 0, 0, 0, 0, 1, 6, 6, 1, 0, 0, 0, 0, 0, 2, 3, 8, 5, 0, 0, 0, 0, 0, 0, 2, 3, 13, 10, 1, 0, 0, 0, 0, 0, 0, 0, 6, 12, 15, 6, 0, 0, 0, 0, 0, 0, 0, 2, 6, 10, 25, 15, 1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 16, 31, 26, 7, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Antti Karttunen, Jun 25 2002

			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 and it is recursively computed from T(5,2)+T(4,2)+T(2,2) = 2+1+1.

Alois P. Heinz, Antidiagonals n = 1..141, 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.

The first row is equal to the characteristic function of A000079, i.e., A036987 with offset 1 instead of 0 and the second row is A073267. The column sums give A023359. A073266 gives the upper triangular region of this array.

T:= proc(n, k) option remember; `if`(k>n, 0,
      `if`(n=k, 1, add(T(n-2^j, k-1), j=0..ilog2(n))))
    end:
seq(seq(T(d-k+1, k), k=1..d), d=1..20);  # Alois P. Heinz, Mar 26 2014

T[n_, k_] := If[k>n, 0, SeriesCoefficient[Sum[x^(2^j), {j, 0, Log[2, n] // Ceiling} ]^k, {x, 0, n}]]; Table[T[n-k+1, k], {n, 1, 20}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Emeric Deutsch *)

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

T(n, k) is the coefficient of x^n in the formal power series (x + x^2 + x^4 + x^8 + x^16 + ...)^k. - Emeric Deutsch, Feb 04 2005

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

Original entry on oeis.org

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

N. J. A. Sloane, Feb 04 2019

			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)

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.

The rows are a subset of the rows of A073266.
Row sums give A248377.
T(n,n) gives A007178 (for n>=1).
Cf. A023359.

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

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

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

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

More terms from James Rayman, Mar 30 2021

A333047 Number of compositions of 2n into n powers of 2.

Original entry on oeis.org

1, 1, 1, 4, 13, 31, 76, 218, 645, 1849, 5281, 15346, 44980, 131704, 385568, 1131874, 3331429, 9819405, 28977079, 85633438, 253424053, 750895163, 2227288196, 6613217348, 19654450476, 58463536356, 174041552556, 518488451716, 1545686334184, 4610827520500

Offset: 0

Alois P. Heinz, Mar 06 2020

nonn

			a(3) = 4: 222, 114, 141, 411.
a(4) = 13: 2222, 1124, 1142, 1214, 1241, 1412, 1421, 2114, 2141, 2411, 4112, 4121, 4211.

Alois P. Heinz, Table of n, a(n) for n = 0..2078

Cf. A003714, A073266.

b:= proc(n, t) option remember; `if`(n=0, `if`(t=0, 1, 0),
      `if`(t=0, 0, add(b(n-2^j, t-1), j=0..ilog2(n))))
    end:
a:= n-> b(2*n, n):
seq(a(n), n=0..30);

b[n_, t_] := b[n, t] = If[n == 0, If[t == 0, 1, 0], If[t == 0, 0, Sum[b[n - 2^j, t - 1], {j, 0, Floor@Log2[n]}]]];
a[n_] := b[2*n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 28 2022, after Alois P. Heinz *)

a(n) = A073266(2n,n).
a(n) mod 2 = 1 <=> n in { A003714 }.
a(n) ~ c * d^n / sqrt(n), where d = 3.03557496500556374352187743150809307334142929675774277... and c = 0.257758082536856928607441503594486605201517917904563... - Vaclav Kotesovec, Mar 10 2020

A007801 Expansion of f(f(x)), where f = x + x^2 + x^4 + x^8 + x^16 + ...

Original entry on oeis.org

1, 2, 2, 3, 6, 8, 8, 16, 22, 40, 80, 146, 240, 356, 488, 661, 870, 1184, 1936, 3750, 7976, 17628, 37528, 74828, 140480, 249444, 420392, 678432, 1056600, 1593512, 2334928, 3337410, 4660246, 6364080, 8527984, 11258182, 14753032, 19622940, 27836440

Offset: 1

Jeffrey Shallit

nonn

Robert Israel, Table of n, a(n) for n = 1..1023

e:= 8;
f:= x -> sum(x^(2^i),i=0..e):
g:= f(f(x)):
S:= series(g,x,2^e):
seq(coeff(S,x,n),n=0..2^e-1); # Robert Israel, Aug 19 2014

f[x_]:= Sum[x^(2^j), {j,0,10}]; g[x_]:=f[f[x]]; CoefficientList[Series[g[x], {x, 0, 50}], x] (* G. C. Greubel, Mar 05 2020 *)

a(n) = Sum_{k=1..n} A073266(n,k)*f(k). - Vladimir Kruchinin, Mar 13 2012

cp's OEIS Frontend

A073265 Table T(n,k) (listed antidiagonalwise in order T(1,1), T(2,1), T(1,2), T(3,1), T(2,2), ...) giving the number of compositions (ordered partitions) of n into exactly k powers of 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A333047 Number of compositions of 2n into n powers of 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A007801 Expansion of f(f(x)), where f = x + x^2 + x^4 + x^8 + x^16 + ...

Views

Author

Keywords

Links

Programs

Maple

Mathematica

Formula