×

An equivalence relation on the symmetric group and multiplicity-free flag \(h\)-vectors. (English) Zbl 1291.05012

Summary: We consider the equivalence relation   on the symmetric group \(S_n\) generated by the interchange of two adjacent elements \(a_i\) and \(a_{i+1}\) of \(w=a_1\cdots a_n \in \mathcal{S}_n\) such that \(|a_{i} - a_{i+1}|=1\). We count the number of equivalence classes and the sizes of equivalence classes. The results are generalized to permutations of multisets using umbral techniques. In the original problem, the equivalence class containing the identity permutation is the set of linear extensions of a certain poset. Further investigation yields a characterization of all finite graded posets whose flag \(h\)-vector takes on only the values \(0,\pm 1\).

MSC:

05A15 Exact enumeration problems, generating functions
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI arXiv