Maximal increasing sequences in fillings of almost-moon polyominoes
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
It was proved by Rubey that the number of fillings with zeros and ones of a given moon polyomino thatdo not contain a northeast chain of a fixed size depends only on the set of column lengths of the polyomino. Rubeysproof uses an adaption of jeu de taquin and promotion for arbitrary fillings of moon polyominoes and deduces theresult for 01-fillings via a variation of the pigeonhole principle. In this paper we present the first completely bijectiveproof of this result by considering fillings of almost-moon polyominoes, which are moon polyominoes after removingone of the rows. More precisely, we construct a simple bijection which preserves the size of the largest northeast chainof the fillings when two adjacent rows of the polyomino are exchanged. This bijection also preserves the column sumof the fillings. In addition, we also present a simple bijection that preserves the size of the largest northeast chains, therow sum and the column sum if every row of the filling has at most one 1. Thereby, we not only provide a bijectiveproof of Rubeys result but also two refinements of it.Rubey a montr que le nombre de remplissages dun polyomino lunaire donn par des zros et des uns quine contiennent pas de chane nord-est dune taille fixe ne dpend que de lensemble des longueurs des colonnesdu polyomino. La preuve de Rubey utilise une adaptation du jeu de taquin et de la promotion sur des remplissagesarbitraires de polyominos lunaires et dduit le rsultat pour les remplissages 0/1 par inclusion-exclusion. Dans cetarticle, nous prsentons la premire preuve bijective de ce rsultat en considrant des remplissages de polyominospresque lunaires, qui sont des polyominos lunaires dont on a supprim une ligne. Plus prcisment, nous construisonsune bijection simple qui prserve la taille de la plus longue chane nord-est des remplissages lorsque deux lignesadjacentes du polyomino sont changes. Cette bijection prserve aussi la somme des colonnes des remplissages. Enoutre, nous prsentons aussi une bijection simple qui prserve la taille de la plus longue chane nord-est, la sommedes lignes et la somme des colonnes si chaque ligne du remplissage contient au plus un 1. Nous fournissons donc nonseulement une preuve bijective du rsultat de Rubey, mais aussi deux raffinements de celui-ci.
