You could make the ultimate "proof-without-words" submission! I think this is cool, and although I am not a combinatorics person at all it seems reasonable as an addition to sage. I think it could underpin a really fantastic @interact.
-Marshall On Jul 23, 1:20 am, Tom Boothby <[email protected]> wrote: > 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 > > catalan.png > 26KViewDownload --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
