A307432 Number T(n,k) of partitions of n into parts whose bitwise AND equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 3, 2, 1, 0, 0, 1, 5, 3, 1, 1, 0, 0, 1, 9, 4, 1, 0, 0, 0, 0, 1, 11, 6, 3, 0, 1, 0, 0, 0, 1, 18, 6, 3, 1, 1, 0, 0, 0, 0, 1, 27, 8, 3, 1, 1, 1, 0, 0, 0, 0, 1, 38, 11, 4, 0, 2, 0, 0, 0, 0, 0, 0, 1, 53, 13, 6, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1

Offset: 0

Author

Alois P. Heinz, Apr 08 2019

Keywords

• nonn
• tabl
• look
• base

Examples

			T(6,0) = 5: 11112, 1122, 123, 114, 24.
T(6,1) = 3: 111111, 1113, 15.
T(6,2) = 1: 222.
T(6,3) = 1: 33.
T(6,6) = 1: 6.
Triangle T(n,k) begins:
   1;
   0, 1;
   0, 1, 1;
   1, 1, 0, 1;
   1, 2, 1, 0, 1;
   3, 2, 1, 0, 0, 1;
   5, 3, 1, 1, 0, 0, 1;
   9, 4, 1, 0, 0, 0, 0, 1;
  11, 6, 3, 0, 1, 0, 0, 0, 1;
  18, 6, 3, 1, 1, 0, 0, 0, 0, 1;
  27, 8, 3, 1, 1, 1, 0, 0, 0, 0, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• Wikipedia, Bitwise operation
• Wikipedia, Partition (number theory)

Crossrefs

Column k=0 gives A307435.

Row sums give A000041.

Main diagonal gives A000012.

Cf. A050314 (the same for XOR), A307431 (the same for OR).

Programs

Maple

b:= proc(n, i, k) option remember; `if`(n=0, x^k, `if`(i<1, 0,
      b(n, i-1, k)+b(n-i, min(n-i, i), Bits[And](i, k))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(
         b(n$2, `if`(n=0, 0, 2^ilog2(2*n)-1))):
seq(T(n), n=0..14);