25 January 2009

Existence of bijections?

I have two counting sequences that I know to be the same. That is, I have objects of type A and of type B, which each have a size, and I know that the number of A-objects of size n and the number of B-objects of size n are the same. But I am struggling to find a bijection between the things they count.

Are there results of the form "sure, the two counting sequences are the same, but there's no `natural' bijection between the corresponding sets?" (Obviously bijections will always exist between sets of the same size, so this would of course depend on the definition of the word "natural" -- perhaps a meaning analogous to the category-theoretic one is what I'm looking for, perhaps not.) I've never seen any, but most of the people I know are more interested in finding the bijections than in proving there aren't any.


David Glasser said...

I assume you're familiar with Stanley's Enumerative Combinatorics stuff?

Anonymous said...

The example which immediately comes to mind is the difference between total orderings and self-bijections (aka permutations).

Since this example could well be confusing (since it may certainly seem at first that there is an obvious natural isomorphism between such structures), it might pay off to be formally precise about what exactly we mean here. Following Joyal, who essentially introduced the category-theoretic view on enumerative combinatorics, a species of structure (espece de structure) is defined to be a functor F: P --> Set, where P is the category of finite sets and bijections between them. The idea is that for a finite set S, F(S) should be the set of combinatorial structures of type F you can put on an underlying set S, and if you have a bijection f: S --> T, it should always be possible to transport a structure of type F on the S along the bijection f, to get a corresponding structure on the set T.

A natural bijection between two species of structure F, G is then given the technical category-theoretic meaning, of being a natural isomorphism between the functors F, G.

Under this technical meaning, the species of total order structures is not isomorphic to the species of permutation structures. Consider for example a permutation structure g: S --> S. Given a bijection f: S --> T, the way to transport this to a permutation on T is to form fgf^{-1}. In the case where S = T, we have then the conjugation action of the symmetric group on S on itself. The orbit structure of this action is well known: two permutations lie in the same orbit if they have the same cycle type. Whereas the action on total orders is transitive, that is, there is exactly one orbit. So it is clear that the species here are non-isomorphic.

Please note that the "standard" bijection between total orders and permutations is dependent on a choice. For example, the standard way of setting up a bijection between total orderings on the set {1, 2, ..., n} and permutations thereon is to compare a given ordering against the "usual" ordering, to get a permutation (taking the first element of the usual to the first of the given, etc.). But the usual order amounts to a choice of standard to make the comparison. It is important to be clear on this point, because the apparent "natural" bijection between orders and permutations breaks down if there is no standard order on the given set S (e.g., S = {star, heart, moon, clover}) to effect the comparison -- there is absolutely no natural way of establishing the bijection between orders and permutations on S. (In technical parlance, the set of total orders on S is a torsor over the permutation group, meaning something like a group without an identity, pretty much as an underlying affine space of a vector space is a torsor of the vector space. There is no explicit identification between a torsor and the group acting on it, just as there is no identification between a vector space and the underlying affine space, until one chooses an element which plays the role of "origin" -- but such a choice cannot be considered in any way "natural".)

If this example is still not convincing enough, then here is another which may be more convincing (but is actually closely related): there is a non-natural bijection between the set of "bipointed tree" structures on a set S (that is, a tree structure on S as node set together with a ordered pair of nodes, possibly the same) and the set of endofunctions on S.

Michael Lugo said...


I'm familiar with Joyal's view but hadn't really thought too hard about how it applies here. I'll keep that in mind.

Mitch said...

How do you -know- they are the same? generating function? recurrence? small # of base cases plus proof that a formula has that # of coefficients?

You could read Stanley or Bergeron/Labelle/Leroux (Combinatorial Species and Tree-like Structures) which will give a lot of theory. There are lots more examples in

Benjamin and Quinn, Proofs that Really Count: The Art of Combinatorial Proof

The executive summary is that if you have an identity (either of the gfs or the counting functions themselves) you can often unravel it assigning a combinatorial action to each algebraic operation.

Anonymous said...

The short article "29 is not equal to 29" by R. Bumby http://www.math.rutgers.edu/~bumby/29.pdf may be of some interest, as it poses a situation where two sets with size 29 are argued to be combinatorially distinct.

Anonymous said...

Here's a more elementary answer than the ones above: is there a group G which acts in both settings? For example, if you are counting structures on a set with n elements, then S_n probably acts.

If the number and type of orbits under G in the two sets does not match up, then any bijection must break the G symmetry.

JSE said...

How about: G_n is some sequence of finite groups, and your two sets are the irreducible representations of n and the conjugacy classes of n?

Or, in the same spirit: the elements of (Z/pZ)^n and the elements of Hom((Z/pZ)^n,Z/pZ).

Qiaochu Yuan said...

JSE, you seem to be talking about the general principle that a finite-dimensional vector space is non-canonically isomorphic to its dual.

I wonder if there's a way to think about total orderings and bijections like this. Bijections correspond to elements of the linear group over F_1, whereas total orderings correspond to complete flags...

Anonymous said...

Nice blog as for me. I'd like to read something more about that topic. Thanx for posting that data.
Sexy Lady
Asian Escort

Anonymous said...

It is very interesting for me to read that blog. Thank author for it. I like such themes and everything that is connected to this matter. I definitely want to read a bit more soon.

Anonymous said...

nellai welcoming frege herbal sidebars habermas taksal maximise instinct browsers creations
servimundos melifermuly

Anonymous said...

deposit responses both adequate cmis candidates abdominal burns hindleyleeds cameraman stephen
servimundos melifermuly