form is that Fn is the nearest integer to √ .

2

5

Second Method

Or we can form an ordinary generating function

Fn z n .

G(z) =

n≥0

Then using the recurrence for Fn and initial conditions we get that G(z)(1 ’ z ’ z 2 ) =

z. We wish to ¬nd the coef¬cient of z n in the expansion of G(z) (which is denoted

[z n ]G(z)). We use partial fractions and the binomial expansion to obtain the same

result as before.

In general, the ordinary generating function associated with the sequence (an )n∈N0

is G(z) = n≥0 an z n , a “formal power series”. It is deduced from the recurrence and

the initial conditions.

Addition, subtraction, scalar multiplication, differentiation and integration work as

expected. The new thing is the “product” of two such series:

n

k l n

ak z bl z = cn z , where cn = ak bn’k .

n≥0

k≥0 l≥0 k=0

(cn )n∈N0 is the “convolution” of the sequences (an )n∈N0 and (bn )n∈N0 . Some

functional substitution also works.

Any identities give information about the coef¬cients. We are not concered about

convergence, but within the radius of convergence we get extra information about val-

ues.

2.6.3 Catalan numbers

A binary tree is a tree where each vertex has a left child or a right child or both or

neither. The Catalan number Cn is the number of binary trees on n vertices.

Lemma 2.2.

Cn = Ck Cn’1’k

0¤k¤n’1

Proof. On removing the root we get a left subtree of size k and a right subtree of size

n ’ 1 ’ k for 0 ¤ k ¤ n ’ 1. Summing over k gives the result.

This looks like a convolution. In fact, it is [z n’1 ]C(z)2 where

Cn z n .

C(z) =

n≥0

We observe that therefore C(z) = zC(z)2 + 1, where the multiplication by z shifts

the coef¬cients up by 1 and then +1 adjusts for C0 . This equation can be solved for

C(z) to get

√

1 ± 1 ’ 4z

C(z) = .

2z

CHAPTER 2. INDUCTION AND COUNTING

18

Since C(0) = 1 we must have the ’ sign. From the binomial theorem

1

1

(’4)k z k .

2

(1 ’ 4z) 2 =

k

k≥0

1

2n

Thus Cn = ’ 1 n+1 (’4)n+1 . Simplifying this we obtain Cn = 1

and note

2

2 n+1 n

the corollary that (n + 1) | 2n .

n

Other possible de¬nitions for Cn are:

• The number of ways of bracketing n + 1 variables.

• The number of sequences of length 2n with n each of ±1 such that all partial

sums are non-negative.

2.6.4 Bell numbers

De¬nition. The Bell number Bn is the number of partitions of {1, . . . , n}.

It is obvious from the de¬nitions that Bn = S(n, k).

k

Lemma 2.3.

n

Bn+1 = Bk

k

0¤k¤n

Proof. For, put the element n + 1 in with a k-subset of {1, . . . , n} for k = 0 to k =

n.

There isn™t a nice closed formula for Bn , but there is a nice expression for its

exponential generating function.

De¬nition. The exponential generating function that is associated with the sequence

(an )n∈N0 is

an n

ˆ

A(z) = z.

n!

n

ˆ ˆ ˆ ˆ

If we have A(z) and B(z) (with obvious notation) and A(z)B(z) = n cn z n thenn!

cn = k n ak bn’k , the exponential convolution of (an )n∈N0 and (bn )n∈N0 .

k

Hence Bn+1 is the coef¬cient of z n in the exponential convolution of the sequences

ˆ ˆ

1, 1, 1, 1, . . . and B0 , B1 , B2 , . . . . Thus B(z) = ez B(z). (Shifting is achieved by

ˆ z

differentiation for exponential generating functions.) Therefore B(z) = ee +C and

ˆ

using the condition B(0) = 1 we ¬nd that C = ’1. So

z

ˆ

B(z) = ee ’1 .

2.6.5 Partitions of numbers and Young diagrams

For n ∈ N let p(n) be the number of ways to write n as the sum of natural numbers.

We can also de¬ne p(0) = 1.

For instance, p(5) = 7:

2.6. SPECIAL SEQUENCES OF INTEGERS 19

5 4+1 3+2 3+1+1

4 13 3 12

5 32

Notation

2+2+1 2+1+1+1 1+1+1+1+1

22 1 2 13 15

Notation

These partitions of n are usefully pictured by Young diagrams.

The “conjugate partition” is obtained by taking the mirror image in the main diag-

onal of the Young diagram. (Or in other words, consider columns instead of rows.)

By considering (conjugate) Young diagrams this theorem is immediate.

Theorem 2.2. The number of partions of n into exactly k parts equals the number of

partitions of n with largest part k.

We now de¬ne an ordinary generating function for p(n)