Bijective counting of plane bipolar orientations

Éric Fusy; Dominique Poulalhon; Gilles Schaeffer

doi:10.1016/j.endm.2007.07.049

Bijective counting of plane bipolar orientations

Éric Fusy, Dominique Poulalhon, Gilles Schaeffer

Research output: Contribution to journal › Article › peer-review

Abstract

We introduce a bijection between plane bipolar orientations with fixed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with some specific extremities. Writing θ{symbol}_{i j} for the number of plane bipolar orientations with (i + 1) vertices and (j + 1) faces, our bijection provides a combinatorial proof of the following formula due to Baxter:(1)θ{symbol}_{i j} = 2 frac((i + j - 2) ! (i + j - 1) ! (i + j) !, (i - 1) ! i ! (i + 1) ! (j - 1) ! j ! (j + 1) !) .

Original language	English
Pages (from-to)	283-287
Number of pages	5
Journal	Electronic Notes in Discrete Mathematics
Volume	29
Issue number	SPEC. ISS.
DOIs	https://doi.org/10.1016/j.endm.2007.07.049
Publication status	Published - 15 Aug 2007

Keywords

bijection
bipolar orientations
non-intersecting paths

Access to Document

10.1016/j.endm.2007.07.049

Cite this

@article{b8734ce9ea5549558731ed0456cf1096,

title = "Bijective counting of plane bipolar orientations",

abstract = "We introduce a bijection between plane bipolar orientations with fixed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with some specific extremities. Writing θ\{symbol\}i j for the number of plane bipolar orientations with (i + 1) vertices and (j + 1) faces, our bijection provides a combinatorial proof of the following formula due to Baxter:(1)θ\{symbol\}i j = 2 frac((i + j - 2) ! (i + j - 1) ! (i + j) !, (i - 1) ! i ! (i + 1) ! (j - 1) ! j ! (j + 1) !) .",

keywords = "bijection, bipolar orientations, non-intersecting paths",

author = "{\'E}ric Fusy and Dominique Poulalhon and Gilles Schaeffer",

year = "2007",

month = aug,

day = "15",

doi = "10.1016/j.endm.2007.07.049",

language = "English",

volume = "29",

pages = "283--287",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

number = "SPEC. ISS.",

}

TY - JOUR

T1 - Bijective counting of plane bipolar orientations

AU - Fusy, Éric

AU - Poulalhon, Dominique

AU - Schaeffer, Gilles

PY - 2007/8/15

Y1 - 2007/8/15

N2 - We introduce a bijection between plane bipolar orientations with fixed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with some specific extremities. Writing θ{symbol}i j for the number of plane bipolar orientations with (i + 1) vertices and (j + 1) faces, our bijection provides a combinatorial proof of the following formula due to Baxter:(1)θ{symbol}i j = 2 frac((i + j - 2) ! (i + j - 1) ! (i + j) !, (i - 1) ! i ! (i + 1) ! (j - 1) ! j ! (j + 1) !) .

AB - We introduce a bijection between plane bipolar orientations with fixed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with some specific extremities. Writing θ{symbol}i j for the number of plane bipolar orientations with (i + 1) vertices and (j + 1) faces, our bijection provides a combinatorial proof of the following formula due to Baxter:(1)θ{symbol}i j = 2 frac((i + j - 2) ! (i + j - 1) ! (i + j) !, (i - 1) ! i ! (i + 1) ! (j - 1) ! j ! (j + 1) !) .

KW - bijection

KW - bipolar orientations

KW - non-intersecting paths

U2 - 10.1016/j.endm.2007.07.049

DO - 10.1016/j.endm.2007.07.049

M3 - Article

AN - SCOPUS:34547700504

SN - 1571-0653

VL - 29

SP - 283

EP - 287

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - SPEC. ISS.

ER -

Bijective counting of plane bipolar orientations

Abstract

Keywords

Access to Document

Fingerprint

Cite this