<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
A Translation Method for Finding Combinatorial Bijections
Philip Matchett Wood and Doron Zeilberger
Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Road, Piscataway, NJ 08854-8019, USA
{matchett, zeilberg}@math.rutgers.edu
Department of Mathematics, University of South Carolina, LeConte College, 1523 Greene Street, Columbia, SC 29208, USA
Annals of Combinatorics 13 (3) pp.383-402 September, 2009
AMS Subject Classification: 05A19
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.
Keywords: bijection, bijective proof, combinatorial identity


1. Benjamin, A.T., Quinn, J.J.: Proofs That Really Count: The Art of Combinatorial Proof. Mathematical Association of America, Washington (2003)

2. Garsia, A.M., Milne, S.C.: A Rogers-Ramanujan bijection. J. Combin. Theory Ser. A 31, 289-–339 (1981)

3. Garsia, A.M., Milne, S.C.: Method for constructing bijections for classical partition identities. Proc. Nat. Acad. Sci. U.S.A. 78, 2026-–2028 (1981)

4. Wood, P.M.: A bijective proof of fn+4 + f1 +2 f2 +  +n fn = (n+1) fn+2 +3. Integers 6, 4 pp. (2006)

5. Wood, P.M.: Bijective proofs for Fibonacci identities related to Zeckendorf's Theorem. Fibonacci Quart. 45, 138–-145 (2007)

6. Wood, P.M.: Five Maple packages: BijTools, Examples, Fibonacci, TransMethodZeck, ZeckFibBijections, online at http://www.math.rutgers. edu/matchett/Publications/Maple.html

7. Werman, M., Zeilberger, D.: A bijective proof of Cassini's Fibonacci identity. Discrete Math. 58, p. 109 (1986)

8. Zeilberger, D.: Enumerative and algebraic combinatorics, In: Gowers, T. (ed.) Princeton Companion of Mathematics, pp. 556-–560. Princeton University Press, Princeton (2008)