A Bijection between well-labelled positive paths and matchings

Details A Bijection between well-labelled positive paths and matchings A Bijection between well-labelled positive paths and matchings

2009-03-31

arxiv.org/abs/0903.5379v1

Seminaire Lotharingien de Combinatoire 63 (2010) B63e

Mathematics

Combinatorics

Scientific paper

A well-labelled positive path of size n is a pair (p,\sigma) made of a word p=p_1p_2...p_{n-1} on the alphabet {-1, 0,+1} such that the sum of the letters of any prefix is non-negative, together with a permutation \sigma of {1,2,...,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,...,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)!!]^2 if n is even and n!!(n-2)!! otherwise. Our result also prove combinatorially that the n-dimensional polytope consisting of all points (x_1,...,x_n) in [-1,1]^n such that the sum of the first j coordinates is non-negative for all j=1,2,...,n has volume (2n-1)!!/n!.

Affiliated with

Also associated with

No associations

Rating

A Bijection between well-labelled positive paths and matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Bijection between well-labelled positive paths and matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Bijection between well-labelled positive paths and matchings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-20068