Some classes for objects that can be counted by the catalan numbers.
What would be a good place to start to look for the format i would
need to follow.
> Some classes for objects that can be counted by the catalan numbers. > What would be a good place to start to look for the format i would > need to follow.
You should contact the author and guys in cc in this ticket to see what has already been done. Since I'm not sure they are following this mailing list, writing directly on the ticket (after getting a trac account) is probably the best way.
it would be great if you worked on that. some of it has already be done in the patch trac_11571_catalan_objects-nm.patch
the files are in sage/combinat/catalan
it has been written by Nevena Milojkovic who was a student in Marne-la-Vallee. She didn't stay and is no longer working on it, But I still have her email if you need it. I'm not sure exactly what she has developed and how far she went. I'm not even sure everything she did is into sage-combinat. But you can have a look, I'm pretty sure she implemented most of the bijection algorithms.
>> Some classes for objects that can be counted by the catalan numbers. >> What would be a good place to start to look for the format i would >> need to follow.
> You should contact the author and guys in cc in this ticket to see what has > already been done. Since I'm not sure they are following this mailing list, > writing directly on the ticket (after getting a trac account) is probably the > best way.
> Cheers,
> Florent
> -- > You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to sage-combinat-devel+unsubscribe@googlegroups.com. > For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
> it would be great if you worked on that. some of it has already be > done in the patch trac_11571_catalan_objects-nm.patch
if I see it right, there are currently implemented
- Dyck paths - Motzkin paths (which are not really counted by Catalan)
in this folder. I don't know how much people work on getting "classical" Catalan combinatorics into Sage - is there more than Dyck paths currently?
In the past, I implemented various objects that are counted by Coxeter-Catalan numbers which are numbers associated to finite reflection groups such that we get back the classical Catalan numbers when looking at the symmetric group. See e.g. Section 1.1. in http://arxiv.org/abs/math/0611106.
Here is a not necessarily exhaustive list (with the classical corresponding object in brackets).
- facets in the cluster complex (triangulations of a multi-gon), - Coxeter-sortable elements (231-pattern avoiding permutations), - noncrossing partitions (noncrossing set partitions), - facets in a certain "subword complex" (triangulations), - antichains in the root poset (Dyck paths), - vertices of the generalized associahedron
I have also implementations of bijections between all of them except antichains in the root poset. The reason is that all the others are naturally connected in a type-free way, while antichains in the root poset were connected in http://arxiv.org/abs/1101.1277, but I have not had the time to implement this bijection (which is inductively defined in a subtle way and thus not easy to implement).
I will be thinking about that in the next days and if people agree I will turn #11571 into an overview patch on what (Coxeter-)Catalan objects and bijections we have.
I would also be very interested in people working on the classical situation to get objects like triangulations into sage (+1 for nice drawings as well, see my macros in tikz for that, http://homepage.univie.ac.at/christian.stump/code.html). If we have (or if we are going to have) any objects implemented, I will be happy to provide bijections from the Coxeter-Catalan setting to the concrete implementation for the symmetric group.
If you need any help on how to work on that, let me know!
I actually started a project like this a while back. I made a catalog which accepts generators and mappings, and constructs mappings between objects types you've connected. It does some plotting, too.
One weird thing about it is that I use the labels from Richard Stanley's catalog of objects.
>> it would be great if you worked on that. some of it has already be >> done in the patch trac_11571_catalan_objects-nm.patch
> if I see it right, there are currently implemented
> - Dyck paths > - Motzkin paths (which are not really counted by Catalan)
> in this folder. I don't know how much people work on getting > "classical" Catalan combinatorics into Sage - is there more than Dyck > paths currently?
> In the past, I implemented various objects that are counted by > Coxeter-Catalan numbers which are numbers associated to finite > reflection groups such that we get back the classical Catalan numbers > when looking at the symmetric group. See e.g. Section 1.1. in > http://arxiv.org/abs/math/0611106.
> Here is a not necessarily exhaustive list (with the classical > corresponding object in brackets).
> - facets in the cluster complex (triangulations of a multi-gon), > - Coxeter-sortable elements (231-pattern avoiding permutations), > - noncrossing partitions (noncrossing set partitions), > - facets in a certain "subword complex" (triangulations), > - antichains in the root poset (Dyck paths), > - vertices of the generalized associahedron
> I have also implementations of bijections between all of them except > antichains in the root poset. The reason is that all the others are > naturally connected in a type-free way, while antichains in the root > poset were connected in http://arxiv.org/abs/1101.1277, but I have not > had the time to implement this bijection (which is inductively defined > in a subtle way and thus not easy to implement).
> I will be thinking about that in the next days and if people agree I > will turn #11571 into an overview patch on what (Coxeter-)Catalan > objects and bijections we have.
> I would also be very interested in people working on the classical > situation to get objects like triangulations into sage (+1 for nice > drawings as well, see my macros in tikz for that, > http://homepage.univie.ac.at/christian.stump/code.html). If we have > (or if we are going to have) any objects implemented, I will be happy > to provide bijections from the Coxeter-Catalan setting to the concrete > implementation for the symmetric group.
> If you need any help on how to work on that, let me know!
> Best, Christian
> -- > You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to sage-combinat-devel+unsubscribe@googlegroups.com. > For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
> -- > You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to sage-combinat-devel+unsubscribe@googlegroups.com. > For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
> Thanks, I can see it now. I was also able to call
> sage: CatCat > <__main__.CatalanCatalog instance at 0x10d01be60>
> on 4.7.2, but the bijections seem to be missing,
> sage: CatCat.map('r','o') > ValueError: Can't map objects of type r into objects of type o
> and also the graph CatCat._graph didn't have any edges. However, on > 4.5.beta6, CatCat wasn't even present anymore.
> It would be great if I could get your code running to enhance it with > further objects, and build a similar catalog for Coxeter-Catalan > objects.
> btw: I wasn't aware of this way to collects objects and bijections; is > this considered the standard way to catalog objects?
> Thanks, Christian
> -- > You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to sage-combinat-devel+unsubscribe@googlegroups.com. > For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
> Christian, this is far from standard. It's fairly discombobulated > scratch work. The objects aren't even classes.
my last reply was too fast, sorry. Now as I look at the actual code, I see what you are doing... Nonetheless, I find it a nice idea to gather Catalan objects and their bijections, as people are apparently looking for that!
What about implementing the objects as classes in the folder combinat/catalan (maybe with some identifications by "canonical bijections", like i = h = zzzz = r = hhh), and then making them available as
CatalanObjects.YourCatalanObject
like in
Posets.BooleanLattice
(to not pollute the global name space too much), and also provide bijections, maybe in
CatalanObjects.Bijections.YourFavoriteBijection
(these are, of course, not unique, so we must give them names to distinguish, like "reverse" and "upside-down" to get from \sigma-avoiding permutations to reverse(\sigma)-avoiding permutations for \sigma \in S_3.)
Better or other ideas, suggestions?
@vivace: are you interested in working/collaborating on that? was this somehow what you thought of?
i would be interested. I had it in mind to focus on the recursive structure of the Catalan objects( objects that can be counted via catalan numbers).
C_{n+1} = \sum_{i=0}^{n}C_{n-i}C_{i}
when defining a new catalan object we would just need to specify the recursive structure. This way we might not have to deal with specific bijections....but that was just my initial idea...i dont know :)
On Mon, Mar 26, 2012 at 9:54 AM, Christian Stump <christian.st...@gmail.com>wrote:
> > Christian, this is far from standard. It's fairly discombobulated > > scratch work. The objects aren't even classes.
> my last reply was too fast, sorry. Now as I look at the actual code, I > see what you are doing... Nonetheless, I find it a nice idea to gather > Catalan objects and their bijections, as people are apparently looking > for that!
> What about implementing the objects as classes in the folder > combinat/catalan (maybe with some identifications by "canonical > bijections", like i = h = zzzz = r = hhh), and then making them > available as
> CatalanObjects.YourCatalanObject
> like in
> Posets.BooleanLattice
> (to not pollute the global name space too much), and also provide > bijections, maybe in
> CatalanObjects.Bijections.YourFavoriteBijection
> (these are, of course, not unique, so we must give them names to > distinguish, like "reverse" and "upside-down" to get from > \sigma-avoiding permutations to reverse(\sigma)-avoiding permutations > for \sigma \in S_3.)
> Better or other ideas, suggestions?
> @vivace: are you interested in working/collaborating on that? was this > somehow what you thought of?
> cheers, Christian
> -- > You received this message because you are subscribed to the Google Groups > "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to > sage-combinat-devel+unsubscribe@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sage-combinat-devel?hl=en.
Yes, this was suggested to me after I'd abandoned the catalog I posted. I'm fairly sure that most, if not all of my bijections follow directly from the recursive structure of Catalan objects.
On Mon, Mar 26, 2012 at 10:25 AM, matthew Drescher <knav...@gmail.com> wrote: > i would be interested. I had it in mind to focus on the recursive structure > of the Catalan objects( objects that can be counted via catalan numbers).
> C_{n+1} = \sum_{i=0}^{n}C_{n-i}C_{i}
> when defining a new catalan object we would just need to specify the > recursive structure. This way we might not have to deal with specific > bijections....but that was just my initial idea...i dont know :)
> On Mon, Mar 26, 2012 at 9:54 AM, Christian Stump <christian.st...@gmail.com> > wrote:
>> > Christian, this is far from standard. It's fairly discombobulated >> > scratch work. The objects aren't even classes.
>> my last reply was too fast, sorry. Now as I look at the actual code, I >> see what you are doing... Nonetheless, I find it a nice idea to gather >> Catalan objects and their bijections, as people are apparently looking >> for that!
>> What about implementing the objects as classes in the folder >> combinat/catalan (maybe with some identifications by "canonical >> bijections", like i = h = zzzz = r = hhh), and then making them >> available as
>> CatalanObjects.YourCatalanObject
>> like in
>> Posets.BooleanLattice
>> (to not pollute the global name space too much), and also provide >> bijections, maybe in
>> (these are, of course, not unique, so we must give them names to >> distinguish, like "reverse" and "upside-down" to get from >> \sigma-avoiding permutations to reverse(\sigma)-avoiding permutations >> for \sigma \in S_3.)
>> Better or other ideas, suggestions?
>> @vivace: are you interested in working/collaborating on that? was this >> somehow what you thought of?
>> cheers, Christian
>> -- >> You received this message because you are subscribed to the Google Groups >> "sage-combinat-devel" group. >> To post to this group, send email to sage-combinat-devel@googlegroups.com. >> To unsubscribe from this group, send email to >> sage-combinat-devel+unsubscribe@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/sage-combinat-devel?hl=en.
> -- > You received this message because you are subscribed to the Google Groups > "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to > sage-combinat-devel+unsubscribe@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sage-combinat-devel?hl=en.
