Our presentation of K.A.Post’s proof of R.Stanley’s theorem (with A.J.M. van Gasteren)

A v G 4 / E W D 7 8 5 - 0

Our presentation of K.A. Post's proof of R. Stanley's theorem.

In the following, the range of $b$ consists of the bags of positive integers, the empty bag included. The functions $c, d,$ and $e$ are defined as follows:

$c\left( b\right) =$ the sum of the contents of $b$

$d\left( b\right) = \frac{\text{the number of distinct integers in} b,$ i.e. (N C::: c in b)

$e\left( b\right) =$ the number of 1's in $b$ .

Richard Stanley's theorem states that for any natural number $n$ we have $D\left( n\right) = E\left( n\right)$ ,where the functions

D and $E$ are defined as follows:

\begin{array}{l} D (n) = (\sum b: ^ {\prime} c (b) = n: ^ {\prime} d (b)) \ E (n) = (\underline {{S}} b: c (b) = n: e (b)) \ \end{array}

Stanley's Theorem is an immediate consequence of the following two lemmata of K.A. Post's:

Lemma 0. $D\left( n\right) = \left( {{S}_{i} : 0 ≤ i < n : P\left( i\right) }\right)$ ,and

Lemma 1. $E(n) = (\underline{S} i:0≤ i < n:P(i))$ ，where

function $P$ is defined by $P\left( n\right) = \left( {Nb}\right) c\left( b\right) = n$ ).

(Note that, since the range of $b$ includes the empty bag, $P\left( 0\right) = 1.$ )

A v G 4 / E W D 7 8 5 - 1

Before proving Post's lemmata, we establish

Lemma 2. For $0 < i$ s n, there exists a one-to-one correspondence between the solutions b of

c (b) = n \wedge i _ {\mathrm {i n}} b

and the solutions $b$ of

c (b ^ {\prime}) = n - i

Proof of Lemma 2. Removing one instance of $i$ from $a$ b that satisfies the first equation yields a $b^{\prime}$ that satisfies the second one. Adding one instance of $i$ to $a$ $b^{\prime}$ that satisfies the last equation yields a $b$ that satisfies the first one. (End of Proof of Lemma 2.)

Proof of Lemma 0.

\begin{array}{l} D (n) = (\underline {{S}} b: c (b) = n: (\underline {{N}} i: i \underline {{i n}} b)) \ = (\underline {{N}} (i, b) \because c (b) = n ∧ i \ln b) \ = (\underline {{S}} i: 0 < i ≤ n: (\underline {{N}} b: c (b) = n ∧ i \in b)) \ = (\underline {{S}} i: 0 < i ≤ n: (\underline {{N}} b: c (b) = n - i)) * \ = (\sum i: 0 < i ≤ n: P (n - i)) \ = (\sum i: 0 ≤ i < n: P (i)) \ \end{array}

*) This line follows from the previous one on account of lemma 2.

(E n d o f P r o o f o f L e m m a 0.)

A v G 4 / E W D 7 8 5 - 2

Proof of Lemma 1. Since $E(0) = 0$ , Lemma 1 holds for $n = 0$ . For $n > 0$ , we deduce

\begin{array}{l} E (n) = (S b: c (b) = n: e (b)) \ = (\sum b: c (b) = n \wedge 1 \underline {{i n}} b: e (b)) \ = (\sum b ^ {\prime}: c (b ^ {\prime}) = n - 1: 1 + e (b ^ {\prime})) x x) \ = P (n - 1) + E (n - 1) \ \end{array}

[{xx)}\text{This line follows from the previous one on account}]

The solution of the above recurrence relation is

E (n) = E (0) + (\sum i: 0 ≤ i < n: P (i))

which, thanks to $E\left( 0\right) = 0$ ,concludes the proof. (End of Proof of Lemma 1.)

Richard Stanley's theorem was communicated to us by Ross A. Homsberger, who added a five-page proof for which he expressed his indebtedness to his colleague Ian Goulden. That proof uses generating functions and we hoped that it was much too complicated. K.A. Post discovered and proved lemma 0 and lemma1. The proofs given above are ours; so is the decision to use in the presentation formulae rather than pictures.

The bags b with $c(b) = n$ correspond to the so-called "unordered partitions of $n$ ", this in

contrast to the so-called "ordered partitions". For instance, for $n = 3$ we have 4 "ordered partitions", viz. 3, 2+1, 1+2, and 1+1+1, but - identifying the two middle ones with each other - only 3 "unordered partitions". It is then very tempting to choose for the unordered partitions a canonical linear representation, say listing the elements in descending order. The next step is a graphical representation in the form of a staircase. But such a linear order, though canonical, is entirely foreign to the original problem statement. (We have played with the staircases and got into a mess; our programmers' pasts may have played a dirty trick upon us!)

We feel attracted by the above presentation because, right from the start, it is expressed in terms of the appropriate concept, viz. the bag. (Regretably, many mathematicians are much more familiar with the notion of sets than with the more general notion of bags.) Furthermore we draw attention to the fact that the above could not have been written without the use of the numeral quantifier "N".

drs.A.J.M.van Gasteren BP Venture Research Fellow Dept. of Mathematics University of Technology 5600 MB EINDHOVEN The Netherlands

9 April 1981 prof. dr. Edsger W. Dijkstra Burroughs Research Fellow Plataanstraat 5 5671 AL NUENEN The Netherlands