p(n)z n .

P (z) = 1 +

n∈N

Proposition.

1 1 1 1

P (z) = ··· = .

2 1 ’ z3 1 ’ zk

1’z1’z

k∈N

Proof. The RHS is (1 + z + z 2 + . . . )(1 + z 2 + z 4 + . . . )(1 + z 3 + z 6 . . . ) . . . .

We get a term z n whenever we select z a1 from the ¬rst bracket, z 2a2 from the

second, z 3a3 from the third and so on, and n = a1 + 2a2 + 3a3 + . . . , or in other words

1a1 2a2 3a3 . . . is a partition of n. There are p(n) of these.

We can similarly prove these results.

Proposition. The generating function Pm (z) of the sequence pm (n) of partitions of n

into at most m parts (or the generating function for the sequence pm (n) of partitions

of n with largest part ¤ m) satis¬es

1 1 1 1

Pm (z) = ... .

2 1 ’ z3 1 ’ zm

1’z1’z

Proposition. The generating function for the number of partitions into odd parts is

1 1 1

....

1 ’ z 1 ’ z3 1 ’ z5

Proposition. The generating function for the number of partitions into unequal parts

is

(1 + z)(1 + z 2 )(1 + z 3 ) . . . .

CHAPTER 2. INDUCTION AND COUNTING

20

Theorem 2.3. The number of partitions of n into odd parts equals the number of par-

titions of n into unequal parts.

Proof.

1 ’ z2 1 ’ z4 1 ’ z6

2 3

(1 + z)(1 + z )(1 + z ) . . . = ...

1 ’ z 1 ’ z2 1 ’ z3

1 1 1

= ...

1 ’ z 1 ’ z3 1 ’ z5

Theorem 2.4. The number of self-conjugate partitions of n equals the number of par-

titions of n into odd unequal parts.

Proof. Consider hooks along the main diagonal like this.

This process can be reversed, so there is a one-to-one correspondance.

2.6.6 Generating function for self-conjugate partitions

Observe that any self-conjugate partition consists of a largest k—k subsquare and twice

a partition of 1 (n ’ k 2 ) into at most k parts. Now

2

1

(1 ’ z 2 )(1 ’ z 4 ) . . . (1 ’ z 2m )

is the generating function for partitions of n into even parts of size at most 2m, or

1

alternatively the generating function for partitions of 2 n into parts of size ¤ m. We

deduce that

zl

(1 ’ z 2 )(1 ’ z 4 ) . . . (1 ’ z 2m )

is the generating function for partitions of 1 (n ’ l) into at most m parts. Hence the

2

generating function for self-conjugate partitions is

2

zk

1+ .

(1 ’ z 2 )(1 ’ z 4 ) . . . (1 ’ z 2k )

k∈N

Note also that this equals

(1 + z 2k+1 ),

k∈N0

as the number of self-conjugate partitions of n equals the number of partitions of n into

unequal odd parts.

In fact in any partition we can consider the largest k — k subsquare, leaving two

partitions of at most k parts, one of (n ’ k 2 ’ j), the other of j for some j. The number

2.6. SPECIAL SEQUENCES OF INTEGERS 21

k

2

1

of these two lots are the coef¬cients of z n’k ’j

and z j in respectively.

i=1 1’z i

Thus

2

zk

P (z) = 1 + 2.

2 k

k∈N ((1 ’ z)(1 ’ z ) . . . (1 ’ z ))

CHAPTER 2. INDUCTION AND COUNTING

22

Chapter 3

Sets, Functions and Relations

3.1 Sets and indicator functions

We ¬x some universal set S. We write P (S) for the set of all subsets of S ” the “power

set” of S. If S is ¬nite with |S| = m (the number of elements), then |P (S)| = 2m .

¯

Given a subset A of S (A ⊆ S) we de¬ne the “complement” A of A in S as

¯

A = {s ∈ S : s ∈ A}.

/

Given two subsets A, B of S we can de¬ne various operations to get new subsets

of S.

A©B = {s ∈ S : s ∈ A and s ∈ B}

A∪B = {s ∈ S : s ∈ A (inclusive) or s ∈ B}

A\B = {s ∈ A : s ∈ B}

/

A—¦B = {s ∈ S : s ∈ A (exclusive) or s ∈ B} the symmetric difference

= (A ∪ B) \ (A © B)

= (A \ B) ∪ (B \ A).

The indicator function IA of the subset A of S is the function IA : S ’ {0, 1}

de¬ned by

1 x∈A

IA (s) =

0 otherwise.

It is also known as the characteristic function χA . Two subsets A and B of S are equal

iff IA (s) = IB (s) ∀s ∈ S. These relations are fairly obvious:

IA = 1 ’ IA

¯

IA©B = IA · IB

IA∪B = IA + IB

IA—¦B = IA + IB mod 2.

Proposition. A —¦ (B —¦ C) = (A —¦ B) —¦ C.

23

CHAPTER 3. SETS, FUNCTIONS AND RELATIONS