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

Sujets

• Sciences et techniques

Informations

• Publié par: opakito
• Nombre de lectures: 220
• Langue: English

Extrait

NOTE ON1CROSSING PARTITIONS

M. BERGERSON, A. MILLER, A. PLIML, V. REINER, P. SHEARER, D. STANTON, AND N. SWITALA

` ´ 2n−r−1 Abstract.It is shown that there arenoncrossing partitions of an n−r ` ´`´ n n−r−1 nset together with a distinguished block of sizerof these, and k−1k−2 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 1≤a < b < c < d≤nfor 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 numberC n and the number of noncrossing= , n+1n   1 n n partitions of [n] intokblocks is the Narayana number. n k−1k OurstartingpointisthemorerecentobservationofB´ona[2,Theorem1]that the number of partitions of [n] havingexactly onecrossing has the even simpler   2n−5 formula.B´ona’sproofutilizesthefactthatC n is also wellknown to count n−4 triangulations of a convex (nthis allows him to biject 1crossing partitions+ 2)gon; of [n] to dissections of anngon that use exactlyn−4 diagonals. The proof is then   1 n+d−1n−3 completed by pluggingd=n−of Kirkman4 into the formula d+1d d (first proven by Cayley; see [7]) for the number of dissections of anngon usingd diagonals. ThegoalhereistogeneralizeBo´na’sresulttocount1crossingpartitionsbytheir 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=Z n acts 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