\documentstyle[12pt,amssymb]{amsart}

\newtheorem{thm}{Theorem}    \renewcommand{\thethm}{}
\newtheorem{prop}{Proposition}  \renewcommand{\theprop}{}
\newtheorem{cor}{Corollary}     \renewcommand{\thecor}{}

\theoremstyle{definition}

\newtheorem{defs}{Definition}    \renewcommand{\thedefs}{}


\def\EE{\text{{\bf E}}}
\def\tr{\text{{\bf tr}}}
\def\rb{\rbrack}
\def\lb{\lbrack}
\def\id{\text{id}}
\def\cA{{\cal A}}
\def\cB{{\cal B}}
\def\cF{{\cal F}}
\def\cP{{\cal P}}
\def\HH{{\cal H}}
\def\CC{{\Bbb C}}
\def\NN{{\Bbb N}}
\def\RR{{\Bbb R}}
\def\ZZ{{\Bbb Z}}
\def\ff{\varphi}
\def\bplus{\boxplus}
\def\btimes{\boxtimes}
\def\reli{\leftrightsquigarrow}
\def\chstar{\check\star}


\begin{document}  
\phantom{.}
\vspace*{-2.5cm}

\hspace*{-.3cm}{\sc S\'eminaire Lotharingien de Combinatoire, B39c(1997), 38pp.}
\vspace*{2cm}


\title{Free Probability Theory and Non-Crossing Partitions}
\author[Roland Speicher]{Roland Speicher $^*$}
\address{Institut f\"ur Angewandte Mathematik, Im
Neuenheimer Feld 294, D-69120 Heidelberg, Germany}
\email{roland.speicher@@urz.uni-heidelberg.de}
\thanks{$^*$ supported by a Heisenberg fellowship of the DFG}
\thanks{I want to thank the organizers of the 
39e S\'eminaire Lotharingien de Combinatoire for 
the opportunity to give this talk}

\begin{abstract}
Voiculescu's free probability theory -- which was introduced in an
operator algebraic context,
but has since then developed into an
exciting theory with a lot of links to other fields -- has
an interesting combinatorial facet: it can be described
by the combinatorial concept of multiplicative functions
on the lattice of non-crossing partitions. In this survey
I want to explain this connection -- without assuming
any knowledge 
neither on free probability theory nor on non-crossing
partitions.
\end{abstract}

\maketitle

\section{{\bf Introduction}}
The notion of \lq freeness' was introduced by Voiculescu around 1985
in connection with some old questions in the theory of operator
algebras.
But Voiculescu separated freeness from this
special context and emphasized it as a concept being worth to
be investigated on its own sake.
Furthermore, he advocated the point of
view that freeness behaves in some respects like an analogue of
the classical probabilistic concept \lq independence' - but an analogue
for non-commutative random variables.

This point of view turned out to be very succesful. Up to now there
has evolved a free probability theory with a lot of links to quite
different parts of mathematics and physics. In this survey, I want to
present some introduction into this lively field; my main
emphasis will be on the combinatorial aspects of freeness -- namely,
it has turned out that in the same way as classical probability theory
is linked with all partitions of sets, free probability theory
is linked with the so-called non-crossing partitions. These partitions
have a lot of nice properties, reflecting features of freeness.

\section{{\bf Independence and Freeness}}
Let me first recall the classical notion of independence for random
variables. Consider two 
real-valued random variables $X$ and $Y$ living
on some probability space. In particular, we have an expectation
$\ff$ which is given by integration with respect to the given
probability measure $P$, i.e. we have
\begin{equation}
\ff\lb f(X,Y)\rb=\int f(X(\omega),Y(\omega))dP(\omega)
\end{equation}
for all bounded functions of two variables. To simplify things and
getting contact with a combinatorial point of view, let us assume that
$X$ and $Y$ are bounded, so that all their moments exist
(and furthermore, their distribution is determined by their moments).
Then we can describe independence as a concrete rule
for calculating mixed moments in $X$ and $Y$ -- i.e. the collection
of all expectations of the form $\ff\lb X^{n_1}Y^{m_1}X^{n_2}Y^{m_2}\dots\rb$
for all $n_i,m_i\geq 0$ --
out of the moments of
$X$ -- i.e. $\ff\lb X^n\rb$ for all $n$ -- and the moments of $Y$ --
i.e. $\ff\lb Y^n\rb$ for all $n$. Namely, independence of $X$ and $Y$ just
means:
\begin{equation}
\ff\lb X^{n_1}Y^{m_1}\dots X^{n_k}Y^{m_k}\rb=\ff\lb 
X^{n_1+\dots+n_k}\rb\cdot
\ff\lb Y^{m_1+\dots+m_k}\rb.
\end{equation}
For example, if $X$ and $Y$ are independent we have
\begin{equation}
\ff\lb XY\rb=\ff\lb X\rb \ff\lb Y\rb
\end{equation}
and
\begin{equation}
\ff\lb XXYY\rb=\ff\lb XYXY\rb=\ff\lb XX\rb\ff\lb YY\rb.
\end{equation}

Let us now come to the notion of freeness. This is an analogue for
independence in the sense that it provides also 
a rule for calculating mixed moments
of $X$ and $Y$ out of the single moments of $X$ and the single 
moments of $Y$. But freeness is a non-commutative concept: $X$ and
$Y$ are not classical random variables any more, but non-commutative
random variables. This just means that we are dealing with a
unital algebra $\cA$ (in general non-commutative) equipped with
a unital linear functional $\ff:\cA\to\CC$, $\ff(1)=1$. (For a lot
of questions it is important that the free theory is consistent if
our $\ff$'s are also positive, i.e. states; but for our more combinatorial
considerations this does not play any role).
Non-commutative random variables are elements in the given algebra
$\cA$ and we define freeness for such random variables as follows.

\begin{defs}
The non-commutative random variables $X,Y\in\cA$ are called {\it free}
(with respect of $\ff$), if
\begin{equation}
\ff\lb p_1(X)q_1(Y)p_2(X)q_2(Y)\dots\rb=0
\end{equation}
(finitely many factors), 
whenever the $p_i$ and the $q_j$ are polynomials such that
\begin{equation}
\ff\lb p_i(X)\rb=0=\ff\lb q_j(Y)\rb
\end{equation}
for all $i,j$.
\end{defs}

As mentioned above, this should be seen as a rule for calculating 
mixed moments in $X$ and $Y$ out of moments of $X$ and moments of $Y$.
In contrary to the case of independence, this is not so obvious from
the definition. So let us look at some examples to get an idea of that
concept. In the following $X$ and $Y$ are assumed to be free and we will
look at some mixed moments.

The simplest mixed moment is $\ff\lb XY\rb$. Our above definition
tells us immediately that 
\begin{equation}\ff\lb XY\rb=0\qquad\text{if $\ff\lb X\rb=0=\ff\lb Y\rb$.}
\end{equation} 
But what about the general case when $X$ and $Y$ are not centered. 
Then we do the following trick: Since our definition allows us to use
polynomials in $X$ and $Y$ -- we should perhaps state explicitely that
polynomials with constant terms are allowed -- we just look at the 
centered variables $p(X)=X-\ff\lb X\rb 1$ and $q(Y)=Y-\ff\lb Y\rb1$ and our 
definition of freeness yields
\begin{equation} \begin{split}
0=\ff\lb p(X)q(Y)\rb&=\ff\lb(X-\ff\lb X\rb 1)(Y-\ff\lb Y\rb 1)\rb\\
&=\ff\lb XY\rb-\ff\lb X\rb \ff\lb Y\rb,
\end{split} \end{equation}  
which implies that we have in general
\begin{equation}
\ff\lb XY\rb=\ff\lb X\rb \ff\lb Y\rb.
\end{equation}

In the same way one can deal with more complicated mixed moments.
E.g. by looking at
\begin{equation} 
\ff\lb (X^2-\ff\lb X^2\rb 1)(Y^2-\ff\lb Y^2\rb 1)\rb=0 \end{equation} 
we get
\begin{equation}
\ff\lb XXYY\rb=\ff\lb XX\rb\ff\lb YY\rb. \label{A}
\end{equation}

Up to now there is no difference to the results for independent random
variables.
But consider next the mixed moment $\ff\lb XYXY\rb$. Again we can calculate
this moment by using
\begin{equation} 
\ff\lb(X-\ff\lb X\rb 1)(Y-\ff\lb Y\rb 
1)(X-\ff\lb X\rb 1)(Y-\ff\lb Y\rb 1)\rb=0.
\end{equation} 
Resolving this for $\ff\lb XYXY\rb$ (and using induction for the other
appearing mixed moments, which are of smaller order) we obtain
\begin{multline}
\ff\lb XYXY\rb=\ff\lb XX\rb \ff\lb Y\rb \ff\lb Y\rb\\
+\ff\lb X\rb \ff\lb X\rb \ff\lb YY\rb 
-\ff\lb X\rb \ff\lb Y\rb \ff\lb X\rb\ff\lb Y\rb. \label{B}
\end{multline}

From this we see that freeness is something different from
independence; indeed it seems to be more complicated: in the independent
case we only get a product of moments of $X$ and $Y$, whereas here in
the free case we have a sum of such product.
Furthermore, from the above examples one sees that variables which are
free cannot commute in general: if $X$ and $Y$ commute then
$\ff\lb XXYY\rb$ must be the same as $\ff\lb XYXY\rb$, which gives, by
comparision between 
(\ref{A}) and (\ref{B}) very special relations between
different moments of $X$ and of $Y$. Taking the 
analogous relations for
higher mixed moments into account it turns out that commuting variables
can only be free if at least one  of them is a constant. This means
that freeness is a real non-commutative concept; it cannot be considered
as a special kind of dependence between classical random variables.

The main problem (at least from a combinatorial point of view) with
the definition of freeness is to understand the combinatorial 
structure behind this concept. Freeness is a rule for calculating
mixed moments, and although we know in
principle how to calculate these mixed moments,
this rule is not very explicit. Up to this point, 
it is not clear how one can
really work with this concept.

Two basic problems in free probability theory are the investigation
of the sum and of the product of two free random variables. 
Let $X$ and $Y$ be free, then we want to understand $X+Y$ and $XY$.
Both these problems were solved by Voiculescu by some operator algebraic
methods, but the main message of my survey will be
that there is a beautiful combinatorial
structure behind these operations.
First, we will concentrate on the problem of the sum, which results in the
notion of the additive free convolution. Later, we will also consider
the problem of the product (multiplicative free convolution).

\section{{\bf Additive free convolution}}
Let us state again the problem: We are given $X$ and $Y$, i.e. we
know their moments $\ff\lb X^n\rb$ and $\ff\lb Y^n\rb$ 
for all $n$. We assume
$X$ and $Y$ are free and we want to understand $X+Y$, i.e. we want
to calculate all moments $\ff\lb (X+Y)^n\rb$. Since the moments of
$X+Y$ are just sums of mixed moments in $X$ and $Y$, we know for sure
that there must be a rule to express the moments of $X+Y$ in terms of
the moments of $X$ and the moments of $Y$. But how can we describe this
rule explicitely?
Again it is a good point of view to consider this problem in analogy with
the classical problem of taking the sum of independent random variables.
This classical problem is of course intimately connected with the
classical notion of convolution of probability measures. By analogy,
we are thus dealing with (additive) free convolution.

Usually these operations are operations on the level of probability
measures, not on the level of moments, but (at least in the case
of self-adjoint bounded random variables) 
these two points of view determine each other uniquely.
So, instead of talking about the collection of all moments of some
random variable $X$ we can also consider the distribution $\mu_X$ 
of $X$ which is
a probability measure on $\RR$ whose moments are just the moments of $X$, i.e.
\begin{equation}
\ff\lb X^n\rb=\int t^nd\mu_X(t).
\end{equation}

Let us first take a look at the classical situation before we deal
with the free counterpart.

\subsection{Classical convolution}
Assume $X$ and $Y$ are independent, then we know that the moments of
$X+Y$ can be written in terms of the moments of $X$ and the moments 
of $Y$ or, equivalently, the distribution 
$\mu_{X+Y}$ of $X+Y$ can be calculated
somehow out of the distribution $\mu_X$ of $X$ and the distribution
$\mu_Y$ of $Y$. Of course, this \lq somehow' is nothing else than the
convolution of probability measures,
\begin{equation}
\mu_{X+Y}=\mu_X*\mu_Y,
\end{equation}
a well-understood operation.

The main analytical tool for handling this convolution is the concept
of the Fourier transform (or characteristic function of the random variable).
To each probability measure $\mu$ or to each random variable $X$ with
distribution $\mu$ (i.e. $\mu_X=\mu$) we assign a function $\cF_{\mu}$
on $\RR$ given by
\begin{equation}
\cF_{\mu}(t):=\int e^{itx}d\mu(x)=\ff\lb e^{itX}\rb.
\end{equation}
From our combinatorial point of view it is the best to view $\cF_{\mu}$
just as a formal power series in the indeterminate $t$. If we
expand
\begin{equation}
\cF_{\mu}(t)=\sum_{n=0}^\infty \frac{(it)^n}{n!}\ff\lb X^n\rb
\end{equation}
then we see that the Fourier transform is essentially the exponential 
generating series in the moments of the considered random variable.

The importance of the Fourier transform in the context of the classical
convolution comes from the fact that it behaves very nicely with
respect to convolution, namely
\begin{equation}
\cF_{\mu*\nu}(t)=\cF_{\mu}(t)\cdot\cF_{\nu}(t).
\end{equation}
If we take the logarithm of this equation then we get
\begin{equation}
\log\cF_{\mu*\nu}(t)=\log\cF_{\mu}(t)+\log\cF_{\nu}(t),
\end{equation}
i.e. the logarithm of the Fourier transform linearizes the classical
convolution.

\subsection{Free convolution}
Now consider $X$ and $Y$ which are free. Then freeness ensures that
the moments of $X+Y$ can be expressed somehow in terms of the moments
of $X$ and the moments of $Y$, or, equivalently, the distribution 
$\mu_{X+Y}$ of
$X+Y$ depends somehow on the distribution $\mu_X$ 
of $X$ and the distribution $\mu_Y$
of $Y$. Following Voiculescu \cite{V2},
we denote this \lq somehow' by $\boxplus$,
\begin{equation}
\mu_{X+Y}=\mu_X\boxplus\mu_Y,
\end{equation}
and call this operation {\it (additive) free convolution}.
This is of course just a notation 
for the object which we want to understand and
the main question is whether we can find some analogue of the
Fourier transform which allows us to deal effectively with $\bplus$.
This question was solved by Voiculescu 
\cite{V2} in the affirmative: He provided
an analogue of the logarithm of the Fourier transform which he called
$R$-transform. Thus, to each probability measure $\mu$ he assigned an
$R$-transform $R_\mu(z)$ -- which is in an analytic function on
the upper half-plane, but which we will view again as a formal power
series in the indeterminate $z$ -- in such a way that this $R$-transform
behaves linear with respect to free convolution, i.e.
\begin{equation}
R_{\mu\boxplus\nu}(z)=R_\mu(z)+R_\nu(z).
\end{equation}
Up to now I have just described what properties the $R$-transform should
have for being useful in our context. The main point is that Voiculescu
could also provide an algorithm for calculating such an object.
Namely, the $R$-transform has to be calculated from the
Cauchy-transform $G_\mu$ which is defined by
\begin{equation}
G_\mu(z)=\int\frac 1{z-x}d\mu(x)=\ff\lb \frac 1{z-X}\rb.
\end{equation}
This Cauchy-transform determines the $R$-transform uniquely by the
prescription that $G_\mu(z)$ and $R_\mu(z)+1/z$ are inverses of each other
with respect to composition:
\begin{equation}
G_\mu\lb R_\mu(z)+1/z\rb=z.
\end{equation}

Although the logarithm of the Fourier transform and the $R$-transform
have analogous properties with respect to classical and free convolution,
the above analytical description looks quite different for both objects.

My aim is now to show that if we go over to a combinatorial level then
the description of classical convolution $*$ and free
convolution $\boxplus$ becomes much more similar (and, indeed, we can
understand the above formulas as translations of combinatorial
identities into generating power series).


\subsection{Cumulants}
The connection of the above transforms with combinatorics comes from
the following observation. The Fourier-transform and the Cauchy-transform
are both formal power series in the moments of the considered distribution.
If we write the logarithm of the Fourier-transform and the $R$-transform
also as formal power series then their coefficients must be some functions
of the moments. In the classical case this coefficients are essentially
the so-called 
{\it cumulants} of the distribution. In analogy we will call
the coefficients of the $R$-transform the {\it free cumulants}. The
fact that $\log\cF$ and $R$ behave additively under classical and
free convolution, respectively, implies of course for the coefficients
of these series that they, too, are additive with respect to the respective
convolution. This means the whole problem of describing the 
structure of the corresponding convolution has been shifted to
the understanding of the connection between moments and cumulants.

Let us state this shift of the problem again more explicitely --
for definiteness in the case of the classical convolution.
We have random variables $X$ and $Y$ which are independent and
we want to calculate the moments of $X+Y$ out of the moments of
$X$ and the moments of $Y$. But it is advantegous (in the free
case even much more than in the classical case) to go over from
the moments to new quantities $c_n$, which we call cumulants, and
which behave additively with repect
to the convolution, i.e. we have $c_n(X+Y)=c_n(X)+c_n(Y)$.
The whole problem has thus been shifted to the connection between
moments and cumulants. Out of the moments we must calculate cumulants
and the other way round.
The connection for the first two moments is quite easy, namely
\begin{equation}
m_1=c_1
\end{equation}
and
\begin{equation}
m_2=c_2+c_1^2
\end{equation}
(i.e. the second cumulant $c_2=m_2-m_1^2$ is just the variance of the
measure). In general, the $n$-th moment is a polynomial in the cumulants
$c_1,\dots,c_n$, but it is very hard to write down a concrete formula
for this.
Nevertheless there is a very nice way to understand the combinatorics
behind this connection, and this is given by the concept of
multiplicative functions on the lattice of all partitions.

So let me first recall this connection between classical probability
theory and multiplicative functions before I am going to
convince you that the
description of free probability theory can be done in a very
analogous way.

\section{{\bf Combinatorial aspects of classical convolution}}
On a combinatorial level classical convolution can be described
quite nicely with the 
help of multiplicative functions on the lattice
of all partitions. 
I extracted my knowledge on this point of view from the 
fundamental work of Rota \cite{R,DRS}.
Let me briefly recall these well-known notions.

\subsection{Lattice of all partitions and their incidence algebra}
Let $n$ be a natural number. A {\it partition} $\pi=
\{V_1,\dots,V_k\}$ of the set
$\{1,\dots,n\}$ is a decomposition of $\{1,\dots,n\}$ into disjoint
and non-empty sets $V_i$, i.e. $V_i\not=\emptyset$, $V_i\cap V_j=
\emptyset$ ($i\not=j$) and $\bigcup_{i=1}^k V_i=\{1,\dots,n\}$.
The elements $V_i$ are called the {\it blocks} of the partition $\pi$.
We will denote the set of all partitions of $\{1,\dots,n\}$ by
$\cP(n)$. This set becomes a lattice if we introduce the following
partial order (called {\it refinement order}): $\pi\leq \sigma$ if
each block of $\sigma$ is a union of blocks of $\pi$. We will denote
the smallest and the biggest element of $\cP(n)$ 
-- consisting of $n$ blocks and one block, respectively -- by special symbols,
namely
\begin{equation}
0_n:=\{(1),(2),\dots,(n)\},\qquad 1_n:=\{(1,2,\dots,n)\}.
\end{equation}
An example for the refinement order is the following:
\begin{equation}\{(1,3),(2),(4)\}\leq \{(1,3),(2,4)\}.\end{equation} 
Of course, there is no need to consider only partitions of the
sets $\{1,\dots,n\}$, the same definitions apply for arbitrary sets 
$S$ and we have a natural isomorphism $\cP(S)\cong\cP(\vert S
\vert)$.

We consider now the collection of all partition lattices $\cP(n)$ 
for all $n$,
\begin{equation}
\cP:=\bigcup_{n\in\NN}\cP(n),
\end{equation} 
and in such a frame 
(of a locally finite poset) there exists the combinatorial 
notion of an incidence algebra, which is just the set of special
functions with two arguments from these partition lattices:
The {\it incidence algebra} consists of all functions
\begin{equation}
f:\bigcup_{n\in\NN}(\cP(n)\times\cP(n))\to\CC
\end{equation} 
subject to the following condition:
\begin{equation}
f(\pi,\sigma)=0,\qquad\text{whenever $\pi\not\leq \sigma$}
\end{equation} 
Sometimes we will also consider functions of one element; these are
restrictions of functions of two variables as above to the case
where the first argument is equal to 
some $0_n$,
i.e.
\begin{equation}
f(\pi)=f(0_n,\pi)\qquad\text{for $\pi\in\cP(n)$.}
\end{equation} 

On this incidence algebra we have a canonical
{\it (combinatorial) convolution} $\star$: For $f$ and $g$
functions as above, we define $f\star g$ by
\begin{equation}
(f\star g)(\pi,\sigma):=\sum
\Sb \tau \in \cP(n)\\ \pi\leq\tau\leq\sigma\endSb f(\pi,\tau)
g(\tau,\sigma)\qquad\text{for $\pi\leq\sigma\in\cP(n).$}
\end{equation} 
One should note that apriori this combinatorial convolution $\star$ has 
nothing to do with our probabilistic convolution $*$ for probability
measures;
but of course we will establish a connection between these two
concepts later on.

The following special functions from the incidence algebra are of
prominent interest:
The neutral element $\delta$ for the 
combinatorial convolution is given by
\begin{equation}
\delta(\pi,\sigma)=\begin{cases}
1,&\pi=\sigma\\
0,&\text{otherwise.}
\end{cases}
\end{equation} 
The {\it zeta function} is defined by
\begin{equation}
Zeta(\pi,\sigma)=\begin{cases}
1,& \pi\leq \sigma\\
0,&\text{otherwise.}
\end{cases}
\end{equation} 
It is an easy exercise to check that the zeta function possesses an
inverse; this is called the {\it M\"obius function} of our
lattice:
$Moeb$ is defined by
\begin{equation}
Moeb\star Zeta=Zeta\star Moeb=\delta.
\end{equation} 

\subsection{Multiplicative functions}
The whole incidence algebra is a quite big object which is in general not
so interesting; in particular, one should note that up to now, although
we have taken the union over all $n$, there was no real connection between
the involved lattices for different $n$.
But now we concentrate on a subclass of the incidence algebra which only
makes sense if there exists
a special kind of relation between the $\cP(n)$ for different
$n$ -- this subclass consists of the so-called 
multiplicative functions.

Our functions $f$ of the incidence algebra have two arguments --
$f(\pi,\sigma)$ -- but since non-trivial things
only happen for $\pi\leq\sigma$ we can also
think of $f$ as a function of the intervals in $\cP$, i.e. of the sets 
$\lb \pi,\sigma\rb:=\{\tau\in\cP(n)
\mid \pi\leq\tau\leq\sigma\}$ for $\pi,\sigma
\in\cP(n)$ ($n\in\NN$) and $\pi\leq\sigma$.
One can now easily check that for our partition lattices such intervals
decompose always in a canonical way in a product of full partition
lattices, i.e. for $\pi,\sigma\in\cP(n)$ with $\pi\leq\sigma$ there
are canonical natural numbers $k_1,k_2,\dots$ such that
\begin{equation}
\lb\pi,\sigma\rb\cong \cP(1)^{k_1}\times \cP(2)^{k_2}\times\cdots.
\end{equation} 
(Of course, only finitely many factors are involved.)
A multiplicative function factorizes  
by definition in an analogous way according to
this factorization of intervals:
For each sequence $(a_1,a_2,\dots)$ of complex numbers we define
the corresponding {\it multiplicative function} $f$ 
(we denote the dependence of $f$ on this sequence by $f\reli (a_1,a_2,\dots)$)
by the
requirement
\begin{equation}
f(\pi,\sigma):=a_1^{k_1}a_2^{k_2}\dots\qquad\text{if}\qquad
\lb\pi,\sigma\rb\cong \cP(1)^{k_1}\times \cP(2)^{k_2}\times\cdots.
\end{equation} 
Thus we have in particular that $f(0_n,1_n)=a_n$, everything else
can be reduced to this by factorization.
It can be seen directly that the combinatorial convolution of
two multiplicative functions is again multiplicative.

Let us look at some examples for the calculation of
multiplicative functions.
\begin{equation} \begin{split}
\lb \{(1,3),(2),(4)\},\{(1,2,3,4)\}\rb&\cong
\lb\{(1),(2),(4)\},\{(1,2,4)\}\rb\\&\cong\cP(3),
\end{split} \end{equation}   
thus
\begin{equation}
f(\{(1,3),(2),(4)\},\{(1,2,3,4)\})=a_3.
\end{equation} 
Note in particular that if the first argument is equal to some $0_n$, then
the factorization is according to the block structure of the second
argument, and hence multiplicative functions of one
variable are really multiplicative with respect to the blocks.
 E. g., we have
\begin{multline}
\lb\{(1),(2),(3),(4),(5),(6),(7),(8)\},\{(1,3,5),(2,4),(6),(7,8)\}\rb
\cong\\ \lb\{(1),(3),(5)\},\{(1,3,5)
\}\rb\times\lb \{(2),(4)\},\{(2,4)\}\rb\times\\
\times \lb\{(6)\},\{(6)\}\rb\times \lb\{(7),(8)\},\{(7,8)\}\rb,
\end{multline}
and hence for the multiplicative function of one argument
\begin{multline}
f(\{(1,3,5),(2,4),(6),(7,8)\})=\\ f(\{(1,3,5)\}) \cdot f(\{(2,4)\})
\cdot
f(\{(6)\}) \cdot f(\{(7,8)\})=a_3a_2a_1a_2.
\end{multline}
The special functions $\delta$, $Zeta$, and $Moeb$ are all
multiplicative with determining sequences as follows:
\begin{align} 
\delta&\reli (1,0,0,\dots)\\
Zeta&\reli (1,1,1,\dots)\\
Moeb&\reli ((-1)^{n-1}(n-1)!)_{n\geq 1}
\end{align} 
 
\subsection{Connection between probabilistic and combinatorial
convolution}
Recall our strategy for describing classical convolution combinatorially:
Out of the moments $m_n=\ff(X^n)$ ($n\geq 1$) of a random variable $X$ we want
to calculate some new quantities $c_n$ ($n\geq 1$) -- which we call
cumulants -- that behave additively
with respect to convolution.
The problem is to describe the relation between the moments and the
cumulants. This relation can be formulated in a nice way by
using the concept of multiplicative functions on all partitions.
Since such functions are determined by a sequence of complex numbers,
we can use the sequence of moments to define a multiplicative function 
$M$ (moment function) 
and the sequence of cumulants to define another multiplicative
function $C$ (cumulant function). 
It is a well known fact (although not to localize easily in this form
in the literature) \cite{R,Sh} that
the relation between these two multiplicative funtions
is just given by taking the combinatorial convolution with
the zeta function or with the M\"obius function.

\begin{thm}
Let $m_n$ and $c_n$ be the moments and the classical cumulants, 
respectively, of a random variable $X$. Let $M$ and $C$ be the 
corresponding multiplicative functions on the lattice of all partitions, i.e.
\begin{equation}
M\reli (m_1,m_2,\dots),\qquad C\reli (c_1,c_2,\dots).
\end{equation} 
Then the relation between $M$ and $C$ is given by
\begin{equation}
M=C\star Zeta,
\end{equation} 
or equivalently by
\begin{equation}
C=M\star  Moeb.\end{equation} 
\end{thm}

Let me also point out that this combinatorial description is
essentially equivalent 
to the previously mentioned analytical description
of classical convolution via the Fourier transform.
Namely, if we denote by
\begin{equation}
A(z):=1+\sum_{n=1}^\infty \frac{m_n}{n!}z^n,\qquad
B(z):=\sum_{n=1}^\infty \frac {c_n}{n!}z^n\end{equation} 
the exponential power series of the moment and cumulant sequences,
respectively, then it is a well known fact 
\cite{R} that the statement
of the above theorem translates in terms of these series into
\begin{equation}
A(z)=\exp B(z)\qquad\text{or} \qquad B(z)=\log A(z).
\end{equation} 
But since the Fourier transform $\cF_{\mu}$ of the random variable $X$ 
(with $\mu=\mu_X$) is
connected with $A$ by
\begin{equation}
\cF_{\mu}(t)=A(it),
\end{equation} 
this means that
\begin{equation}
B(it)=\log \cF_{\mu}(t),\end{equation} 
which is exactly the usual description of the classical cumulants -- 
that they are given by the coefficents of the logarithm of
the Fourier transform; the additivity of the logarithm of the
Fourier transform under classical convolution is of course
equivalent to the
same property for the cumulants.

\section{{\bf Combinatorial aspects of free convolution}}
Now we switch from classical convolution to free convolution. Where\-as
on the analytical level the analogy between the logarithm of
the Fourier transform and the $R$-transform is not so obvious, on
the combinatorial level things become very clear: The description
of free convolution is the same as the description of
classical convolution, the only difference is that one has to
replace all partitions by the so-called non-crossing partitions.

\subsection{Lattice of non-crossing partitions and their incidence algebra}
We call a partition $\pi\in \cP(n)$ {\it crossing} if there 
exist four numbers $1\leq i<k<j<l\leq n$ such that $i$ and $j$ are in
the same block, $k$ and $l$ are in the same block, but $i,j$ and $k,l$
belong to two different blocks.
If this situation does not happen, then we call $\pi$ 
{\it non-crossing}.
The set of all non-crossing partitions in $\cP(n)$ is dentoted
by $NC(n)$, i.e.
\begin{equation}
NC(n):=\{\pi\in\cP(n)\mid \text{$\pi$ non-crossing.}\}
\end{equation} 
Again, this set becomes a lattice with respect to the refinement order. 
Of course, $0_n$ and $1_n$ are non-crossing and they are
the smallest and the biggest element of $NC(n)$, respectively.

The name \lq non-crossing' becomes quite clear in a graphical
representation of partitions:
The partition 
\setlength{\unitlength}{0.3cm}
$$\pi=\{(1,3,5),(2),(4)\}
\qquad=\qquad
\begin{picture}(4,2)\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){4}}
\put(2,0){\line(0,1){2}}
\put(4,0){\line(0,1){2}}
\put(1,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(-0.3,2.2){1}
\put(0.7,2.2){2}
\put(1.7,2.2){3}
\put(2.7,2.2){4}
\put(3.7,2.2){5}
\end{picture}
$$
is non-crossing, whereas
$$\pi=\{(1,3,5),(2,4)\}
\qquad=\qquad
\begin{picture}(4,2)\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){4}}
\put(2,0){\line(0,1){2}}
\put(4,0){\line(0,1){2}}
\put(1,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(1,1){\line(1,0){2}}
\put(-0.3,2.2){1}
\put(0.7,2.2){2}
\put(1.7,2.2){3}
\put(2.7,2.2){4}
\put(3.7,2.2){5}
\end{picture}
$$
is crossing.

One should note, that 
the linear order
of the set $\{1,\dots,n\}$ is of course important for deciding whether
a partition is crossing or non-crossing. Thus, in contrast to the case
of all partitions, non-crossing partitions only make sense for a set
with a linear order. However, one should also note that instead of
the linear order of $\{1,\dots,n\}$ we could also put the points
$1,\dots,n$ on a circle and consider them with circular order.
The concept \lq non-crossing' is also compatible with this.

For $n=1$, $n=2$, and $n=3$ all partitions are non-crossing, for
$n=4$ only $\{(1,3),(2,4)\}$ is crossing. The following figure
shows $NC(4)$. Note the high symmetry
of that lattice compared to $\cP(4)$.

\newsavebox{\NCa}
\savebox{\NCa}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){3}}
\put(1,0){\line(0,1){2}}
\put(2,0){\line(0,1){2}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCb}
\savebox{\NCb}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(1,0){\line(1,0){2}}
\put(2,0){\line(0,1){2}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCc}
\savebox{\NCc}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){3}}
\put(1,1){\line(0,1){1}}
\put(2,0){\line(0,1){2}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCd}
\savebox{\NCd}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){3}}
\put(1,0){\line(0,1){2}}
\put(2,1){\line(0,1){1}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCe}
\savebox{\NCe}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){2}}
\put(1,0){\line(0,1){2}}
\put(2,0){\line(0,1){2}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCf}
\savebox{\NCf}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){1}}
\put(1,0){\line(0,1){2}}
\put(2,0){\line(0,1){2}}
\put(3,0){\line(0,1){2}}
\put(2,0){\line(1,0){1}}}

\newsavebox{\NCg}
\savebox{\NCg}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,0){3}}
\put(1,1){\line(0,1){1}}
\put(2,1){\line(0,1){1}}
\put(3,0){\line(0,1){2}}
\put(1,1){\line(1,0){1}}}

\newsavebox{\NCh}
\savebox{\NCh}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(2,0){\line(0,1){2}}
\put(2,0){\line(1,0){1}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCi}
\savebox{\NCi}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(2,0){\line(0,1){2}}
\put(1,0){\line(1,0){1}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCj}
\savebox{\NCj}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(2,0){\line(0,1){2}}
\put(0,0){\line(1,0){1}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCk}
\savebox{\NCk}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(2,1){\line(0,1){1}}
\put(1,0){\line(1,0){2}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCl}
\savebox{\NCl}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,1){\line(0,1){1}}
\put(2,1){\line(0,1){1}}
\put(0,0){\line(1,0){3}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCm}
\savebox{\NCm}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,1){\line(0,1){1}}
\put(2,0){\line(0,1){2}}
\put(0,0){\line(1,0){2}}
\put(3,0){\line(0,1){2}}}

\newsavebox{\NCn}
\savebox{\NCn}(3,2){
\thicklines
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(2,0){\line(0,1){2}}
\put(3,0){\line(0,1){2}}}

$$\usebox{\NCa}$$
\vskip0.5cm
$$\usebox{\NCb}\qquad\usebox{\NCc}\qquad\usebox{\NCd}
\qquad\usebox{\NCe}\qquad\usebox{\NCf}\qquad\usebox{\NCg}$$
\vskip0.5cm
$$\usebox{\NCh}\qquad
\usebox{\NCi}\qquad
\usebox{\NCj}\qquad
\usebox{\NCk}\qquad
\usebox{\NCl}\qquad
\usebox{\NCm}$$
\vskip0.5cm
$$\usebox{\NCn}$$
\vskip0.5cm

Non-crossing partitions were introduced by Kreweras \cite{K}
in 1972 (but see also \cite{B}) and since then there
have been some combinatorial investigations on this lattice,
e.g. \cite{P,E1,E2,SU}.
But it seems that the concept of incidence algebra and multiplicative
functions for this lattice have not received any interest so far.
Motivated by my investigations \cite{Sp1} on freeness I introduced
these concepts in \cite{Sp2}.
It is quite clear that this goes totally in parallel to the case
of all partitions: 
We consider the collection of the lattices of non-crossing
partitions for all
$n$,
\begin{equation}
NC:=\bigcup_{n\in\NN}NC(n),\end{equation} 
and the incidence algebra is as before the set of 
special functions with two arguments from these lattices:
The {\it incidence algebra of non-crossing partitions} 
consists of all functions
\begin{equation}
f:\bigcup_{n\in\NN}(NC(n)\times NC(n))\to\CC\end{equation} 
subject to the following condition:
\begin{equation}
f(\pi,\sigma)=0,\qquad
\text{whenever $\pi\not\leq \sigma$.}
\end{equation} 
Again, sometimes we will
also consider functions of one element; these are
restrictions of functions of two variables
as above to the case where the first element is equal to 
some $0_n$,
i.e.
\begin{equation}
f(\pi)=f(0_n,\pi)\qquad\text{for $\pi\in NC(n)$.}\end{equation} 

Again, we have a canonical 
{\it (combinatorial) convolution} $\star$ on this
incidence algebra: For functions $f$ and $g$
as above, we define $f\star g$ by
\begin{equation}
(f\star g)(\pi,\sigma):=\sum\Sb
\tau\in NC(n)\\ \pi\leq\tau\leq\sigma\endSb 
f(\pi,\tau)
g(\tau,\sigma)\qquad\text{for $\pi\leq\sigma\in NC(n)$}.
\end{equation} 

As before we have the following 
important special functions: 
The neutral element $\delta$ for the 
combinatorial convolution $\star$ is given by
\begin{equation}
\delta(\pi,\sigma)=\begin{cases}
1,&\pi=\sigma\\
0,&\text{otherwise.}
\end{cases}
\end{equation} 
The {\it zeta function} is defined by
\begin{equation}
zeta(\pi,\sigma)=\begin{cases}
1,& \pi\leq \sigma\\
0,&\text{otherwise.}
\end{cases}
\end{equation} 
Again, 
the zeta function possesses an
inverse, which we call {\it M\"obius function}:
$moeb$ is defined by
\begin{equation}
moeb\star zeta=zeta\star moeb=\delta.
\end{equation} 

\subsection{Multiplicative functions on non-crossing partitions}
Where\-as the notion of an incidence algebra and the corresponding
combinatorial convolution is a very general notion (which can be
defined on any locally finite poset), the concept of a multiplicative
function requires a very special property of the considered lattices,
namely that each interval can be decomposed into a
product of full lattices. This was fulfilled in the case
of all partitions and it is not hard to see that we have the
same property also for non-crossing partitions \cite{Sp2,
NS1}: 
For all $\pi,\sigma\in NC(n)$ with $\pi\leq \sigma$ there exist
canonical natural numbers $k_1,k_2,\dots$ such that
\begin{equation}
\lb \pi,\sigma\rb\cong NC(1)^{k_1}\times NC(2)^{k_2}\times
\dots.
\end{equation}

Having this factorization property at hand it is quite natural to
define a {\it multiplicative function $f$
(for non-crossing partitions)} corresponding to a sequence
$(a_1,a_2,\dots)$ of complex numbers by the requirement
that
\begin{equation}
f(\pi,\sigma):=a_1^{k_1}a_2^{k_2}\dots
\end{equation} 
if $\lb\pi,\sigma\rb$ has a factorization as above.
Again we use the notation
$f\reli (a_1,a_2\dots)$ to denote the dependence of $f$ on 
the sequence $(a_1,a_2,\dots)$.

As before, the special functions $\delta$, $zeta$, and $moeb$ are 
all multiplicative with the following determining sequences:
\begin{align}
\delta&\reli (1,0,0,\dots)\\
zeta&\reli (1,1,1,\dots)\\
moeb&\reli ((-1)^{n-1}c_{n-1})_{n\geq 1},
\end{align}
where $c_n$ are the Catalan numbers.

Let me stress the following: Consider $\pi\in NC(n)
\subset\cP(n)$. Then the
factorization for intervals of the form $\lb 0_n,\pi\rb$ is 
the same in $\cP(n)$ and in $NC(n)$, i.e. we have the
same $k_i$ in both decompositions:
\begin{multline}
\lb 0_n,\pi\rb_{\cP(n)}\cong \cP(1)^{k_1}\times\cP(2)^{k_2}
\times\dots
\\ \Longleftrightarrow
\lb 0_n,\pi\rb_{NC(n)}\cong NC(1)^{k_1}\times NC(2)^{k_2}
\times\dots.
\end{multline}
For intervals of the form $\lb \pi,1_n\rb$, however, 
the factorization
might be quite different -- reflecting the different structure of
both lattices.
For example, for $\pi=\{(1,3),(2),(4)\}\in NC(4)\subset\cP(4)$
we have
\begin{equation}
\lb\{(1,3),(2),(4)\},
\{(1,2,3,4)\}\rb_{\cP(4)}\cong \cP(3),
\end{equation} 
but
\begin{equation}
\lb\{(1,3),(2),(4)\},\{(1,2,3,4)\}\rb_{NC(4)}
\cong NC(2)\times NC(2).
\end{equation} 
The latter factorization comes from the fact that, by the
non-crossing property, the block
$(1,3)$  separates the blocks $(2)$ and $(4)$ 
from each other.

\subsection{Connection between free convolution and
combinatorial convolution}
As in the case of classical convolution we want to describe
free convolution by quantities $k_n$ ($n\geq 1$) which behave
additively unter free convolution. These $k_n$ are calculated
somehow out of the moments $m_n$ of a random variable $X$ --
they should essentially be the coefficients of the $R$-transform --
and they will be called the 
{\it free cumulants} of $X$. The question is
how we calculate the cumulants out of the moments and vice versa.
The answer is very simple: it works 
as in the classical
case,  just replace all partitions by non-crossing partitions.
\begin{thm}[Speicher \cite{Sp2}]
Let $m_n$ and $k_n$ be the moments and the free cumulants,
respectively, of a random variable $X$. Let $m$ and $k$ be
the corresponding multiplicative functions on the lattice
of non-crossing partitions, i.e.
\begin{equation}
m\reli (m_1,m_2,\dots),
\qquad k\reli (k_1,k_2,\dots).
\end{equation} 
Then the relation between $m$ and $k$ is given by
\begin{equation} 
m=k\star zeta,
\end{equation} 
or equivalently
\begin{equation} 
k=m\star moeb.
\end{equation} 
\end{thm}

The important point 
that I want to emphasize 
is that this combinatorial relation between
moments and free cumulants can again be translated into a relation
between the corresponding 
formal power series;  these
series are essentially
the Cauchy transform and the $R$-transform and their relation
is nothing but Voiculescu's formula for the $R$-transform.

Let us look at this more closely:  By taking into account the 
non-crossing character of the involved partitions, 
the relation $m=k\star zeta$
can be written more concretely in a recursive way as 
(where $m_0=1$)
\begin{equation}
m_n=\sum_{r=1}^n\sum\Sb i_1,\dots,i_r\geq 0\\ i_1+\dots
i_r+r=n\endSb k_rm_{i_1}\dots m_{i_r}.
\end{equation} 
Multiplying this by $z^n$, distributing the powers of $z$ and
summing over all $n$ this gives
\begin{equation} 
\sum_{n=0}^\infty m_nz^n=1+\sum_{n=1}^\infty\sum_{r=1}^\infty
\sum\Sb i_1,\dots,i_r\geq 0\\ i_1+\dots
i_r+r=n\endSb
k_rz^r m_{i_1}z^{i_1}\dots m_{i_r}z^{i_r},
\end{equation} 
which is easily recognized as a relation between the 
formal power series 
\begin{equation} 
C(z):=1+\sum_{n=1}^\infty m_nz^n\qquad\text{and} \qquad
D(z):=1+\sum_{n=1}^\infty k_nz^n
\end{equation} 
of the momens and of the free cumulants.
The above formula reads in terms of these power series as
\begin{equation} 
C(z)=D\lb zC(z)\rb,\end{equation} 
and the simple redefinitions
\begin{equation} 
G(z):=\frac {C(1/z)}z\qquad\text{and}\qquad
R(z)=\frac {D(z)-1}z
\end{equation} 
change this into
\begin{equation} 
G\lb R(z)+1/z\rb=z.\end{equation} 
But -- by noticing that the above defined function $G$ is nothing
but
the Cauchy transform -- this is exactly Voiculescu's formula for
the $R$-transform.

Thus we see: The analytical descriptions of the classical and the
free convolution via the logarithm of the Fourier transform and via
the $R$-transform are nothing but translations of the combinatorial
relations between
moments and cumulants into formal power 
series.
Whereas the analytical descriptions look quite different for both
cases the underlying combinatorial relations are very similar.
They have the same structure, the only difference is the 
replacement of all partitions by non-crossing partitions.

\section{{\bf Freeness and generalized cumulants}}
Whereas up to now I have described free cumulants as a good
object to deal with additive free convolution I will now show
that cumulants have a much more general  meaning: they are
the right concept to deal with the notion of freeness itself.
From this more general point of view we will also get a very
simple proof of the main property of free cumulants, that
they linearize free convolution. (In Sect.~5.3, we have presented
the connection between moments and cumulants, but we have
not yet given any idea why the cumulants from that theorem
are additive unter free convolution.)  

\subsection{Generalized cumulants}
Whereas I defined freeness in Sect.~2 only for two random
variables, I will now present the general case.

Again, we are working on a unital algebra $\cA$ equipped
with a fixed unital linear functional $\ff$. Usually one calls the
pair $(\cA,\ff)$ a {\it (non-commutative) probability space}.

We consider elements $a_1,\dots,a_l\in\cA$ of our algebra
(called {\it random variables}) and the only information
we use about these random variables is the collection of
all mixed moments, i.e. all quantities
\begin{equation} 
\ff\lb a_{i(1)}\dots a_{i(n)}\rb \qquad\text{for all $n\in\NN$
and all $1\leq i(1),\dots,i(n)\leq l$.}
\end{equation} 

\begin{defs}
The random variables $a_1,\dots,a_l\in\cA$ are called {\it free}
(with respect to $\ff$) if
\begin{equation} 
\ff\lb p_1(a_{i(1)})
p_2(a_{i(2)})\dots p_n(a_{i(n)})\rb=0
\end{equation} 
whenever the $p_j$ ($n\in\NN$, $j=1,\dots,n$) are polynomials
such that
\begin{equation} 
\ff\lb p_j(a_{i(j)})\rb=0\qquad (j=1,\dots,n)\end{equation} 
and
\begin{equation} 
i(1)\not=i(2)\not=\dots\not= i(n).\end{equation} 
\end{defs}
Note that the last condition in the definition requires only that
consecutive indices are different; it might happen,
e.g.,  that $i(1)=i(3)$.

As said before, this definition provides a rule for calculating
mixed moments, but it is far from being explicit. Thus freeness is
difficult to handle in terms of moments. The cumulant philosophy
presented so far can be generalized to this more general 
setting by
trying to 
find some other quantities 
in terms of which freeness is much easier to describe.
I will now show that there are indeed
such (generalized) free cumulants and that the
transition between moments and cumulants is given as before
with the help of non-crossing partitions.

Similarly as our general moments are of the form
\begin{equation} 
\ff\lb a_{i(1)}\dots a_{i(n)}\rb, 
\end{equation} 
our general cumulants $(k_n)_{n\in\NN}$ 
will be $n$-linear functionals $k_n$ with arguments of
the form
\begin{equation} 
k_n(a_{i(1)},\dots,a_{i(n)})\qquad
(n\in\NN, 1\leq i(1),\dots,i(n)\leq l).
\end{equation} 
In the one-dimensional case, as treated up to now, we
had only one random variable $a$ and the previously
considered numbers $k_n$
are related with the above functionals by
$k_n=k_n(a,\dots,a)$.

The rule for calculating the cumulants out of the moments
is the same as before, formally it is given by
$\ff=k\star zeta$.
This means that for calculating a moment 
$\ff\lb a_{i(1)}\dots a_{i(n)}\rb$
in terms of 
cumulants we have to sum over all non-crossing partitions,
each such partition gives a contribution in terms of 
cumulants which is calculated according to the factorization
of that partition into its blocks:
$$\ff\lb a_{i(1)}\dots a_{i(n)}\rb=\sum_{\pi\in NC(n)}
k(\pi)\lb a_{i(1)},\dots,a_{i(n)}\rb;$$
here
$k(\pi)\lb a_{i(1)},\dots,a_{i(n)}\rb$
denotes a product of cumulants where the $a_{i(1)},\dots,a_{i(n)}$
are distributed as arguments to these cumulants according to the 
block structure of $\pi$.

The best way to get the idea is to look at some examples:
\begin{equation} 
\ff\lb a_1\rb=k_1(a_1)
\end{equation} 
\begin{equation} 
\ff\lb a_1a_2\rb=k_2(a_1,a_2)+k_1(a_1)k_1(a_2)
\end{equation} 
\begin{equation} \begin{split}
\ff\lb a_1a_2a_3\rb=&k_3(a_1,a_2,a_3)+k_2(a_1,a_2)k_1(a_3)
\\&+k_2(a_2,a_3)k_1(a_1)+ k_2(a_1,a_3)k_1(a_2)
\\&+k_1(a_1)k_1(a_2)k_1(a_3)
\label{D1}
\end{split} \end{equation} 
\begin{equation}
\begin{split}
\ff\lb a_1a_2a_3a_4\rb=&k_4(a_1,a_2,a_3,a_4)+
k_3(a_1,a_2,a_3)k_1(a_4)\\ &+k_3(a_1,a_2,a_4)k_1(a_3)+
k_3(a_1,a_3,a_4)k_1(a_2)\\ &+k_3(a_2,a_3,a_4)k_1(a_1)+
k_2(a_1,a_2)k_2(a_3,a_4)\\ &+k_2(a_1,a_4)k_2(a_2,a_3)+
k_2(a_1,a_2)k_1(a_3)k_1(a_4)\\ &+k_2(a_1,a_3)k_1(a_2)k_1(a_4)+
k_2(a_1,a_4)k_1(a_2)k_1(a_3)\\&+ k_2(a_2,a_3)k_1(a_1)k_1(a_4)+
k_2(a_2,a_4)k_1(a_1)k_1(a_3)\\ &+k_2(a_3,a_4)k_1(a_1)k_1(a_2)+
k_1(a_1)k_1(a_2)k_1(a_3)k_1(a_4).
\end{split}
\label{D2}
\end{equation}
Note that in the last example the summation is only over the
14 non-crossing partitions, the crossing $\{(1,3),(2,4)\}$ makes
no contribution.

Of course, on can also invert the above expressions in order
to get the cumulants in terms of moments; formally we can
write this as  $k=\ff\star moeb$.

The justification for the introduction of these quantities
comes from the following theorem, which shows that
these free cumulants behave very nicely with respect to
freeness.

\begin{thm}[Speicher \cite{Sp2}, cf.~\cite{N}]
In terms of cumulants, freeness can  
be characterized by the vanishing
of mixed cumulants, i.e. the following two statements are
equivalent:
\newline
i) $a_1,\dots,a_l$ are free
\newline
ii) $k_n(a_{i(1)},\dots,a_{i(n)})=0$ ($n\in\NN$) whenever
there are $1\leq p,q\leq n$ with: $i(p)\not=i(q)$.
\end{thm}

This characterization of freeness is nothing but a translation of
the original definition  in terms of moments to cumulants,
by using the relation $\ff=k\star zeta$.
However, 
it should be clear that this characterization
in terms of cumulants is much
easier to handle than the original definition.

Let me indicate the main step in the proof of the theorem.

\begin{pf}
In terms of moments freeness is characterized by
the vanishing of very special moments, namely 
mixed, alternating
and centered ones.
Because of the relation $\ff=k\star zeta$ it is clear that, by
induction, this should also translate to the vanishing of special
cumulants. However, what we claim is that on
the level of cumulants the assumptions are
much less restrictive, namely the arguments only
have to be mixed. Thus by the transition from moments to
cumulants (via non-crossing partitions) we get somehow rid
of the conditions \lq alternating' and \lq centered'. 
The essential point is centeredness. 
(It is also this condition that is 
not so easy to handle in concrete calculations with moments.)
That we can get rid of this
is essentially equivalent to the fact that
\begin{equation} 
k_n(\dots,1,\dots)=0\qquad\text{for all $n\geq 2$}.
\label{C}
\end{equation} 
That this removes the centeredness condition for cumulants
is clear, since 
with the help of this we can go over from non-centered
to centered arguments without changing the cumulants:
\begin{equation} 
k_n(a_{i(1)},\dots,a_{i(n)})=
k_n\bigl(a_{i(1)}-\ff\lb a_{i(1)}\rb 1,\dots,a_{i(n)}-\ff\lb 
a_{i(n)}\rb 1\bigr).
\end{equation} 
So it only remains to see the validity of (\ref{C}).
But this follows from the fact that the calculation rule
$\ff=k\star zeta$ -- which 
is indeed a system of rules, one for
each $n$ -- is consistent for different $n$'s.
This can again be seen best by an example. Let us see
why $k_4(a_1,a_2,a_3,1)=0$. By induction, we can assume that
we know the vanishing of $k_2$ and $k_3$ if one of their arguments
is equal to 1. 
Now we take formula (\ref{D2}) and put there $a_4=1$. According
to our induction hypothesis some of the terms will vanish and we remain with
\begin{equation} \begin{split}
\ff\lb a_1a_2a_3\rb&=\ff\lb a_1a_2a_3 1\rb\\
&=k_4(a_1,a_2,a_3,1)+
k_3(a_1,a_2,a_3)k_1(1)\\&\quad+k_2(a_1,a_2)k_1(a_3)
k_1(1)+ k_2(a_1,a_3)k_1(a_2)k_1(1)\\
&\quad+k_2(a_2,a_3)k_1(a_1)k_1(1)
+k_1(a_1)k_1(a_2)k_1(a_3)k_1(1).
\end{split} \end{equation} 
Note that we have $k_1(1)=
\ff\lb 1\rb=1$ and thus the right hand
side of the above is, by (\ref{D1}), exactly equal to
\begin{equation} 
k_4(a_1,a_2,a_3,1)+\ff\lb a_1a_2a_3\rb.\end{equation} 
But this implies $k_4(a_1,a_2,a_3,1)=0$.
\end{pf}

\subsection{Additive free convolution}
Having the characterization of freeness by the vanishing of
mixed cumulants, it is now quite easy to give a 
selfcontained combinatorial (i.e. without using
the results of Voiculescu on the $R$-transform) proof of
the linearity of free cumulants under additive free convolution.
Recall that the problem of describing additive free convolution 
consists in calculating, for $X$ and $Y$ being free, the moments
of $X+Y$ in terms of moments of $X$ and moments of $Y$. As a
symbolic notation for this we have introduced the concept of
(additive) free convolution,
\begin{equation} 
\mu_{X+Y}=\mu_X\bplus \mu_Y.\end{equation} 
As described before, this problem can be treated by going over
to the free cumulants according to
\begin{equation} 
m_X=k_X\star zeta\qquad\text{or}\qquad
k_X=m_X\star moeb, \label{E}
\end{equation} 
where $m_X$ and $k_X$ are the multiplicative functions on the
lattice of non-crossing partitions determined by the sequence of
moments $(m_n^X)_{n\geq 1}$ 
of $X$ and the sequence of free cumulants 
$(k_n^X)_{n\geq 1}$ of $X$, respectively.
In the last section I have shown that
the above relation 
(\ref{E}) is essentially equivalent to Voiculescu's
formula for the calculation of the $R$-transform.
So it only remains to recognize the additivity of the free cumulants
(and thus of the $R$-transform) under free convolution.
But since the one-dimensional cumulants of the last section
are just special cases of the above defined more general cumulants
according to
\begin{equation} 
k_n^X=k_n(X,\dots,X),\end{equation} 
this additivity is a simple corollary of the vanishing of mixed
cumulants in free variables:
\begin{equation} \begin{split}
k_n^{X+Y}&=k_n(X+Y,\dots,X+Y)\\
&=k_n(X,\dots,X)+k_n(Y,\dots,Y)\\
&=k_n^X+k_n^Y.
\end{split} \end{equation}  

Thus we have recovered, by our combinatorial approach, the full
content of Voiculescu's results on additive free convolution.

\section{{\bf Multiplicative free convolution and 
the general structure of the combinatorial
convolution on $NC$}}

\subsection{Multiplicative free convolution}
Voiculescu considered also the problem of the product of free
random variables: if $X$ and $Y$ are free, how can we 
calculate moments of $XY$ out of moments of $X$ and moments
of $Y$?

Note that in the classical case we can make a transition from
the additive to the multiplicative problem just by
exponentiating; thus
in this case the multiplicative problem reduces to the
additive one, there is no need to investigate something like
multiplicative classical convolution as a new operation.

In the free case, however, this reduction does not work,
because for non-commuting random variables we have
in general
\begin{equation} 
\exp(X+Y)\not= \exp X\cdot \exp Y.
\end{equation} 
Hence it is by no means clear whether the multiplicative
problem is somehow related to the additive problem.

We know that freeness results in some rule for calculating
the moments of $XY$ out of the moments of $X$ and the
moments of $Y$, thus the distribution of $XY$ depends
somehow on the distribution of $X$ and the distribution
of $Y$. As in the additive case, Voiculescu 
\cite{V3} introduced a
special symbol, $\btimes$, for this \lq somehow' and named the 
corresponding operation on probability measures
{\it multiplicative free convolution}:
\begin{equation} 
\mu_{XY}=\mu_X\btimes\mu_Y.\end{equation} 
And, more importantly, he could solve the problem of
describing this operation in analytic terms. In the same way
as the additive problem was dealt with by introducing the
$R$-transform, he defined now a new formal power series,
called $S$-transform, which behaves nicely with respect
to multiplicative convolution, 
\begin{equation} 
S_{\mu\btimes\nu}(z)=S_\mu(z)\cdot S_\nu(z).
\label{K}
\end{equation} 
Again he was able 
(by quite involved arguments)
to derive a formula for the calculation
of this $S_\mu$-transform out of the distribution $\mu$:
\begin{equation} 
S_\mu(z):=\frac {1+z}z \bigl(\sum_{n=1}^\infty \ff(X^n)z^n
\bigr)^{<-1>},
\end{equation} 
where $<-1>$ denotes the operation of taking the inverse with
respect to composition of formal power series.

Voiculescu dealt with two problems in connection
with freeness, the additive 
convolution $\bplus$ and the multiplicative convolution $\btimes$,
and he could solve both of them by introducing the
$R$-transform and the $S$-transform, respectively. 
I want to emphasize that in his
treatment there is no connection between both problems,
he solved them independently.

One of the big advantages of our combinatorial approach is
that we shall see a connection between
both problems.
Up to now, I have described how we can understand the 
$R$-transform combinatorially in terms of cumulants -- the
latter were just the coefficients in the $R$-transform.
My next aim is to show that also the multiplicative
convolution (and the $S$-transform) 
can be described very nicely in combinatorial terms
with the help of the free cumulants.

But before I come to this, let me again switch to the
purely combinatorial side by recognizing that there is also
still some canonical problem open.

\subsection{General structure of the combinatorial convolution
on $NC$}
Recall that, in Sect.~5, we have introduced a
combinatorial convolution on the incidence algebra of non-crossing
partitions. We are particulary interested in multiplicative
functions on non-crossing partitions and it is quite easy to
check that the combinatorial convolution of multiplicative
functions is again multiplicative.
This means that for two multiplicative functions $f$
and $g$, given by
their corresponding sequences,
\begin{equation}
f\reli (a_1,a_2,\dots),\qquad g\reli (b_1,b_2,\dots),\end{equation} 
their convolution
\begin{equation}
h:=f\star g\end{equation} 
must, as a multiplicative function, also be determined by some
sequence of numbers
\begin{equation} 
h\reli (c_1,c_2,\dots).\end{equation} 
These $c_i$ are some functions of the $a_i$ and $b_i$ and
it is an obvious question to ask for the concrete form of this
connection. The answer, however, is not so obvious.

Note that in Sect.~5 we dealt with a special case of
this problem, namely the case where $g=zeta$. This was
exactly what was needed for describing additive free
convolution in the form $m=k\star zeta$, and the relation between
the two series $f$ and $h=f\star zeta$ is more or less Voiculescu's
formula for the $R$-transform:
If 
\begin{equation}
f\reli (a_1,a_2,\dots)
\qquad\text{and}\qquad
h=f\star zeta\reli (c_1,c_2,\dots)
\end{equation} 
then in terms of the generating power series
\begin{equation} 
C(z):=1+\sum_{n=1}^\infty c_nz^n \qquad\text{and}\qquad
D(z):=1+\sum_{n=1}^\infty a_nz^n
\end{equation} 
the relation is given by
\begin{equation} 
C(z)=D\lb zC(z)\rb.\end{equation} 

Now we ask for an analogue treatment of the general case
$h=f\star g$.
The corresponding problem for all partitions was
solved by Doubilet, Rota, and Stanley in \cite{DRS}:
The multiplicative functions on $\cP$ correspond to 
exponential power series of their determining sequences and
under this correspondence the convolution $\star$ goes over
to composition of power series. 

What is the corresponding result for non-crossing partitions?
The answer to this is more involved than in the case of all
partitions, but it will turn out that this is also intimately 
connected with the problem of multiplicative free
convolution and the $S$-transform. In the case of all partitions
there is no connection between the above mentioned result
of Doubilet, Rota, and Stanley and some classical probabilistic
convolution.

The answer for the case of non-crossing partitions depends
on a special property of $NC$ 
(which has no analogue in $\cP$): all $NC(n)$ are self-dual
and there exists a nice mapping, the
{\it (Kreweras) complementation map}
\begin{equation} 
K:NC(n)\to NC(n),\end{equation} 
which implements this self-duality.
This complementation map is a lattice anti-isomorhism, i.e.
\begin{equation} 
\pi\leq \sigma\Leftrightarrow K(\pi)\geq K(\sigma),
\end{equation} 
and it is defined as follows:
If we have a partition $\pi\in NC(n)$ then we insert between
the points $1,2,\dots,n$ new points $\bar 1,\bar 2,\dots,\bar n$
(linearly or circularly), such that we have
$1,\bar 1,2,\bar 2,\dots,n,\bar n$. We draw now the partition
$\pi$ by connecting the blocks of $\pi$ and we define $K(\pi)$
as the biggest non-crossing partition of $\{\bar 1,\bar 2,\dots,
\bar n\}$ which does not have crossings with the partition 
$\pi$: $K(\pi)$ is the maximal element of the set
$\{\sigma\in NC(\bar 1,\dots,\bar n)\mid \pi\cup\sigma
\in NC(1,\bar 1,\dots,n,\bar n)\}$.
(The union of two partitions on different sets is of course just
given by the union of all blocks.)

This complementation map was introduced by Kreweras
\cite{K}. Note that $K^2$ is not equal to the identity
but it shifts the points by one (mod $n$) (corresponding to
a rotation in the circular picture). Simion and Ullman
\cite{SU} modified the 
complementation map to make it involutive, but the 
original map of Kreweras is more adequate for our
investigations. Biane \cite{Bia1} showed that 
the complementation map of Kreweras and the
modification of Simion and Ullman generate together the group 
of all skew-automorphisms (i.e., automorphisms or
anti-automorphisms) of $NC(n)$, which is the dihedral group
with $4n$ elements.

As an example for $K$ we have:
\begin{equation} 
K(\{(1,4,8),(2,3),(5,6),(7)\})=\{(1,3),(2),(4,6,7),(5),(8)\}.
\end{equation} 
\setlength{\unitlength}{0.5cm}
\begin{picture}(16,5)
\thicklines
\put(1,0){\line(0,1){4}}
\put(1,0){\line(1,0){14}}
\put(7,0){\line(0,1){4}}
\put(15,0){\line(0,1){4}}
\put(3,2){\line(0,1){2}}
\put(3,2){\line(1,0){2}}
\put(5,2){\line(0,1){2}}
\put(9,2){\line(0,1){2}}
\put(9,2){\line(1,0){2}}
\put(11,2){\line(0,1){2}}
\put(13,2){\line(0,1){2}}
\linethickness{0.6mm}
\put(2,1){\line(0,1){3}}
\put(2,1){\line(1,0){4}}
\put(6,1){\line(0,1){3}}
\put(4,3){\line(0,1){1}}
\put(8,1){\line(0,1){3}}
\put(8,1){\line(1,0){6}}
\put(12,1){\line(0,1){3}}
\put(14,1){\line(0,1){3}}
\put(10,3){\line(0,1){1}}
\put(16,1){\line(0,1){3}}
\put(0.8,4.5){1}
\put(1.8,4.5){$\bar 1$}
\put(2.8,4.5){2}
\put(3.8,4.5){$\bar 2$}
\put(4.8,4.5){3}
\put(5.8,4.5){$\bar 3$}
\put(6.8,4.5){4}
\put(7.8,4.5){$\bar 4$}
\put(8.8,4.5){5}
\put(9.8,4.5){$\bar 5$}
\put(10.8,4.5){6}
\put(11.8,4.5){$\bar 6$}
\put(12.8,4.5){7}
\put(13.8,4.5){$\bar 7$}
\put(14.8,4.5){8}
\put(15.8,4.5){$\bar 8$}
\end{picture}

\vskip1cm

With the help of this complementation map $K$ we can rewrite
our combinatorial convolution in the following way:
If we have multiplicative functions connected by
$h=f\star g$, and the sequence determining $h$ is denoted
by $(c_1,c_2,\dots)$, then we have by definition of our
convolution
\begin{equation} 
c_n=h(0_n,1_n)=\sum_{\pi\in NC(n)} f(0_n,\pi)g(\pi,1_n),
\end{equation} 
which looks quite unsymmetric in $f$ and $g$. But the
complementation map allows us to replace
\begin{equation} 
\lb \pi,1_n\rb\cong \lb K(1_n),K(\pi)\rb=\lb 0_n,K(\pi)\rb
\end{equation} 
and thus we obtain
\begin{equation} 
c_n=\sum_{\pi\in NC(n)} f(0_n,\pi)g(0_n,K(\pi))=
\sum_{\pi\in NC(n)} f(\pi) g(K(\pi)). \label{V}
\end{equation} 

An immediate corollary of that observation is the 
commutativity of the combinatorial convolution on non-crossing
partitions.

\begin{cor}[Nica+Speicher \cite{NS1}]
The combinatorial convolution $\star$ on non-crossing
partitions is commutative:
\begin{equation} 
f\star g=g\star f.\end{equation} 
\end{cor}

\begin{pf}
\begin{equation}
\begin{split}
(f\star g)(0_n,1_n)&=\sum_{\pi\in NC(n)} f(\pi)g(K(\pi))\\
&=\sum_{\sigma=K^{-1}(\pi)}f(K(\sigma))g(\sigma)\\
&=(g\star f)( 0_n,1_n).
\end{split}
\end{equation}
\end{pf}

The corresponding statement for the 
convolution on all partitions is not true -- this is 
obvious from the
fact that under the above stated correspondence with exponential
power series this convolution goes over to composition, which is
clearly not commutative.
This indicates that the description of the combinatorial convolution
on non-crossing partitions should differ substantially from the
result for all partitions. Of course, this corresponds to the
fact that the lattice of all partitions is not self-dual, there
exist no analogue of the complementation map for arbitrary
partitions.

\subsection{Connection between $\star$ and $\btimes$}
Before I am going on to present the solution to the problem of
describing the full structure of the combinatorial convolution
$\star$, I want to establish the connection between this
combinatorial problem and the problem of the multiplicative
free convolution.

Let $X$ and $Y$ be free. Then multiplicative free convolution
asks for the moments of $XY$.
In terms of cumulants we can write them as
\begin{equation} 
\ff\lb(XY)^n\rb=\sum_{\pi\in NC(2n)}
k(\pi)\lb X,Y,X,Y,\dots ,X,Y\rb,
\end{equation} 
where $k(\pi)\lb X,Y,X,Y,\dots ,X,Y\rb$ 
denotes a product of cumulants which
factorizes according to the block structure of the 
partition $\pi$. The vanishing of mixed cumulants
in free variables implies that only such partitions $\pi$
contribute where all blocks connect either only $X$ or only $Y$.
Such a $\pi\in NC(2n)$ splits into the union $\pi=
\pi_1\cup \pi_2$, where $\pi_1\in NC(1,3,5,\dots)$ 
(the positions of the $X$) and
$\pi_2\in NC(2,4,6,\dots)$ (the positions of the $Y$),
and we can continue the above equation with
\begin{equation} \begin{split}
&\ff\lb(XY)^n\rb=\\ &=
\sum\Sb \pi=\pi_1\cup \pi_2\in NC(2n)\\
\pi_1\in NC(1,3,5,\dots)\\
\pi_2\in NC(2,4,6,\dots)\endSb
k(\pi_1)\lb X,X,\dots ,X\rb \cdot k(\pi_2)\lb Y,Y,\dots ,Y\rb\\
&=\sum_{\pi_1\in NC(n)}\Bigl( k(\pi_1)\lb X,X,\dots ,X\rb\cdot
\sum\Sb \pi_2\in NC(n)\\ \pi_1\cup \pi_2\in NC(2n)\endSb k(\pi_2)
\lb Y,Y,\dots ,Y\rb\Bigr).
\end{split} \end{equation}
Now note that the condition 
\begin{equation} 
\pi_2\in NC(n)\qquad\text{with}\qquad \pi_1\cup \pi_2\in NC(2n)
\end{equation} 
is equivalent to
\begin{equation} 
\pi_2\leq K(\pi_1)\end{equation} 
and that with $k_Y$ and $m_Y$ being the multiplicative functions
determined by the cumulants and the moments of $Y$, respectively,
the relation $m_Y=k_Y\star zeta$ just means explicitely
\begin{equation} 
m_Y(\sigma_1)=\sum_{\sigma_2\leq\sigma_1}k_Y(\sigma_2).
\end{equation} 
Taking this into account we can continue our calculation of the
moments of $XY$ as follows:
\begin{equation} \begin{split}
\ff\lb(XY)^n\rb&=\sum_{\pi_1\in NC(n)}
\Bigl( k_X(\pi_1)
\cdot\sum_{\pi_2\leq K(\pi_1)} k_Y(\pi_2)\Bigr)\\
&=\sum_{\pi_1\in NC(n)}k_X(\pi_1)\cdot m_Y(K(\pi_1)).
\end{split} \end{equation}
According to our 
formulation of the combinatorial convolution
in terms of the complementation map,
cf.~(\ref{V}), this is nothing but the
following relation
\begin{equation} 
m_{XY}=k_X\star m_Y. \label{F}
\end{equation} 
Hence we can express multiplicative free
convolution $\btimes$ in terms of the
combinatorial convolution $\star$. This becomes even more striking
if we remove the above unsymmetry in moments and cumulants.
By applying the M\"obius function on (\ref{F}) we end up with
\begin{equation} 
k_{XY}=m_{XY}\star moeb=k_X\star m_Y\star moeb=k_X\star k_Y,
\end{equation} 
and we have the beautiful result
\begin{equation} 
k_{XY}=k_X\star k_Y\qquad\text{for $X$ and $Y$ free.}
\end{equation} 
One sees that we can describe also multiplicative free convolution
in terms of cumulants, just by taking the combinatorial convolution
of the corresponding cumulant functions. Thus the problem
of describing multiplicative free convolution $\btimes$ is
equivalent to understanding the general structure of the
combinatorial convolution $h=f\star g$.

\subsection{Description of $\star$}
The above connection means
in particular that Voiculescu's description
of the multiplicative free convolution,
via the $S$-transform, must also contain
(although not in an explicit form) the solution for the 
description of $h=f\star g$.

This insight was the starting point of my joint work 
\cite{NS1} with
A. Nica on the combinatorial convolution $\star$. From
Voiculescu's result on the $S$-transform and the above
connection
we got an idea how the solution should look like and then
we tried to derive this by purely combinatorial means.

\begin{thm}[Nica+Speicher \cite{NS1}]
For a multiplicative function $f$ on NC with
\begin{equation} 
f\reli (a_1,a_2,\dots)\qquad\text{where}\qquad a_1=1
\end{equation} 
we define its \lq Fourier transform' $\cF(f)$ by
\begin{equation} 
\cF(f)(z):=\frac 1z\bigl(\sum_{n=1}^\infty a_nz^n\bigr)^{<-1>}.
\end{equation} 
Then we have
\begin{equation} 
\cF(f\star g)(z)=\cF(f)(z)\cdot \cF(g)(z).\end{equation} 
\end{thm}

Hence multiplicative functions on $NC$ correspond to formal
power series (but now this correspondence $\cF$ is not as direct as in 
the case of all partitions), and under this correspondence the
combinatorial convolution $\star$ is mapped onto multiplication of
power series. This is of course consistent with the commutativity
of $\star$.

This result is not obvious on the first look, 
but its proof does not require more than some clever
manipulations with non-crossing partitions.
Let me present you the main steps of the proof.

\begin{pf}
Let us denote for a multiplicative function $f$ determined
by a sequence $(a_1,a_2,\dots)$ its generating power series by
\begin{equation} 
\Phi_f(z):=\sum_{n=1}^\infty a_nz^n.\end{equation} 
Then we do the summation in
\begin{equation} 
c_n=\sum_{\pi\in NC(n)} f(\pi)g(K(\pi))\end{equation} 
in such a way that we fix the first block of $\pi$ and then
sum over the remaining possibilities. A careful look
reveals that this results in a relation
\begin{equation} 
\Phi_{f\star g}=\Phi_f\circ \Phi_{f \check\star g},
\label{G}
\end{equation} 
where $f\check\star g$ is defined by
\begin{equation} 
(f\check\star g)(0_n,1_n):=\sum_{\pi\in NC'(n)} f(\pi)g(K(\pi));
\end{equation} 
the summation does not run over all of $NC(n)$ but only
over
\begin{equation} 
NC'(n):=\{\pi\in NC(n)\mid \text{$(1)$ is a block of $\pi$}\}.
\end{equation} 
This relation comes from the fact that if we fix the first block of 
$\pi$, then the remaining blocks are all separated from each other,
but each one of them has to be considered in connection with one
point of the first block.

The relation 
(\ref{G}) alone does not help very much, since it 
involves also the new
quantitiy $f\chstar g$.
In order to proceed further 
we need one more relation. 
This is given by the following symmetrization lemma
(in contrast to $\star$ the operation $\chstar$ is not commutative)
\begin{equation} 
z\cdot \Phi_{f\star g}(z)=\Phi_{f\chstar g}(z)\cdot
\Phi_{g\check\star f}(z), \label{H}
\end{equation} 
which just encodes a nice bijection between
\begin{equation} 
NC(n) \qquad\longleftrightarrow \qquad
\bigcup_{1\leq j\leq n} NC'(j)\times NC'(n+1-j).
\end{equation} 
The two relations 
(\ref{G}) and (\ref{H}) are all we need, the rest is just
playing around with formal power series: (\ref{G}) implies
\begin{align}
\Phi^{<-1>}_f&=\Phi_{f\chstar g}\circ \Phi^{<-1>}_{f\star g}
\label{I}\\
\Phi^{<-1>}_g&=\Phi_{g\chstar f}\circ \Phi^{<-1>}_{g\star f},
\label{J}
\end{align}
where in the last expression we can replace $g\star f$ by
$f\star g$.
Putting now $z=\Phi_{f\star g}^{<-1>}(w)$ in 
(\ref{H}) we obtain
\begin{equation} 
\Phi^{<-1>}_{f\star g}(w)\cdot w=
\Phi_{f\chstar g}\bigl(\Phi^{<-1>}_{f\star g}(w)\bigr)\cdot
\Phi_{g\chstar f}\bigl(\Phi^{<-1>}_{f\star g}(w)\bigr).
\end{equation} 
If we replace the quantities on the right hand side according to
(\ref{I}), (\ref{J}) and divide by $w^2$ we end up with
\begin{equation} 
\frac{\Phi^{<-1>}_{f\star g}(w)}w=
\frac{\Phi^{<-1>}_{f}(w)}w \cdot\frac{\Phi^{<-1>}_{g}(w)}w.
\end{equation} 
Since, by definition, the Fourier transform is nothing but
\begin{equation} 
\cF(f)(w)=\frac{\Phi^{<-1>}_{f}(w)}w,
\end{equation} 
this yields exactly the assertion.
\end{pf}
Biane \cite{Bia2} related the above theorem to the concept
of central multiplicative functions on the infinite symmetric
group and gave another proof of the theorem in that context.

\subsection{Connection between $S$-transform and Fourier transform}
According to Sect.~7.3, the problem of the general structure of
the combinatorial convolution is 
essentially the same as the problem of
multiplicative free convolution. So the above theorem should also
be connected with the crucial property 
(\ref{K}) of the $S$-transform.
Let me point out this connection and show that everything
fits together nicely.

If we denote by $k(\mu)$ the cumulant function of the
distribution $\mu$ (i.e. the multiplicative function on non-crossing
partitions determined by the free cumulants of $\mu$), then I have
shown, in Sect.~7.3, that the connection between probability and
combinatorics is given by
\begin{equation} 
k(\mu\btimes \nu)=k(\mu)\star k(\nu). \label{P}
\end{equation} 
If one compares the definition of the $S$-transform and of the
Fourier transform $\cF$ and takes into account the relation
which exists between moments and cumulants then one sees
that the definitions are made in such a way that we have
the relation
\begin{equation} 
S_\mu=\cF(k(\mu)). \label{Q}
\end{equation} 
It is then clear that our theorem on the description of $\star$
via the Fourier transform together with the two equations 
(\ref{P})
and (\ref{Q}) yields 
directly the behaviour of the $S$-transform under
multiplicative free convolution:
\begin{equation} \begin{split}
S_{\mu\btimes\nu}&=\cF\bigl(k(\mu\btimes\nu)\bigr)\\
&=\cF\bigl(k(\mu)\star k(\nu)\bigr)\\
&=\cF(k(\mu))\cdot\cF(k(\nu))\\
&=S_\mu\cdot S_\nu.
\end{split} \end{equation}
Thus we get a purely combinatorial proof of Voiculescu's
theorem on the $S$-transform. Furthermore, our approach
reveals a much closer relationship between additive and
multiplicative free convolution than one would expect
at a first look.

Let me close this section by emphasizing 
again that these considerations
on the multiplicative free convolution 
possess no classical counterpart;
combinatorially all this relies on the existence of the
Kreweras complementation map for non-crossing partitions --
some extra structure which is absent in the case of all partitions.
Freeness and non-crossing partitions behave in many respects
analogous to independence and all partitions, respectively, but
in the free case there exists also some extra structure which
makes this theory even richer than the classical one.

\section{{\bf Applications of the combinatorial description of
freeness}}
Up to now I have essentially shown how one can use freeness as
a motivation for developing a lot of nice mathematics on
non-crossing partitions. Note that the combinatorial problems
are canonical for themselves -- I hope you find them interesting
even without taking into account the connection with free probability.

But of course this relation between freeness and non-crossing
partitions can also be reversed; we can use the combinatorial
description of freeness to derive some new results in free
probability theory (up to now I have only shown how to rederive
some known results of Voiculescu). This programme was pursued
in a couple of joint papers with A. Nica \cite{NS2,NS3,NS4}.
For illustration, I want to present some of these results.

\subsection{Construction of free random variables}
One class of results are those were one starts with some variables
that are free and constructs out of them new variables; then one
asks whether one can say something about
the freeness of the new variables.
It is quite astonishing that there are a lot of constructions which
preserve freeness -- usually constructions which have no
classical counterpart. In a sense freeness is much more rigid
than classical independence  --
on a combinatorial level this corresponds to the
fact that there exist a lot of special bijections 
between
non-crossing partitions.

Let me just state one theorem of that type.
It involves a so-called {\it semi-circular}
distribution; this is the free analogue of the classical Gauss
distribution and a semi-circular variable can be characterized
by the fact that only its second free cumulant is different from 
zero. 

\begin{thm}[Nica+Speicher \cite{NS2}]  
Let $a$ and $b$ be random variables which are free. If $b$
is semi-circular, then $a$ and $bab$ are also free.
\end{thm}

The proof of this theorem relies mainly on the fact that
there exists a canonical bijection between $NC(n)$ and the
set 
\begin{multline} 
NCP(2n):=\{\pi\in NC(2n)\mid\text{each block of $\pi$
contains} \\ \text{exactly two elements}\}.
\end{multline} 

\subsection{Unexpected results}
Surprises are to be expected from investigations which involve
the Kreweras complementation map -- since there is
no classical analogy it might happen that one can derive 
properties which are totally opposite to what one knows
from the classical case.
One striking example of that kind is the following theorem, whose
proof can be finally traced back to the property
\begin{equation} 
\vert\pi\vert+\vert K(\pi)\vert=n+1\qquad\text{for all
$\pi\in NC(n)$.}
\end{equation} 

\begin{thm}[Nica+Speicher \cite{NS2}]
Let $\mu$ be a (compactly supported) probability measure
on $\RR$. Then there exists, for each $\alpha\geq 1$, a
probability measure $\mu^{\bplus \alpha}$ such that
\begin{equation} 
\mu^{\bplus 1}=\mu\end{equation} 
and 
\begin{equation} 
\mu^{\bplus\alpha}\bplus\mu^{\bplus\beta}=
\mu^{\bplus(\alpha+\beta)}\qquad\text{for all $\alpha,\beta\geq
1$.}
\end{equation} 
\end{thm}

Note that here positivity is the main assertion, it is crucial that
we require the fractional powers to be {\it probability measures}.
The corresponding statement on the level of linear functionals
would be trivially true for arbitrary $\alpha$.

To get an idea of the assertion consider the following example:
If $\mu$ is a probability measure then we claim that there
exists another probability measure $\nu=\mu^{\bplus 3/2}$
such that
\begin{equation} 
\nu\bplus\nu=\mu\bplus\mu\bplus\mu.
\end{equation} 

The analogous statement for classical convolution is of
course totally wrong, as one can see, e.g.,  from the above example
by taking $\mu$ to be the symmetric 
Bernoulli distribution with mass on
$+1$ and $-1$.

\subsection{Free commutator}
An important advantage of our combinatorial description over
the original analytical approach of Voiculescu is the
possibility to extend the combinatorial treatment without any
extra
effort from the one-dimensional to the more-dimensional case.
This opens  the possibility to attack problems which are not
treatable from the analytic side. The most considerable result
of that kind is our analysis of the free commutator in
\cite{NS4}.
Voiculescu solved the problem of the sum $X+Y$ 
and the product $XY$ 
of two free random variables $X$ and $Y$. The next canonical
problem, the free commutator $XY-YX$, could be treated,
for the first time, by
our combinatorial machinery --  the description of the
commutator relies heavily on an understanding of the
two-dimensional distribution of the pair ($XY,YX$).

\subsection{Generalization to the case with amalgamation}
I want to indicate that one can generalize free probability
theory also to an operator-valued frame; linear functionals
are replaced by conditional expectations onto some fixed algebra
$\cB$ and all appearing algebras are with amalgamation
over this $\cB$. Again, the combinatorial point of view using
non-crossing partitions gives a natural and beautiful description
for this theory. This approach was developed in \cite{Sp3}.

\section{{\bf Relations between freeness and other fields}}

Up to now I have concentrated on presenting the connection
between free probability theory and non-crossing partitions.
In a sense, freeness can be regarded as an abstract concept
which is more or less equivalent to the combinatorics of
non-crossing partitions. The most exciting feature of freeness,
however, is that this is only one facet, there exist much more
connections to various fields. Freeness is an abstract concept
with a lot of concrete manifestations in quite different contextes.
In the following I want to give a slight idea of some of these
connections. Whereas my presentation of the combinatorial part
has covered most of the essential aspects, the following remarks
will be very brief and selective. 
(In particular, I will say nothing about \lq free
entropy' -- at present one of the most
exciting directions in free probability theory .)
For 
a more exhaustive survey I suggest to consult \cite{VDN,V5,V6}.
In particular, \cite{V6} contains a collection of articles
on quite different aspects of freeness.

\subsection{Origin of freeness: the free group factors}
Voiculescu introduced \lq freeness' in a context 
which is quite different from the topics I have treated up to
now: namely in the theory of operator algebras, 
in connection with some old problems on special von 
Neumann algebras.

Let me give a very brief idea of that context. To a discrete
group $G$ one can associate in a canoncial way a von Neumann
algebra $L(G)$, which is the closure in some topology of
the group ring of $G$: On the Hilbert space
\begin{equation}
l_2(G):=\{\sum_{g\in G} \alpha_g g\mid \sum_g\vert \alpha_g
\vert^2<\infty\}
\end{equation}
with the scalar product
\begin{equation}
\langle g_1,g_2\rangle:=\delta_{g_1,g_2}
\end{equation}
one has a natural unitary representation $\lambda$ of the 
group $G$, which is given by left multiplication, i.e.
\begin{equation}
\lambda(g)h=gh.
\end{equation}
The von Neumann algebra $L(G)$ associated to $G$ is by
definition the closure in the weak topology of the 
group ring $\CC(G)$ in this representation:
\begin{equation}
L(G):=\overline{\lambda(\CC(G))}^{weak}=
vN(\lambda(g)\mid g\in G)\subset B(l_2(G)).
\end{equation}

If the considered group is i.c.c. (i.e. all its non-trivial conjugacy
classes contain infinitely many elements) then the von Neumann
algebra $L(G)$ is a so-called factor; factors are in a sense the
simplest building blocks of general von Neumann algebras.
Furthermore, there exists a canonical trace on $L(G)$, which
is given by the identity element $e$ of $G$: define
\begin{equation}
\ff(\cdot):=\langle e,\cdot e\rangle,\qquad\text{i.e.}\qquad
\ff(\sum_g \alpha_g g)=\alpha_e,
\end{equation}
then it is easy to check that $\ff$ is a trace, i.e. it 
fulfills
\begin{equation}
\ff(ab)=\ff(ba)\qquad\text{for all $a,b\in L(G)$.}
\end{equation}
Factors having such a trace are called $II_1$-factors --
they are the simplest class of non-trivial von Neumann algebras.
(Trivial are the von Neumann algebras $B(\HH)$ for some
Hilbert space $\HH$; and there exist also type III factors,
which possess no trace and which are much harder to analyze.)

Almost all known constructions of von Neumann algebras 
rely on the above construction of group factors and
one has to face the following canonical question:
What is the structure of $L(G)$ for different $G$,
in particular,
how much of the structure of $G$ survives within
$L(G)$.

For some classes of groups this is quite well understood.
If the group $G$ is amenable, then one gets always the same
factor, the so-called hyperfinite factor $R$,
\begin{equation}
L(G)=R\qquad\text{for all amenable groups $G$.}
\end{equation}
This hyperfinite $II_1$-factor (and its type $III$ counterparts)
has a lot of nice properties and the class of hyperfinite
factors is regarded as the nicest class of von Neumann algebras.

On the other extreme there is a treatable class of groups which are
considered as the bad guys: if $G$ has the so-called Kazhdan
property then $L(G)$ has some exotic properties (usually
used for constructing counter-examples);
but for this class there is some evidence (i.e. it is an open
conjecture) that the von Neumann algebra contains the full
information on the group, i.e.
\begin{equation}
L(G_1)\cong L(G_2)\Longleftrightarrow G_1\cong G_2
\qquad\text{$G_1,G_2$ Kazhdan groups}.
\end{equation}
There is a canonical class of groups  lying between amenable
and Kazhdan groups: the free groups $F_n$ on $n$ generators.
Voiculescu advocates the philosophy that
the free group factors $L(F_n)$ are the nicest class of von
Neumann algebras after the hyperfinite case.
However, since the early days of Murray-von Neumann
there has been no progress on this class -- only the most
basic things are know, like that they are different from the
hyperfinite factor. But even the most canonical question,
namely whether $L(F_n)$ is isomorphic to $L(F_m)$ for
$n\not=m$, is still open.

Voiculescu introduced the notion of \lq freeness' exactly
in order to investigate the structure of the free group factors.
His idea was the following:
The free group $F_n$ is the free product (of groups)
\begin{equation}
F_n=\ZZ*\dots*\ZZ,
\end{equation}
thus one might expect that the corresponding free
group factor can also be decomposed as a free product
(of von Neumann algebras) like
\begin{equation}
L(F_n)=L(\ZZ)*\dots* L(\ZZ).
\end{equation}
$L(\ZZ)$ are commutative von Neumann algebras, thus 
well-understood; the main problem consists in understanding
the operation of taking the free product
of von Neumann algebras. 
But this amounts to understanding freeness:
It is easy to see that
with respect to the canonical trace in $L(F_n)$ the
different copies of $L(\ZZ)$ are free in $L(F_n)$.
The first main
step of Voiculescu was to separate freeness as an abstract
concept from that concrete problem and to develop it as
a theory on its own sake. The second main point was 
to consider 
freeness as a non-commutative analogue of independence  
and thus to develop a free probability theory.

One should emphasize that for a couple of years there
was no real progress on the problem of free group factors,
it was absolutey unclear whether this approach via free
probability theory would in the end yield something for
the original operator algebraic problem. But slowly
connections between freeness and other fields emerged
and these really had a big impact on the 
operator algebraic side: Although the problem of the
isomorhpism of the free group factors is still open, there has
been a lot of progress on the structure of these algebras. Let
me just mention as one result in this direction the following
(according to Dykema \cite{Dyk} and Radulescu \cite{Rad},
building on results of Voiculescu): Either all $L(F_n)$ are
isomorhpic or all of them are different. (One can even 
extend the definition of $L(F_n)$ in a consistent way
to non-integer $n$.)

This progress on the original problem relied essentially
on the discovery of Voiculescu 
\cite{V4} that freeness has
also a canonical realization in terms of random matrices.

\subsection{Freeness and random matrices}
Probably the most important link of freeness with another,
apriori totally unrelated, context is the connection with random
matrices. Let me just state the basic version of this theorem
\begin{thm}[Voiculescu \cite{V4}, cf.~\cite{Sp4}]
1) Let 
\begin{equation}
X^{(N)}=(a_{ij}^{(N)})_{i,j=1}^N\qquad\text{and}\qquad
Y^{(N)}=(b_{ij}^{(N)})_{i,j=1}^N
\end{equation}
be symmetric $N\times N$-random matrices with
\newline
i) 
$a_{ij}^{(N)}$ ($1\leq i\leq j\leq N$) are independent and
normally distributed (mean zero, variance $1/N$)
\newline
ii)
$b_{ij}^{(N)}$ ($1\leq i\leq j\leq N$) are independent and
normally distributed (mean zero, variance $1/N$)
\newline
iii) all $a_{ij}^{(N)}$ are independent from all 
$b_{kl}^{(N)}$
\newline
Then $X^{(N)}$ and $Y^{(N)}$ become free in the limit 
$N\to\infty$ with respect to
\begin{equation}
\ff(\cdot):=\frac 1N\langle \tr(\cdot)\rangle_{ensemble}.
\end{equation}
2) Let $A^{(N)}$ and $B^{(N)}$
be symmetric deterministic (e.g. diagonal) $N\times N$-matrices 
whose eigenvalue distribtutions tend to some fixed
probability measures $\mu$ and $\nu$, respectively, in
the limit $N\to\infty$.
Consider now
\begin{equation}
X^{(N)}:=A^{(N)}\qquad\text{and}\qquad
Y^{(N)}:=UB^{(N)}U^*,
\end{equation}
where $U$ is a random unitary $N\times N$-matrix from
the ensemble
\begin{equation}
U\in\Omega_N=(U(N), \,Haar\, measure).
\end{equation}
Then $X^{(N)}$ and $Y^{(N)}$ become free 
in the limit $N\to\infty$
with respect to
\begin{equation}
\ff(\cdot):=\frac 1N \langle \tr(\cdot)\rangle_{\Omega_N}.
\end{equation}
\end{thm}

Note that part 2 of this theorem is much more general than part 1.
In the first part, $X^{(N)}$ and $Y^{(N)}$ are Gaussian 
random matrices and thus, by a celebrated result of 
Wigner, their eigenvalue distributions tend, for $N\to\infty$, 
towards the so-called semi-circle distribution.
We can also say that (in the sense of convergence of all
moments)
\begin{equation}
\lim_{N\to\infty} (X^{(N)},Y^{(N)})=(X,Y),
\end{equation}
where $X$ and $Y$ are free and both 
have a semi-circular distribution
(cf. Sect.~8.1).

In part 2 of the theorem, however, we are not restricted to
semi-circular distributions, but we can prescribe in the limit any
distribution we want. In this case we can
rephrase the statement in the form
\begin{equation}
\lim_{N\to\infty} (X^{(N)},Y^{(N)})=(X,Y),
\end{equation}
where $X$ and $Y$ are free and have the prescribed
distributions
\begin{equation}
\mu_X=\mu\qquad\text{and}\qquad \mu_Y=\nu.
\end{equation}

As a conclusion one can say that \lq freeness' can
also be considered as the mathematical structure of 
$N\times N$-random matrices which survives in the 
limit $N\to\infty$, or that \lq freeness' is the right concept for
the description of $\infty\times\infty$-random matrices.

As mentioned before, this connection resulted in some deep
results on the von Neumann algebras of the free groups.
But it opens also the possibility for using the concept
\lq freeness' in physical applications. Random matrices
are quite frequently introduced in physics, usually in connection
with some approximations. In such a context,
the concept \lq freeness' promises to give
a mathematical rigorous frame for otherwise ad
hoc approximations.

One example for such results is my joint work with
P. Neu, where we could show that a physically 
well-established approximation -- called CPA --
consists in replacing independent by free random variables
in the underlying Hamiltonian. This did not only 
clarify the mathematical structure of this approximation
but explained also the hitherto badly understood connection
between CPA and so-called Wegner models.
For more information in this direction one might consult
my survey \cite{Sp5}.

\bibliographystyle{amsplain}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{99}

\bibitem{B}
H.W.~Becker, \emph{Planar rhyme schemes}, Bull. Amer. Math.
Soc.~\textbf{58} (1952), 39.

\bibitem{Bia1}
P.~Biane, \emph{Some properties of crossings and partitions},
to appear in Discrete Math.

\bibitem{Bia2}
P.~Biane, \emph{Minimal factorizations of a cycle and central
multiplicative functions on the infinite symmetric group},
J.~Combin.~Th.~A \textbf{76} (1996), 197--212.

\bibitem{DRS}
P.~Doubilet, G.-C.~Rota, and R.~Stanley,
\emph{On the foundations of combinatorial theory VI: The idea
of generating function}, Proceedings of the Sixth 
Berkely Symposium on Mathematical Statistics and Probability,
Lucien M. Le Cam et al. (Ed.), University of California
Press, 1972, pp.~267--318.

\bibitem{Dyk}
K.~Dykema, 
\emph{Interpolated free group factors},
Pac. J. Math.
\textbf{163} (1994), 123--135.

\bibitem{E1}
P.H.~Edelman, \emph{Chain enumeration and non-crossing partitions},
Discrete Math.~\textbf{31} (1980), 171--180.

\bibitem{E2}
P.H.~Edelman, \emph{Multichains, non-crossing partitions and trees},
Discrete Math.~\textbf{40} (1982), 171--179.


\bibitem{K}
G.~Kreweras, \emph{Sur les partitions non-croisees d'un cycle},
Discrete Math. \textbf{1} (1972), 333--350.

\bibitem{N}
A.~Nica, \emph{$R$-transforms of free joint distributions, and
non-crossing partitions}, J. Funct. Anal.~\textbf{135} (1996),
271--296.

\bibitem{NS1}
A.~Nica and R.~Speicher, \emph{A "Fourier Transform" for
Multiplicative Functions on Non-Crossing Partitions}, Journal
of Algebraic Combinatorics \textbf{6} (1997), 141--160.

\bibitem{NS2}
A.~Nica and R.~Speicher, \emph{On the multiplication of free
$n$-tuples of non-commutative random variables}
(with an appendix by D. Voiculescu), Amer. J. Math. \textbf{118}
(1996), 799--837.

\bibitem{NS3}
A.~Nica and R.~Speicher, \emph{{$R$}-diagonal pairs---a common approach to
  {Haar} unitaries and circular elements}, Free Probability 
Theory (D.-V. Voiculescu,
  ed.), AMS, 1997, pp.~149--188.

\bibitem{NS4}
A.~Nica and R.~Speicher, \emph{Commutators of free random
variables}, to appear in Duke Math. J.;
also available under\newline
{\tt http://www.rzuser.uni-heidelberg.de/$\sptilde$L95}

\bibitem{P}
Y.~Poupard, \emph{Etude et denombrement paralleles des partitions
non croisees d'un cycle et des coupage d'un polygone convexe},
Discrete Math. \textbf{2} (1972), 279--288.

\bibitem{Rad}
F.~Radulescu,
\emph{Random matrices, amalgamated free products and 
subfactors of the von Neumann algebra of a free group, of noninteger
index}, Invent. math.~\textbf{115} (1994), 347--389.

\bibitem{R}
G.-C.~Rota, \emph{On the foundations of combinatorial theory I:
Theory of M\"obius functions}, Z. Wahrscheinlichkeitstheorie Verw.
Geb.~\textbf{2} (1964), 340--368.

\bibitem{Sh}
A.N.~Shiryayev, \emph{Probability} (Grad. Texts Math., vol.~95),
Springer, 1984.

\bibitem{SU}
R.~Simion and D. Ullman, \emph{On the structure of the lattice of
non-crossing partitions}, Discrete Math.~\textbf{98} (1991),
193--206.

\bibitem{Sp1}
R.~Speicher, \emph{A new example of \lq independence' and
\lq white noise'}, Probab. Theory Rel. Fields \textbf{84}
(1990), 141--159.

\bibitem{Sp2}
R. Speicher, \emph{Multiplicative functions on the lattice of
non-crossing partitions and free convolution},
Math. Ann.~\textbf{298} (1994), 611--628.

\bibitem{Sp3}
R.~Speicher, \emph{Combinatorial theory of the free product with
amalgamation and operator-valued free probability theory}
(Habilitationsschrift), to appear as Memoir of the AMS;
also available under \newline
{\tt http://www.rzuser.uni-heidelberg.de/$\sptilde$L95}

\bibitem{Sp4}
R.~Speicher, \emph{Free Convolution and the Random 
Sum of Matrices}, Publ. RIMS~\textbf{29} (1993), 731--744.

\bibitem{Sp5}
R.~Speicher, \emph{Physical applications of freeness},
to appear in the Proceedings of the International Congress
on Mathematical Physics, Brisbane, 1997;
also available under \newline
{\tt http://www.rzuser.uni-heidelberg.de/$\sptilde$L95}

\bibitem{V1}
D. Voiculescu, \emph{Symmetries of some reduced free product
$C^*$-algebras}, Operator Algebras and Their Connection with
Topology and Ergodic Theory (Lecture Notes in Mathematics 
\textbf{1132}), Springer, 1985, pp.~556--588.

\bibitem{V2}
D. Voiculescu, \emph{Addition of certain non-commuting
random variables}, J. Funct. Anal.~\textbf{66} (1986),
323--346.

\bibitem{V3}
D. Voiculescu, \emph{Multiplication of certain non-commuting random
variables}, J. Operator Theory~\textbf{18} (1987), 223--235.

\bibitem{V4}
D. Voiculescu, \emph{Limit laws for random matrices and free
products}, Invent. math.~\textbf{104} (1991), 201--220.

\bibitem{V5}
D. Voiculescu, \emph{Free probability theory: random matrices and
von Neumann algebras} Proceedings of the ICM 1994,
Birkh\"auser, 1995, pp.~227--241.

\bibitem{V6}
D. Voiculescu (ed.), \emph{Free Probability Theory} (Fields
Institute Communications, vol.~12), AMS, 1997

\bibitem{VDN}
D.V.~Voiculescu, K.J.~Dykema, and A.~Nica, \emph{Free
Random Variables} (CRM Monograph Series, vol.~1), AMS, 1993.

\end{thebibliography}


\end{document}