TY - JOUR
T1 - A translation method for finding combinatorial bijections
AU - Wood, Philip Matchett
AU - Zeilberger, Doron
N1 - Funding Information:
Acknowledgments. The first author would like to thank the National Defense Science and Engineering Graduate (NDSEG) Fellowship program for providing support for this research.
PY - 2009/10
Y1 - 2009/10
N2 - Consider a combinatorial identity that can be proved by induction. In this paper, we describe a general method for translating the inductive proof into a recursive bijection. Furthermore, we will demonstrate that the resulting recursive bijection can often be defined in a direct, non-recursive way. Thus, the translation method often results in a bijective proof of the identity that helps illuminate the underlying combinatorial structures. This paper has two main parts: First, we describe the translation method and the accompanying Maple code; and second, we give a few examples of how the method has been used to discover new bijections.
AB - Consider a combinatorial identity that can be proved by induction. In this paper, we describe a general method for translating the inductive proof into a recursive bijection. Furthermore, we will demonstrate that the resulting recursive bijection can often be defined in a direct, non-recursive way. Thus, the translation method often results in a bijective proof of the identity that helps illuminate the underlying combinatorial structures. This paper has two main parts: First, we describe the translation method and the accompanying Maple code; and second, we give a few examples of how the method has been used to discover new bijections.
KW - Bijection
KW - Bijective proof
KW - Combinatorial identity
UR - http://www.scopus.com/inward/record.url?scp=70449529660&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449529660&partnerID=8YFLogxK
U2 - 10.1007/s00026-009-0024-y
DO - 10.1007/s00026-009-0024-y
M3 - Article
AN - SCOPUS:70449529660
SN - 0218-0006
VL - 13
SP - 383
EP - 402
JO - Annals of Combinatorics
JF - Annals of Combinatorics
IS - 3
ER -