[math-fun] Tree terminology
Speaking of terminology, I¹m drawing a blank: Tree is to Composition AS X is to Partition X == ...? For example the following are distinct Trees, but equivalent X¹s: O O / \ / \ O O O O / \ \ / / \ O O O O O O Thanks! --MLB
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? On Wed, Jul 11, 2012 at 10:43 PM, Marc LeBrun <mlb@well.com> wrote:
Speaking of terminology, I¹m drawing a blank:
Tree is to Composition AS X is to Partition
X == ...?
For example the following are distinct Trees, but equivalent X¹s:
O O / \ / \ O O O O / \ \ / / \ O O O O O O
Thanks! --MLB
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
="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.
Isn't that just a set (assuming the foundation axiom). --ms On 7/12/2012 10:16 AM, Marc LeBrun 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
To mathematicians, X = Tree. The thing that cares what order the children are in is called a "planar tree" instead. Computer scientists don't know that things come in "unordered", so they dropped the word "planar" and just call the ordered things trees. --Michael On Thu, Jul 12, 2012 at 10: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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Surely you're not serious when you say "computer scientists don't know that things come in "unordered"? Are you saying that it was invading mathematicians that were responsible for such data types as dictionaries and sets in various programming languages from PostScript to Python? And do you not count as computer scientists those who work on graph algorithms? --ms On 7/12/2012 10:49 AM, Michael Kleber wrote:
To mathematicians, X = Tree. The thing that cares what order the children are in is called a "planar tree" instead.
Computer scientists don't know that things come in "unordered", so they dropped the word "planar" and just call the ordered things trees.
--Michael
On Thu, Jul 12, 2012 at 10: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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
participants (5)
-
Gareth McCaughan -
Marc LeBrun -
Michael Kleber -
Mike Speciner -
Mike Stay