A translation method for finding combinatorial bijections

Philip Matchett Wood, Doron Zeilberger

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)383-402
Number of pages20
JournalAnnals of Combinatorics
Volume13
Issue number3
DOIs
StatePublished - Oct 2009

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Keywords

  • Bijection
  • Bijective proof
  • Combinatorial identity

Fingerprint

Dive into the research topics of 'A translation method for finding combinatorial bijections'. Together they form a unique fingerprint.

Cite this