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.

Ifnis odd,b=_{n}b, and_{n-1}

ifnis even,b=_{n}b+_{n-1}b._{n/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
*b*_{n-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
*b*_{n/2}.

The ordinary generating function for binary partitions is

giving rise to the functional equation B(

1 B( x) =

(1 -x)(1-x^{2})(1-x^{4})(1-x^{8})...,

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

[Error Opening Counter File -- Click for more info]

©Frank Ruskey, 1995-2003.