One basic activity in combinatorics is to establish combinatorial
identities by so-called `bijective proofs,' which consists in
constructing explicit bijections between two types of the
combinatorial objects under consideration.
We show how such bijective proofs can be extracted in a systematic way
from the `lattice properties' of partition ideals, and how the desired
bijections are computed by means of multiset rewriting, for a variety
of combinatorial problems involving partitions. Establishing the
required bijections involves a two-directional reduction technique
novel in the sense that forward and backward applications of rewrite
rules head, respectively, for two different normal forms (representing
the two combinatorial types).
The basic methodological idea is to study the filters, the complement
of the partition ideals, and more specifically, the sets of all
minimal elements of these filters (`supports').
Based on the two-way rewriting technique, we fully characterize all
equinumerous partition ideals when each of these supports is made of
pairwise disjoint multisets.
As a corollary, a first `bijective' (and transparent) proof is given
for all equinumerous classes of the partition ideals of order 1
from the classical book `The Theory of Partitions' by G. Andrews.
Furthermore, our criterion provides the bijection that preserves more
structure (a `statistics' expressing how much a partition is far from
being in the ideal).
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 balance conditions.
The main technical development here (which is important for
establishing that the mapping yielding the combinatorial bijection is
functional) is that the restricted two-directional strong
normalization holds for the multiset rewriting systems in question.
Lastly, we address the case of filters having overlapping supports.
We show how two-directional multiset rewriting techniques can
be used to construct `bijective proofs' for a new series of
partition identities related to Fibonacci and Lucas numbers.
No acquaintance with logic or math is required.
|