Bijections Between Partitions by Two-Directional Rewriting Techniques
- Max Kanovich, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA
One basic activity in combinatorics is to establish combinatorial
identities by so-called `bijective proofs,'
which consist in constructing explicit bijections between two types
of the combinatorial objects under consideration.
We show how such bijective proofs can be established,
and how the bijections are computed by means of multiset rewriting,
for a variety of combinatorial problems involving partitions.
In particular, a new proof, the 'bijective' one, is given for
all equinumerous classes of the partition ideals of order 1
from the classical book ``The Theory of Partitions'' by G.Andrews.
Establishing the required bijections involves novel
two-directional reductions in the sense that forward and backward
application of rewrite rules head for two different normal forms
(representing the two combinatorial types).
It is well-known that non-overlapping multiset rules are
confluent. As for termination, it generally fails even
for multiset rewriting systems that satisfy certain natural
invariant conditions.
The main technical development of the paper,
which is important for establishing that the mapping yielding
the combinatorial bijection is functional,
is that the `restricted' two-directional strong normalization
holds for these multiset rewriting systems
(which yields, in addition, bounds on the complexity of the
computation of the combinatorial bijections).
Keywords: multiset rewriting, confluence, termination,
strong normalization, integer partitions,
partition identities, Euler's partition theorem