A Bijection between well-labelled positive paths and matchings

Original · EN

A well-labelled positive path of size n is a pair (p,σ) made of a word p=p₁p₂...pₙ₋₁ on the alphabet -1, 0,+1 such that the sum of the letters of any prefix is non-negative, together with a permutation σof 1,2,...,n such that pᵢ=-1 implies σ(i)<σ(i+1), while pᵢ=1 implies σ(i)>σ(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,...,2n. This proves that the number of well-labelled positive paths is (2n-1)!!. By specialising our bijection, we also 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)!! otherwise. Our result also prove combinatorially that the n-dimensional polytope consisting of all points (x₁,...,xₙ) in [-1,1]ⁿ such that the sum of the first j coordinates is non-negative for all j=1,2,...,n has volume (2n-1)!!/n!.