In situations where two involutions act we can use the following result which allows to replace certain identities of orders by bijections:
are disjoint decompositions of the finite sets
where
.
The Garsia-Milne bijection
We assume that
and 
, that
is a sign-preserving bijection, and that 
are sign-reversing involutions such that
.
Then the following mapping is a bijection:
Proof: Easy checks give the following implications:
and as an immediate consequence, for each natural number 
:
implies that
We now prove the existence of 
indirectly.
Consider 
. If does not exist, then the
implications mentioned above yield that
, for each natural .
But this set is supposed to be finite. Hence there would be
such that 
, and thus (assume
): 
, a contradiction to the
earlier implications since 
.
Finally we mention that
is injective for the following reason:
Assume 
, for which 
. They satisfy
and hence also (assuming 
)
Thus either 
, which is equivalent to 
, or there exists a
such that
since otherwise we had 
.
This contradicts to the minimality of 
.
An application to certain inclusion-exclusion situations runs as follows.
Consider two families 
and 
of subsets of two finite sets 
and 
. For each 
we put
The Principle of Inclusion and Exclusion yields
In the case when 
, for each , these two families 
and 
are called
sieve-equivalent ,
a property which implies 
.
Now we assume that this holds and that furthermore we are given,
for each , a bijection
Then the Garsia-Milne construction in fact allows us to sharpen the identity
by replacing it by a bijection
since we need only put
A sign preserving bijection is
and the involutions 
are as
in the proof of the Principle of Inclusion and Exclusion.
Another consequence of the Garsia-Milne bijection is (exercise 
):
.
The Two Involutions' Principle If 
is a disjoint decomposition of the finite set , and
are
sign-reversing involutions such that
, then each orbit of
either consists of a fixed point of 
alone, or it contains exactly one fixed point of 
and exactly one fixed
point of 
, or it contains neither a fixed point of nor a fixed
point of . This means in particular that there is a canonical
bijection
between 
and 
, namely the that maps
onto the fixed point of that lies in the orbit
of 
.
Exercises
E 
.
Evaluate the derangement number
i.e. the number of fixed point free elementes in 
Derive a
recursion for these numbers and show that they
tend to 
.