...

Does this phenomenon account for the fact that it is so often easier to establish that two sets are equipollent than to establish an elegant 1-1 correspondence?

Is the question discussed in the literature on cominatorics?

This is the life blood of a lot of combinatorics.

Well, yes and no. The combinatorial literature is full of bijective arguments, but comparatively devoid of "meta-combinatorial" assertions about the limits of the bijective method. Here's a very simple example of such a limitation: Let S be a set with n elements. Then the assertion that the alternating sum of the binomial coefficients n-choose-k (with k going from 0 to n) vanishes is equivalent to the assertion that there exists a bijection between the subsets of S with even cardinality and the subsets of S with odd cardinality. When n is odd, there is a simple bijection of this kind (namely, the bijection that maps each subset of S to its complement). When n is even, there is no such bijection. Indeed, one can show that singling out a bijection between the even-cardinality and odd-cardinality subsets of a set S is equivalent to singling out one odd-cardinality subset of S. A good way to think about these problems is define a canonical bijection as one that is invariant under relabellings of the underlying set of "points". So, as another example, the set of linear orderings of an n-element set S and the set of invertible maps from S to itself both have n! elements, but there can be no canonical bijection between them, because they are not the same S_n-set (where a G-set is a set together with an action of a group G on that set). This is the perspective taken by the theory of species. If there has been any important recent works on the limits of the bijective method, I'd be extremely interested in knowing about it! Jim Propp