Dyck tilings, linear extensions, descents, and inversions

Abstract

Dyck tilings were introduced by Kenyon and Wilson in their study of double-dimer pairings. They are certain kinds of tilings of skew Young diagrams with ribbon tiles shaped like Dyck paths. We give two bijections between "cover-inclusive'' Dyck tilings and linear extensions of tree posets. The first bijection maps the statistic (area + tiles)/2 to inversions of the linear extension, and the second bijection maps the "discrepancy'' between the upper and lower boundary of the tiling to descents of the linear extension.

Keywords

• dyck path
• linear extension
• tree poset
• perfect matching
• dyck tiling
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]