I am looking for a bijection between permutations in $\mathfrak S_n$ with a certain weight and a second set, which arises by interpreting the expression $$ \frac{1}{2}\left(1 + \exp(q \log\left(\frac{1+x}{1-x}\right)\right) $$ as the exponential generating function for permutations with only odd cycles, where each cycle is coloured blue or red, up to interchanging the colours. Each cycle carries the weight $q$. For example, there are $4!=24$ cycles of length 5, $\binom{5}{2}\cdot 2\cdot 2^2 = 80$ coloured permutations with a 3-cycle and two singletons, and $2^4 = 16$ coloured permutations with 5 singletons.

On the other hand, the weight of a permutation in $\mathfrak S_n$ is obtained by computing https://www.findstat.org/StatisticsDatabase/St000389oMp00093oMp00127oMp00066oMp00090 : write down the cycle decomposition of the permutation, cycles ordered by minimal elements, and such that the minimal element of each cycle comes first. Then erase the parenthesis and interpret the result as a permutation $\sigma$ in one-line notation. Finally, interpret this permutation as a Dyck path - drawn as a subdiagonal path from $(0,0)$ to $(n,n)$ - with peaks at $\{(i, \sigma_i-1) | \sigma_i\text{ is a right-to-left minimum of }\sigma\}$. For example, the permutation $2,4,3,1$ has cycle decomposition $(1,2,4)(3)$, thus $\sigma=1,2,4,3$, so the Dyck path has peaks at $(4,3-1)$, $(2,2-1)$, and $(1, 1-1)$. Each ascent of odd length of this Dyck path carries the weight $q$.

This question arises by comparing this answer with this, and the following comments.


1 Answer 1


In what follows I describe a bijection between your colored odd cycle only permutations and all permutations. Under this bijection, the number of cycles of the initial odd cycle only permutation becomes the number of cycles of the output permutation plus some additional factor (which could be described but seems a bit complicated). I am not sure how this weight relates to your proposed weight— see my comments below the answer.

Start with a permutation with only odd cycles, and interpret the red/blue coloring as a binary string of length equal to the number of cycles minus one.

Write the permutation in “standard cycle form” with the biggest element of each cycle first and with biggest elements increasing from left to right. E.g., (3)(746)(95182)

Then process the binary word by starting at the leftmost cycle and whenever we see a one move the last element of that cycle to be the last element of the cycle to its right (whereas do nothing when we see a zero). Proceed to the next cycle when processing the next letter, and so on.

E.g., with (3)(746)(95182) and the word 11 we process the first 1 and get (7463)(95182), then we process the second 1 and end with (746)(951823).

The inverse is obtained by starting with any permutation and moving the last elements of the cycles (in standard form) from right to left so as to make sure the cycles are all of odd length.

The basic idea behind this bijection appears in Section 6.2 of Bóna’s “Walk Through Combinatorics” textbook (3rd ed.) and is explained in the answers to the previous MO question: Permutations with all cycles odd length and permutations with all cycles even length.

  • $\begingroup$ Is it clear that this preserves (a variation of) the weight? $\endgroup$ Dec 29, 2021 at 13:10
  • $\begingroup$ I’m not quite sure about the weight (certainly you can extract some kind of weight from this bijection). But I’m a bit suspicious of what you have right now. For example, why do you start by applying the “Foata’s fundamental transform” to the permutation? This should not affect the distribution of the statistic. $\endgroup$ Dec 29, 2021 at 17:04
  • $\begingroup$ Moreover, unless I am misunderstanding what “ascent of odd length” means, you are suggesting we count some subset of the LRM in the statistic. But actually the above bijection shows we should count a superset of the LRM (equidistributed with # of cycles, again thanks to the fundamental transform). $\endgroup$ Dec 29, 2021 at 17:07
  • 1
    $\begingroup$ Oh I see now the source of my confusion: the first step of your procedure is not the fundamental transformation (in particular, it is not a bijection on permutations). $\endgroup$ Dec 29, 2021 at 18:17
  • 1
    $\begingroup$ That is a beautiful bijection, regardless wether it solves the original question. $\endgroup$ Jan 29, 2022 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.