A360189 Number T(n,k) of nonnegative integers <= n having binary weight k; triangle T(n,k), n>=0, 0<=k<=floor(log_2(n+1)), read by rows.

1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 3, 2, 1, 3, 3, 1, 3, 3, 1, 1, 4, 3, 1, 1, 4, 4, 1, 1, 4, 5, 1, 1, 4, 5, 2, 1, 4, 6, 2, 1, 4, 6, 3, 1, 4, 6, 4, 1, 4, 6, 4, 1, 1, 5, 6, 4, 1, 1, 5, 7, 4, 1, 1, 5, 8, 4, 1, 1, 5, 8, 5, 1, 1, 5, 9, 5, 1, 1, 5, 9, 6, 1, 1, 5, 9, 7, 1

Offset

0,5

Comments

T(n,k) is defined for all n >= 0 and k >= 0. Terms that are not in the triangle are zero.

Links

Alois P. Heinz, Rows n = 0..2^12-1, flattened

Wikipedia, Iverson bracket

Formula

T(n,k) = T(n-1,k) + [A000120(n) = k] where [] is the Iverson bracket and T(n,k) = 0 for n<0.

T(2^n-1,k) = A007318(n,k) = binomial(n,k).

T(n,floor(log_2(n+1))) = A090996(n+1).

Sum_{k>=0} T(n,k) = n+1.

Sum_{k>=0} k * T(n,k) = A000788(n).

Sum_{k>=0} k^2 * T(n,k) = A231500(n).

Sum_{k>=0} k^3 * T(n,k) = A231501(n).

Sum_{k>=0} k^4 * T(n,k) = A231502(n).

Sum_{k>=0} 2^k * T(n,k) = A006046(n+1).

Sum_{k>=0} 3^k * T(n,k) = A130665(n).

Sum_{k>=0} 4^k * T(n,k) = A116520(n+1).

Sum_{k>=0} 5^k * T(n,k) = A130667(n+1).

Sum_{k>=0} 6^k * T(n,k) = A116522(n+1).

Sum_{k>=0} 7^k * T(n,k) = A161342(n+1).

Sum_{k>=0} 8^k * T(n,k) = A116526(n+1).

Sum_{k>=0} 10^k * T(n,k) = A116525(n+1).

Sum_{k>=0} n^k * T(n,k) = A361257(n).

Example

T(6,2) = 3: 3, 5, 6, or in binary: 11_2, 101_2, 110_2.
T(15,3) = 4: 7, 11, 13, 14, or in binary: 111_2, 1011_2, 1101_2, 1110_2.
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 2;
  1, 2, 1;
  1, 3, 1;
  1, 3, 2;
  1, 3, 3;
  1, 3, 3, 1;
  1, 4, 3, 1;
  1, 4, 4, 1;
  1, 4, 5, 1;
  1, 4, 5, 2;
  1, 4, 6, 2;
  1, 4, 6, 3;
  1, 4, 6, 4;
  1, 4, 6, 4, 1;
  ...

Maple

b:= proc(n) option remember; `if`(n<0, 0,
      b(n-1)+x^add(i, i=Bits[Split](n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..23);

Crossrefs

Columns k=0-2 give: A000012, A029837(n+1) = A113473(n) for n>0, A340068(n+1).

Last elements of rows give A090996(n+1).

Cf. A000027, A000120, A000225, A000788, A006046, A007318, A116520, A116522, A116525, A116526, A130665, A130667, A161342, A231500, A231501, A231502, A361257.

Sequence in context: A249809 A075104 A253667 * A368210 A233932 A008289

Adjacent sequences: A360186 A360187 A360188 * A360190 A360191 A360192

Keyword

nonn,look,tabf,base

Author

Alois P. Heinz, Mar 04 2023

Status

approved