Lecture 9 - Basic combinatorics I: non-crossing partitions

Summary

In the preceding lecture we saw that a special type of partitions seems to lie underneath the structure of free probability. These are the so-called “non-crossing” partitions. The study of the lattices of non-crossing partitions was started by combinatorialists quite some time before the development of free probability. In this and the next lecture we will introduce these objects in full generality and present their main combinatorial properties which are of relevance for us.

The preceding lecture has also told us that, from a combinatorial point of view, classical probability and free probability should behave as all partitions versus non-crossing partitions. Thus, we will also keep an eye on similarities and differences between these two cases.

Non-crossing partitions of an ordered set

Definitions 9.1. Let S be a finite totally ordered set.

1. (1) We call π = {V₁, …, V_r} a partition of the set S if and only if the V_i (1 ≤ i ≤ r) are pairwise disjoint, non-void subsets of S such that V₁ ∪ … ∪ V_r = S. We call V₁, …, V_r the blocks of π. The number of blocks of π is denoted by |π|. Given two elements p, q ∈ S, we write p ∼_πq if p and q belong to the same block of π.

2. (2) The set of all partitions of S is denoted by P(S). In the special case S = {1, …, n}, we denote this by P (n).

3. […]