Odd parts and distinct parts

The previous post looked at a result of Euler regarding even and odd distinct partitions. This post will illustrate a related theorem by Euler.

Definitions

A partition of a positive integer n is a way of writing n as the sum of positive integers, without distinguishing the order of the terms, only the multi-set of summands.

For example, 6 can be written as

1 + 2 + 3

or as

3 + 2 + 1,

but these count as the same partition. Another possible partition of 6 is

3 + 1 + 1 + 1.

Here the summands form a multistet

{3, 1, 1, 1}.

This is not a set because the 1's appear more than once. If the multiset of summands is actually a set, the partition is called a distinct partition.

A partition is called odd if every element is odd, and even if every element is even.

Theorem

Now we can state Euler's theorem: The number of odd partitions of an integer equals the number of distinct partitions.

As before we will illustrate this with Mathematica.

Mathematica

First we define a couple predicate functions.

 distinctPartitionQ[list_] := Length[list] == Length[Union[list]] oddPartitionQ[list_] := And @@ Map[OddQ, list]

There are six odd partitions of 8:

 In: Select[IntegerPartitions[8], oddPartitionQ] Out: {{7, 1}, {5, 3}, {5, 1, 1, 1}, {3, 3, 1, 1}, {3, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}}

And six distinct partitions of 8:

 In: Select[IntegerPartitions[8], distinctPartitionQ] Out: {{8}, {7, 1}, {6, 2}, {5, 3}, {5, 2, 1}, {4, 3, 1}}

To try partitions of more numbers, let's define

 d[n_] := Length[Select[IntegerPartitions[n], distinctPartitionQ]] - Length[Select[IntegerPartitions[n], oddPartitionQ]]

We can see that d[n] is 0 for n = 1, 2, 3, ..., 50 by running

 Table[d[n], {n, 1, 50}]

Testing understanding

This post and the previous post illustrate something important: it helps to verify a theorem computationally, even if you know the theorem is true, in order to test your understanding of the theorem. If a theorem by Euler were wrong, we'd know by now. But my interpretation of the terms in this theorem and the theorem in the previous post were both wrong at first, and computations made this obvious.

Note that in this post, odd partition" means a partition consisting of only odd numbers.

In the previous post, an odd distinct partition" is a distinct partition of odd length. If we defined odd distinct partition" to be a distinct partition consisting of only odd numbers, the statement of Euler's pentagonal number theorem would be false.

For example, consider the distinct partitions of 3: 3 and 2+1. One distinct partition of even length and one of odd length, as the pentagonal number theorem predicts. But of these two partitions, one consists entirely of odd numbers, and none consists entirely of even numbers.

The post Odd parts and distinct parts first appeared on John D. Cook.