MIT Combinatorics Seminar
Crossings and nestings of matchings and partitions
Richard Stanley
(MIT)
http://wwwmath.mit.edu/~rstan/
Friday, October 29, 2004
4:15 pm Room 2338
ABSTRACT

Let M be a complete matching (graph with n disjoint edges)
of the set {1,2,...,2n}. A crosssing (respectively,
nesting) of M is two edges (i,j)
and (k,m) of M such
that i<k<j<m (respectively, i<k<m<j).
It is wellknown that the
number of complete matchings of the set {1,2,...,2n} with no
crossings or with no nestings is the Catalan number
C_{n}.
We discuss
how the theory of oscillating tableaux, which originally arose in the
representation theory of the symplectic and orthogonal groups and the
Brauer algebra, can be used to obtain further results on crossings and
nestings of matchings. In particular, if
f_{n}(i,j)
is the number of
complete matchings of {1,2,...,2n} with at most i mutually
crossing edges and with at most j mutually nested edges, then
f_{n}(i,j)=f_{n}(j,i).
Moreover, the GesselZeilberger reflection
principle allows the determination of the generating function
F_{i}(x) =
∑_{n≥0} f_{n}(i,∞)
x^{2n}/(2n)!. Similar
results hold when matchings are replaced with set partitions, using a
variation of oscillating tableaux called vacillating tableaux.
This is joint work with William Y. C. Chen, Eva Y. P. Deng, Rosena R.
X. Du, and Catherine H. Yan.


