3 Pages
English

Note on 1 crossing partitions given a partition π of the set [n

Gain access to the library to view online
Learn more

Informations

Published by
Reads 220
Language English
NOTE ON1CROSSING PARTITIONS
M. BERGERSON, A. MILLER, A. PLIML, V. REINER, P. SHEARER, D. STANTON, AND N. SWITALA
` ´ 2nr1 Abstract.It is shown that there arenoncrossing partitions of an nr ` ´`´ n nr1 nset together with a distinguished block of sizerof these, and k1k2 havekrapnititwsnoohtiregaltsuB´ofaoonnecrossing.lbinizaleren,gksoc Furthermore, when one evaluates naturalqanalogues of these formulae forq th annroot of unity of orderd, one obtains the number of such objects having dfold rotational symmetry.
Given a partitionπof the set [n] :={1,2, . . . , n}, acrossinginπis a quadruple of integers (a, b, c, d) with 1a < b < c < dnfor whicha, care together in a block, andb, dIt is wellknown [10, Exericsesare together in a different block. 6.19(pp)],[4] that the number ofnoncrossing partitionsof [n] (that is, those with   1 2n no crossings) is the Catalan numberCnand the number of noncrossing= , n+1n  1n n partitions of [n] intokblocks is the Narayana number. n k1k OurstartingpointisthemorerecentobservationofB´ona[2,Theorem1]that the number of partitions of [n] havingexactly onecrossing has the even simpler   2n5 formula.B´onasproofutilizesthefactthatCnis also wellknown to count n4 triangulations of a convex (nthis allows him to biject 1crossing partitions+ 2)gon; of [n] to dissections of anngon that use exactlyn4 diagonals. The proof is then  1n+d1n3 completed by pluggingd=nof Kirkman4 into the formula d+1d d (first proven by Cayley; see [7]) for the number of dissections of anngon usingd diagonals. ThegoalhereistogeneralizeBo´nasresulttocount1crossingpartitionsbytheir number of blocks, and also to examine a naturalqanalogue with regard to thecyclic sieving phenomenonshown in [8] for certainqCatalan andqNarayana numbers. The crux is the observation that 1crossing partitions of [n] biject naturally with noncrossing partitions of [n] having a distinguished 4element block:replace the crossing pair of blocks{a, c},{b, d}with a single distinguished block{a, b, c, d}. Thus one should count the following more general objects.
Definition 1.Anrblocked noncrossing partition of[n] is a pair (π, B) of a non crossing partitionπtogether with a distinguishedrelement blockBofπ.
Note that the notion of a crossing in a partition is invariant under cyclic rotations i7→i+ 1modnof the set [nthe cyclic group]. ConsequentlyC=Znacts on the
Date: August 2006. Key words and phrases.noncrossing partition, cyclic sieving phenonomenon. This work was the result of an REU at the University of Minnesota School of Mathematics in Summer 2006, mentored by V. Reiner and D. Stanton, and supported by NSF grants DMS0601010 and DMS0503660.The authors also thank D. Armstrong for helpful conversations. 1