On Thu, Jul 23, 2009 at 8: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.
It would definitely be cool to have this in Sage. There is a sage-combinat conference starting on Saturday, which I will be attending, and I'll make sure to bring this up and ask about interface design. Take care, Franco -- --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
