  In this paper we define and study what we call the double Catalan monoid.
This monoid is the image of a natural map from the 0-Hecke monoid to the monoid
of binary relations. We show that the double Catalan monoid provides an
algebraization of the (combinatorial) set of 4321-avoiding permutations and
relate its combinatorics to various off-shoots of both the combinatorics of
Catalan numbers and the combinatorics of permutations. In particular, we give
an algebraic interpretation of the first derivative of the Kreweras involution
on Dyck paths, of 4321-avoiding involutions and of recent results of Barnabei
{\em et al.} on admissible pairs of Dyck paths. We compute a presentation and
determine the minimal dimension of an effective representation for the double
Catalan monoid. We also determine the minimal dimension of an effective
representation for the 0-Hecke monoid.
