Richard Stanley currently lists 172 combinatorial interpretations of the Catalan numbers. I've been doing some research on Coxeter groups this summer, and we recently found that a class of permutations in S_n which are counted by the Catalan numbers. Turns out, the permutations are just the 321-avoiding permutations. A research partner, Matt Macauley noted that when one finds objects counted by the Catalan numbers, that it can be interesting to see what other objects they might correspond to.
In particular, we've got a subset of the 321-avoiding permutations
that we want to investigate. If there's a nice bijection between
321-avoiding permutations, and say, Dyck paths, we'd like to look at
the Dyck paths which correspond to this special subset. So, I've
started going down Stanley's list and hacking up as many bijections as
I can devise between the objects he's listed. At the present, I can
generate the following given, say, a Dyck word (one can generate these
in Sage), and draw nice pictures of them all. Further, almost all of
them are strongly connected -- given almost any object below, I can
create any of the others. (though my constructions are bijective, I
haven't coded both ways for a couple of them)
These reference Stanley's numbering scheme, see [1] and [2]
(c) binary trees on n vertices
(h) lattice paths from (0,0) to (n,n) below x=y
(i) Dyck paths from (0,0) to (n,0) above x=0
(o) non-crossing matchings of [2n]
(r) valid strings of parentheses (description in text differs by '('
<-> 1, ')' <-> -1)
(ff) 231-avoiding permutations (hah -- but I don't have 321-avoiding
permutations yet -- I found these by a lucky guess)
(pp) non-crossing partitions of [n]
(tt) non-crossing partitions of [2n+1] into n+1 parts with
nonconsecutive entries
(hhh) stacks of coins
(z^4) non-nesting matchings of [2n]
I'm mostly doing this for research and for pleasure, but since I'm
doing the research with a few partners, the code is readable. I'm
wondering: is there sufficient interest for this to be added to Sage?
If I manage to construct even a quarter of the bijections listed, it
will be a rather large amount of code. I'd like some input from the
combinat people as to what sort of interface would be appropriate.
Thanks,
--tom
Note: the attached is a sample image of my current constructions --
the binary trees are particularly ugly, but they're drawn that way to
make the bijection between (r) and (c) clear. Also, the objects look
much better when plotted on their own, but I couldn't figure out how
to get a graphics_array to fix the aspect ratio for the individual
images.
[1] http://math.mit.edu/~rstan/ec/catalan.pdf
[2] http://math.mit.edu/~rstan/ec/catadd.pdf
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
<<attachment: catalan.png>>
