A Bijection Between Well-Labelled Positive Paths and Matchings

Olivier Bernardi ; Bertrand Duplantier ; Philippe Nadeau

Séminaire lotharingien de combinatoire, Tome 63 (2010)

Résumé

A well-labelled positive path of size n is a pair (p,\sigma) made of a word p=p₁p₂...p_n-1 on the alphabet {-1,0,+1} such that \sum_{i=1}^j p_i >= 0 for all j=1,...,n-1, together with a permutation \sigma=\sigma₁\sigma₂...\sigma_n of {1,...,n} such that p_i=-1 implies \sigma_i<\sigma_i+1, while p_i=1 implies \sigma_i>\sigma_i+1. We establish a bijection between well-labelled positive paths of size n and matchings (i.e., fixed-point free involutions) on {1,...,2n}. This proves that the number of well-labelled positive paths is (2n-1)!!=(2n-1).(2n-3)...3.1.

Well-labelled positive paths appeared recently in the author's article "Partition function of a freely-jointed chain in a half-space" [in preparation] as a useful tool for studying a polytope \Pi_n related to the space of configurations of the freely-jointed chain (of length n) in a half-space. The polytope \Pi_n consists of points (x₁,...,x_n) in [-1,1]ⁿ such that \sum_{i=1}^j x_i >= 0 for all j=1,...,n, and it was shown that well-labelled positive paths of size n are in bijection with a collection of subpolytopes partitioning \Pi_n. Given that the volume of each subpolytope is 1/n!, our results prove combinatorially that the volume of \Pi_n is (2n-1)!!/n!.

Our bijection has other enumerative corollaries in terms of up-down sequences of permutations. Indeed, by specialising our bijection, we prove that the number of permutations of size n such that each prefix has no more ascents than descents is [(n-1)!!]² if n is even and n!!(n-2)!! if n is odd.