A bijection between well-labelled positive paths and matchings

MaRDI QIDQ624822zbMATH OpenFDO

Authors Olivier Bernardi, Bertrand Duplantier, Philippe Nadeau

Publication date 9 February 2011

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.5379, http://www.emis.de/journals/SLC/wpapers/s63bernadu.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

matchingsubpolytopes partitioningwell-labelled positive path

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Abstract: 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!.

Recommendations

• A bijection between partially directed paths in the symmetric wedge and matchings
• scientific article; zbMATH DE number 2245581
• n! matchings, n! posets (extended abstract)
• $n!$ matchings, $n!$ posets
• Ascending runs in permutations and valued Dyck paths

Cited in

(12)

• The peak and descent statistics over ballot permutations
• Refined Eulerian numbers and ballot permutations
• A decomposition of ballot permutations, pattern avoidance and Gessel walks
• Ballot permutations and odd order permutations
• The moment polytope of the abelian polygon space
• The symplectic geometry of closed equilateral random walks in 3-space
• Arcsine laws for random walks generated from random permutations with applications to genomics
• A complete enumeration of Ballot permutations avoiding sets of small patterns
• A bijection between partially directed paths in the symmetric wedge and matchings
• Callan permutations and odd order permutations
• Enriched cycle structures and roots of permutations
• A Toeplitz property of ballot permutations and odd order permutations

This page was built for publication: A bijection between well-labelled positive paths and matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q624822)