A partition theorem of Euler’s generalized

A partition theorem of Euler's generalized

Here is the original theorem - according to [0] in Euler's words! - :

Theorem. The number of different ways a given number can be expressed as the sum of different whole numbers is the same as the number of ways in which that same number can be expressed as the sum of odd numbers, whether the same or different.

It will emerge as the case $n = 2$ of a more general theorem.

We consider bags of positive natural num- bers. For natural $k$ and $n$ , $n \geq 2$ ,we confine our attention to bags whose contents add up to $k$ ; such a bag qualifies as an A-bag if no value occurs in it n or more times, it qualifies as a B-bag if no value in it is divisible by $n$ . The theorem states that there are as many A-bags as there are B-bags.

We prove this by establishing a 1-to-1 correspondence between $A$ -bags and $B$ -bags.

For the definition of the B-bag that cor- responds to a given A-bag we use that any positive number has (because of $n \geq 2$ ) a unique factorization of the form

$$ (a p o w e r o f n) \cdot x $$

where $x$ is not divisible by $n$ . For any occurrence of ${n}^{i} \cdot x$ in the given $A$ - bag the corresponding B-bag contains ${n}^{i}$ occurrences of $x$ . This clearly yields a bag whose contents add up to $k$ and in-clude no value divisible by $n$ .

For the definition of the $A$ -bag that corresponds to a given $B$ -bag,we observe, with $g$ and $d$ related by the rules of n-ary representation

(0) $g = \left\langle {\sum i : 0 \leq i : {d}{i} \cdot {n}^{i}}\right\rangle \land \left\langle {\forall i : 0 \leq i : 0 \leq {d}{i} < n}\right\rangle$ ,

the simple calculation

$=$ {multiplication distributes over summation and is associative}

$$ \begin{array}{l} = \begin{array}{l} g ^ {*} x \ {(0) } \end{array} \ \langle \sum i: 0 \leq i: d _ {i} \cdot n ^ {i} \rangle \cdot x \ \langle \sum i: 0 \leq i: d _ {i} \cdot (n ^ {i} \cdot x) \rangle \ \end{array} $$

For any $x$ with $g$ occurrences in the given

B-bag, the corresponding A-bag contains (for all i) according to (o) $d_{i}$ occurrences of nix. This clearly yields a bag whose contents (according to the simple calculation) add up to k and include no value n or more times. Because $d_{i} < n$ and the original A-bag contained no value n or more times, the second correspondence is the inverse of the first one.

I designed this proof many years ago but could not find a record of it for general $n$ ; hence this note. I was reminded of it while reading [0], Ria's present for my latest birthday. I think my proof simpler, and easier to formulate for general $n$ than Euler's.

[0] William Dunham, "Euler: The Master of Us All", The Mathematical Association of America, Washington, D.C., 1999, ISBN 0-88385-328-0

Nuenen, 28 June 1999

pror. dr Edsger W. Dijkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712 - 1188 USA