Info on Binary Partitions

A binary partition of an integer m is a is a numerical partition of m, all of whose parts are powers of 2.

For example, the four binary partitions of m = 5 are 1 1 1 1 1,   1 1 1 2,   1 2 2, and 1 4.

For n = 0, 1, 2, 3, ..., 11 the number of binary partitions is 1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14. This is sequence Anum=A000123"> A000123 in

Binary partitions satisfy the following recurrence relation.

If n is odd, bn = bn-1, and
if n is even, bn = bn-1 + bn/2.

To see that this recurrence relation is correct, classify the partitions according to whether 1 is a part or not. If 1 is a part, remove it, obtaining a partition counted by bn-1. If 1 is not a part, then n must be even, and each part can be divided by two to obtain a partition counted by bn/2.

The ordinary generating function for binary partitions is

1
B(x)   =  
(1-x)(1-x2)(1-x4)(1-x8)...,
giving rise to the functional equation B(x2)   =   (1-x)B(x).


It was last updated .