A cycle lemma for permutation inversions

DOI10.1016/S0012-365X(02)00254-6MaRDI QIDQ1849989zbMATH OpenWikidataFDO

Authors S. Brunetti, A. Del Lungo, F. Del Ristoro

Publication date 2 December 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00254-6

zbMATH Keywords

cyclic shiftGaussian binomial coefficientgreatest common divisorinversionmajor indexmultisetpermutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Factorials, binomial coefficients, combinatorial functions (05A10) Exact enumeration problems, generating functions (05A15)

Review text

The permutations of the multiset \(\{ 1^{m_1},2^{m_2}\}\) of size \(n=m_1+m_2\) can be enumerated by the number of inversions. For \(d=\gcd(m_1,m_2)\), the authors give a combinatorial proof that the remainders modulo \(n/d\) of the numbers of inversions are equally distributed, and the remainders modulo \(m_1/d\) of the numbers of inversions of permutations whose first term is 1 are equally distributed. These results provide combinatorial interpretations of some properties of the Gaussian binomial coefficients.

Recommendations

• Publication:4502529
• On inversions and cycles in permutations
• A new universal cycle for permutations
• A permutation regularity lemma
• Inversions in \(k\)-sorted permutations
• scientific article; zbMATH DE number 1270967
• On the constructions of n-cycle permutations
• The cycle lemma and some applications

Cited in

(4)

• Signatures of strings
• scientific article; zbMATH DE number 1504578 (Why is no real title available?)
• An equipartition property for the distribution of multiset permutation inversions
• On the polynomial \(\frac {1} {[n]_q}[ ^n_k]_q\)

This page was built for publication: A cycle lemma for permutation inversions

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