TY - JOUR
T1 - Bijective counting of plane bipolar orientations and Schnyder woods
AU - Fusy, Éric
AU - Poulalhon, Dominique
AU - Schaeffer, Gilles
PY - 2009/1/1
Y1 - 2009/1/1
N2 - A bijection Φ is presented between plane bipolar orientations with prescribed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with prescribed extremities. This yields a combinatorial proof of the following formula due to Baxter for the number Θi j of plane bipolar orientations with i non-polar vertices and j inner faces: Θi j = 2 frac((i + j) ! (i + j + 1) ! (i + j + 2) !, i ! (i + 1) ! (i + 2) ! j ! (j + 1) ! (j + 2) !) . In addition, it is shown that Φ specializes into the bijection of Bernardi and Bonichon between Schnyder woods and non-crossing pairs of Dyck words. This is the extended and revised journal version of a conference paper with the title "Bijective counting of plane bipolar orientations", which appeared in Electr. Notes in Discr. Math. pp. 283-287 (Proceedings of Eurocomb'07, 11-15 September 2007, Sevilla).
AB - A bijection Φ is presented between plane bipolar orientations with prescribed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with prescribed extremities. This yields a combinatorial proof of the following formula due to Baxter for the number Θi j of plane bipolar orientations with i non-polar vertices and j inner faces: Θi j = 2 frac((i + j) ! (i + j + 1) ! (i + j + 2) !, i ! (i + 1) ! (i + 2) ! j ! (j + 1) ! (j + 2) !) . In addition, it is shown that Φ specializes into the bijection of Bernardi and Bonichon between Schnyder woods and non-crossing pairs of Dyck words. This is the extended and revised journal version of a conference paper with the title "Bijective counting of plane bipolar orientations", which appeared in Electr. Notes in Discr. Math. pp. 283-287 (Proceedings of Eurocomb'07, 11-15 September 2007, Sevilla).
U2 - 10.1016/j.ejc.2009.03.001
DO - 10.1016/j.ejc.2009.03.001
M3 - Article
AN - SCOPUS:67650444337
SN - 0195-6698
VL - 30
SP - 1646
EP - 1658
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
IS - 7
ER -