Abstract:  We present results on the enumeration of crossings and nestings for matchings and set par- titions. Using a bijection between partitions and vacillating tableaux, we show that if we x the sets of minimal block elements and maximal block elements, the crossing number and the nesting number of partitions have a symmetric joint distribution. It follows that the crossing numbers and the nesting numbers distributed symmetrically over all partitions of [n], as well as over all matchings on [2n]. As a corollary, the number of k-noncrossing partitions is equal to the number of k-nonnesting partitions. The same is also true for matchings. An application is given to the enumeration of matchings with no k-crossing (or with no k-nesting).

  AMS Classification:  05A18, 05A15.

  Keywords:  Crossing, nesting, partition, vacillating tableau.

  Download:   DVI