A307435 Number of partitions of n into parts whose bitwise AND equals 0.

1, 0, 0, 1, 1, 3, 5, 9, 11, 18, 27, 38, 53, 75, 102, 137, 178, 238, 313, 406, 528, 677, 865, 1093, 1382, 1742, 2181, 2717, 3377, 4175, 5146, 6320, 7737, 9454, 11516, 13986, 16950, 20473, 24682, 29672, 35631, 42663, 50992, 60807, 72399, 86008, 102027, 120793

Offset

0,6

Links

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

Wikipedia, Bitwise operation

Wikipedia, Partition (number theory)

Example

a(0) = 1: the empty partition.
a(3) = 1: 21.
a(4) = 1: 211.
a(5) = 3: 2111, 221, 41.
a(6) = 5: 21111, 2211, 321, 411, 42.
a(7) = 9: 211111, 22111, 2221, 3211, 4111, 421, 43, 52, 61.
a(8) = 11: 2111111, 221111, 22211, 32111, 3221, 41111, 4211, 422, 431, 521, 611.
a(9) = 18: 21111111, 2211111, 222111, 22221, 321111, 32211, 3321, 411111, 42111, 4221, 4311, 432, 441, 5211, 522, 6111, 621, 81.

Maple

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

Crossrefs

Column k=0 of A307432.

Sequence in context: A100456 A059819 A074986 * A123328 A226175 A091945

Adjacent sequences: A307432 A307433 A307434 * A307436 A307437 A307438

Keyword

nonn,base

Author

Alois P. Heinz, Apr 08 2019

Status

approved