# [FOM] Computer searches for combinatorial bijections

Jacques Carette carette at mcmaster.ca
Wed Oct 11 16:14:03 EDT 2006

```Timothy Y. Chow describes work of Zeilberger which involves,
> The examples described by Zeilberger still require the programmer to
> create data structures and algorithms that are highly specific to the
> particular pair of combinatorial objects in question.  But ideally, one
> would like to create a general environment with a language that is
> flexible enough to allow the description of a wide variety of
> combinatorial objects.  The user would then describe two classes of
> combinatorial objects in this formal language, and the program would then
> go off in search of a bijection between the two, returning with a
> description of a bijection and a proof that it is correct.
>
> The question I have is, is there any existing environment or language that
> might be adaptable to such a project?
>
Yes, there is.  First, the proper mathematical framework to do this in
is indeed that of *species*, as you mention.  A very readable account is
a book by Bergeron, Labelle and Leroux, see
http://bergeron.math.uqam.ca/Species/especes.html.  They make the theory
very practical and down-to-earth (unlike some accounts).
One can get a taste of the theory at
http://en.wikipedia.org/wiki/Combinatorial_species (which contains

Part of the theory of species for combinatorial structures has been
implemented in the Maple package 'combstruct' (short for combinatorial
structures).  See http://algo.inria.fr/libraries/autocomb/ for some
examples of its use.

Note that combstruct can at least help you prove some basic things about
your combinatorial structures -- for example you can often show that two
structures' generating functions are equal.  This is certainly a
necessary, but unfortunately not sufficient, condition for two
structures to be equal.

The framework of species gives one a lot of canonical maps and tools
between species, which help tremendously in the automation of possible
bijections.  The aforementioned book is filled with further insights.

The approach I would take would be based on so-called 'combinatorial
differential equations', in exactly the same way the WZ-method uses
recurrences for proving combinatorial identities.  The real trick would
be to find a way to unwind such equations into an english description of
a bijection -- that I don't have a handle on right now.

Jacques
```