[FOM] Computer searches for combinatorial bijections

[Jacques Carette]

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.
>   
and then asks
> 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 
further links).

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