DMTCS Proceedings, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)

Font Size:  Small  Medium  Large

A bijection between noncrossing and nonnesting partitions of types A and B

Ricardo Mamede


The total number of noncrossing partitions of type Ψ is the nth Catalan number 1 / n+1binom(2n, n) when Ψ=An-1, and the binomial coefficient binom(2n, n) when Ψ=Bn, and these numbers coincide with the correspondent number of nonnesting partitions. For type A, there are several bijective proofs of this equality; in particular, the intuitive map, which locally converts each crossing to a nesting, is one of them. In this paper we present a bijection between nonnesting and noncrossing partitions of types A and B that generalizes the type A bijection that locally converts each crossing to a nesting.
Résumé. Le nombre total des partitions non-croisées du type Ψ est le n-ème nombre de Catalan 1 / n+1binom(2n, n) si Ψ=An-1, et le coefficient binomial binom(2n, n) si Ψ=Bn, et ces nombres son coïncidents avec le nombre correspondant des partitions non-emboîtées. Pour le type A, il y a plusieurs preuves bijectives de cette égalité; en particulier, la intuitive fonction, qui convertit localement chaque croisée en une emboîtée, c'est un d'entre eux. Dans ce papier nous présentons une bijection entre partitions non-croisées et non-emboîtées des types A et B qui généralise la bijection du type A qui localement convertit chaque croisée en une emboîtée.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional