Discrete Mathematics

----------------------------COMBINATORICS

257

of

length

>.Jri.

By Dilworth's Theorem,

it

must have an antichain

of

length at least n

I.Jri

=

fn.

But the elements

of

an antichain determine a decreasing subsequence.

8.5

SETS OF THE SAME SIZE: BIJECTIONS

Counting is a theme throughout discrete mathematics: how many leaves in a tree, minimal colourings

of

a

graph, trees with a given set

of

vertices, five-card hands in a deck

of

fifty-two, consistent rankings

of

players

in a tournament, stable marriages given boy's and girl's preferences, and so on.

A useful technique for determining the size

of

a set is an exact correspondence between the elements ...