#####
Séminaire Lotharingien de Combinatoire, B63e (2010), 13 pp.

# Olivier Bernardi, Bertrand Duplantier and Philippe Nadeau

# A Bijection Between Well-Labelled Positive Paths and Matchings

**Abstract.**
A *well-labelled positive path* of size *n* is a pair (**p**,*\sigma*)
made of a word
**p**=*p*_{1}*p*_{2}...*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*_{1}*\sigma*_{2}...*\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,...,2*n*}. This proves that the number of well-labelled
positive paths is (2*n*-1)!!=(2*n*-1).(2*n*-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*_{1},...,*x*_{n}) in [-1,1]^{n} 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
(2*n*-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)!!]^{2} if *n* is even and
*n*!!(*n*-2)!! if *n* is odd.

Received: November 11, 2009.
Accepted: April 22, 2010.
Final Version: April 23, 2010.

The following versions are available: