Major index for 01-fillings of moon polyominoes Academic Article

abstract

• We propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M,s;A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations. 2010 Elsevier Inc.

authors

• Yan, Catherine

published proceedings

• JOURNAL OF COMBINATORIAL THEORY SERIES A

author list (cited authors)

• Chen, W., Poznanovic, S., Yan, C. H., & Yang, A.

citation count

• 6

complete list of authors

• Chen, William YC||Poznanovic, Svetlana||Yan, Catherine H||Yang, Arthur LB

publication date

• January 2010

publisher

• Elsevier  Publisher

published in

• Journal of Combinatorial Theory Series A  Journal

keywords

• 01-filling
• Major Index
• Moon Polyomino
• North-east Chain

Digital Object Identifier (DOI)

• 10.1016/j.jcta.2010.01.004

start page

• 1058

end page

• 1081

volume

• 117

issue

• 8

URL

• http://dx.doi.org/10.1016/j.jcta.2010.01.004