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

Author

Alois P. Heinz, Mar 04 2023

Keywords

• nonn
• look
• tabf
• base

Comments

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

Examples

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

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

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.

Programs

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

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

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