首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Crossings and nestings of matchings and partitions
Authors:William Y C Chen  Eva Y P Deng  Rosena R X Du  Richard P Stanley  Catherine H Yan
Institution:Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, People's Republic of China ; Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, People's Republic of China ; Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, People's Republic of China ; Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139 ; Department of Mathematics, Texas A&M University, College Station, Texas 77843-3368
Abstract:We present results on the enumeration of crossings and nestings for matchings and set partitions. Using a bijection between partitions and vacillating tableaux, we show that if we fix 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 are 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).

Keywords:Crossing  nesting  partition  vacillating tableau
点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息
点击此处可从《Transactions of the American Mathematical Society》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号