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 A000123 in Neil J. Sloane's database of integer sequences.

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

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.