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

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

opakito

Langue

English

Publié par

opakito

Langue

English

Sciences et techniques

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 diﬀerent 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 k−1k OurstartingpointisthemorerecentobservationofB´ona[2,Theorem1]that the number of partitions of [n] havingexactly onecrossing has the even simpler   2n−5 formula.B´ona’sproofutilizesthefactthatCnis 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   1n+d−1n−3 completed by pluggingd=n−of Kirkman4 into the formula d+1d d (ﬁrst 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.

Deﬁnition 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

Voir