Cool to hear that people are interested. So far, I've implemented a CatalanCatalog class, which keeps lists of descriptions of Catalan constructions, maps between different constructions, and functions which enumerate various families of constructions. It also maintains a directed graph of which maps have been established, so one can ask for a mapping from one class of objects to another.
At some point, I'm thinking to make a CatalanConstruction class which has a nice interface for which CatalanCatalog is a backend. The user would be able to construct a generic object through any number of means: sage: s = SymmetricGroup(3)([1,3,2]) sage: c = CatalanConstruction(s,'avoid312') sage: b = c.binary_tree() sage: d = CatalanConstruction(b,'binary tree') sage: c == d True sage: d.plot(style='coin stack') ... similarly, one could enumerate Catalan objects: sage: for c in CatalanConstructions(3): ... print c.parentheses(), c.avoid312() ... ()()() () (())() (12) ()(()) (23) (()()) (13) ((())) (123) Part of my problem is that these objects can have quite verbose descriptions. How should they be referenced? I've been using the numbering system that Stanley uses, but it's very clumsy. Also, I can come up with short names like "avoid312", but that's not really good enough, because a number of the constructions are rather hard to summarize in a word or two. Ideas? On Thu, Jul 23, 2009 at 2:58 PM, Franco Saliola<[email protected]> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
