  We extend the relation between random matrices and free probability theory
from the level of expectations to the level of all correlation functions (which
are classical cumulants of traces of products of the matrices). We introduce
the notion of "higher order freeness" and develop a theory of corresponding
free cumulants. We show that two independent random matrix ensembles are free
of arbitrary order if one of them is unitarily invariant. We prove R-transform
formulas for second order freeness. Much of the presented theory relies on a
detailed study of the properties of "partitioned permutations".
