Combinatorics and Graph Theory · Problem 3.5.6

Generating Functions — David Guichard

Mathematics — Combinatorics · catalan-numbers-non-crossing-partitions

Problem

A partition of a set

S

is a collection of non-empty subsets

A_i \subseteq S

1 \leq i \leq k

(the parts of the partition), such that

\cup_{i=1}^k A_i = S

and for every

i \neq j

A_i \cap A_j = \emptyset

. For example, one partition of

\{1, 2, 3, 4, 5\}

\{\{1,3\}, \{4\}, \{2,5\}\}

. Suppose the integers

1, 2, \ldots, n

are arranged on a circle, in order around the circle. A partition of

\{1, 2, \ldots, n\}

is a non-crossing partition if it satisfies this additional property: If

w

and

x

are in some part

A_i

, and

y

and

z

are in a different part

A_j

, then the line joining

w

x

does not cross the line joining

y

z

. The partition above,

\{1,3\}, \{4\}, \{2,5\}

, is not a non-crossing partition, as the line 1--3 crosses the line 2--5. Find the number of non-crossing partitions of

\{1, 2, \ldots, n\}

. Recall from section 1.4 that the Bell numbers count all of the partitions of

\{1, 2, \ldots, n\}

. Hence, this exercise gives us a lower bound on the total number of partitions.