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

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

Peter J. Taylor, Closed form for Sum_{k=0..n} [wt(k) = m] where wt(n) is the binary weight of n, answer to question on MathOverflow (2024).

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

T(n,k) = Sum_{j=0..min(k, A000120(n+1)-1)} binomial(A272020(n+1,j+1)-1,k-j) for n >= 0, k >= 0 (see Peter J. Taylor link). - Mikhail Kurkov, Nov 27 2024

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

Prog

(PARI) T(n, k) = my(v1); v1 = Vecrev(binary(n+1)); v1 = Vecrev(select(x->(x>0), v1, 1)); sum(j=0, min(k, #v1-1), binomial(v1[j+1]-1, k-j)) \\ Mikhail Kurkov, Nov 27 2024

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