On Thu, Jul 12, 2012 at 7:16 AM, Marc LeBrun <mlb@well.com> wrote:
="Mike Stay" <metaweta@gmail.com> Composition is associative, so I'd think you'd have a list rather than a tree. Can you expand a bit on what you're looking for?
I guess I'm seeking the "Official Name" for the tree data-structure analog that reflects the partitions vs. compositions distinction. Basically,
A Tree is either a Leaf or an ordered sequence of sub-Trees.
An X is either a Leaf or an unordered set of sub-X's.
What do you call an X?
="Gareth McCaughan" <gareth.mccaughan@pobox.com> "Unordered tree"?
That's reasonable, but I don't want to coin a new term if there's already an existing one--which I suspect there may be, though for some reason I can't seem to recall what it is.
As an "application", there's that nice categorical correspondence of 7-tuples of trees to trees, so what is the analog for X's--and so on.
From a generating function point of view, the ordinary generating function for a structure is really the exponential generating function for the structure with a choice of order.
So the unordered tree would be a solution of T(a) = 1/2 T(a)^2 + a, since permuting the order of the trees is a symmetry. When you have an action of a group G (like a permutation) on a set X, you can form the groupoid X//G by taking the elements of the groupoid to be the elements of X and the arrows out of x in X to be x -> gx for each g in G. The cardinality of a groupoid H is |H| = sum_[x] 1/Aut(x) (where [x] means the sum is taken over isomorphism classes) so |X//G| = |X| / |G|. Taking a=1, we get T = T^2/2 + 1 and get 1 +/- i as solutions in the complex plane. (1+i)^9 = 16(1+i), so there are nine unordered trees and four bits in one unordered tree. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com