CHAPTER I

P R E L I M I N A R I E S O N NON-CROSSIN G PARTITION S

In this first chapter, we want to collect all relevant combinatorial facts about

the lattice of non-crossing partitions. In particular, we will examine the notion of

(scalar-valued) multiplicative functions on this lattice, a notion which will be gen-

eralized in the next chapter to the crucial concept of operator-valued multiplicative

functions. The material presented here is essentially taken from [Spe4] and deeply

inspired by Rota's [Rotl,Rot2] combinatorial point of view on classical probability

theory.

1.1. Non-crossing partitions

We start by recalling the basic definitions and facts about non-crossing partitions.

1.1.1. DEFINITION. Let 5 be a linearly ordered set. Then ir = {Vi,... , Vp} is a

partition of 5, if the Vi ^ 0 are disjoint sets, whose union is S. The partition TT is

called non-crossing if for all z, j = 1,.. . ,p with Vi = {^i,..., vn} (vi • • • vn)

and Vj = {wi,..., iu

m

} (wi • • • wm) we have

wk vi Wk+i OWkvn Wk+i (k = 1 , . . . , m - 1).

We can reformulate the definition of 'non-crossing' in a recursive way: The partition

7r = {Vi,... , Vp} is non-crossing if at least one Vi is an interval in S (i.e. it contains

exactly all points of S lying between two points) and 7r\{Vj} is a non-crossing

partition of S\Vi.

We will denote the set of all non-crossing partitions of 5 by NC(S).

1.1.2. EXAMPLE. Non-crossing partitions of {1,2,3,4,5} are

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

crossing ones are

{{1,3}, {2,4,5}} and {{1,4}, {2},{3,5}}.

1.1.3. NOTATIONS. 1) The Vi are called the blocks of a given partition TT =

{Vi,...,V^}. If we write a block in the form Vi — (vi, •.. ,vm) then this will

always imply that v± • • • vm. A ir G NC(S) determines an equivalence relation

on S in a canonical way and we will write v ^ w, if v, w E S belong to the same

block of 7r. By |7r| we will denote the number of blocks of 7r, and in the same way

by |V| the number of elements of the set V. For si, S2 € S with si 52, we call

[si, s2] := {s G S I si s s2} and ]si, s2[:= {s G S \ Si s s2}

3