d-regular set partitions and rook placements

zbMATH Open1283.05029arXiv1307.0495MaRDI QIDQ846049FDOQ846049

Authors: Anisse Kasraoui 

Publication date: 29 January 2010

Published in: Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Abstract: We consider the enumeration of ordered set partitions avoiding a permutation pattern, as introduced by Godbole, Goyt, Herdan and Pudwell. Let $o{p}_{n,k}(p)$ be the number of ordered set partitions of $1,2,ldots,n$ into $k$ blocks that avoid a permutation pattern $p$. We establish an explicit identity between the number $o{p}_{n,k}(p)$ and the numbers of words avoiding the inverse of $p$. This identity allows us to easily translate results on pattern-avoiding words obtained in earlier works into equivalent results on pattern-avoiding ordered set partitions. In particular, emph{(a)} we determine the asymptotic growth rate of the sequence $(o{p}_{n,k}(p){)}_{ngeq1}$ for every positive $k$ and every permutation pattern $p$, emph{(b)} we partially confirm a conjecture of Godbole et al. concerning the variation of the sequences $(o{p}_{n,k}p){)}_{1leqkleqn}$, emph{(c)} we undertake a detailed study of the number of ordered set partitions avoiding a pattern of length 3.

Full work available at URL: https://arxiv.org/abs/1307.0495

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

set partitionsrook placementsreduction identity

Mathematics Subject Classification ID

Partitions of sets (05A18)

Cited In (3)

• ROOK PLACEMENTS AND CLASSIFICATION OF PARTITION VARIETIES B\ M_λ
• Rook placements and cellular decomposition of partition varieties
• A simple bijection for enhanced, classical, and 2-distant \(k\)-noncrossing partitions

This page was built for publication: \(d\)-regular set partitions and rook placements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q846049)