[seqfan] Re: Help wanted on A005646 connection to A000055
franktaw at netscape.net
franktaw at netscape.net
Wed Dec 30 00:00:57 CET 2009
I can now prove that the diagonal is indeed A000055.
Clearly each tree gives rise to a classification with the desired
property, with each edge being mapped to a binary partition
distinguishing between points in the two components created when the
edge is removed. We need to show that any such classification arises
from such a tree.
Given a classification of N points with R = N-1 binary partitions,
choose any of the binary partitions. There must be at least one pair
of points distinguished only by this binary partition; otherwise it is
not essential. Look at the classification resulting when this binary
partition is removed and each such pair is identified in the remainder.
(These must be discrete pairs; the relation is transitive, so if two
pairs had a point in common, they would be a triple, which could not be
distinguished by a single binary partition.) Clearly, the result of
doing this is again a classification, without regard to the R = N-1
condition. With R = N-1, if there was more than one pair uniquely
distinguished by this binary partition, the result would be a
classification with R >= N, which is impossible; hence there is only
one uniquely distinguished pair.
Now we have a classification with N-1 objects and R-1 binary
partitions, so by induction it arises from a tree. The tree for the
original classification comes from separating the point that was
combined. The neighbors of the combined point must join to whichever
of the original points they are classified with in the selected binary
partition: the binary partition corresponding to their joining edge is
the only one distinguishing them from that point, while connecting to
the other point would create another distinction. Likewise, there is
one binary partition forcing each more distant point into the
corresponding part of the selected binary partition. We have proved
that this binary partition is the one generated by the selected edge of
the tree, and by induction it follows that the classification is
generated by the tree.
Q.E.D.
Franklin T. Adams-Watters
P.S. I sent the sub-diagonal 1,3,17,74,358,1631,7563 to superseeker; it
found nothing.
-----Original Message-----
From: franktaw at netscape.net
...
It feels like I can almost prove this, but the final result eludes me.
It will suffice to prove that there must always (for R = N-1 > 0) be
one classification that distinguishes a single point. The result then
follows ...
...
Franklin T. Adams-Watters
-----Original Message-----
From: Robert Munafo <mrob27 at gmail.com>
Andrew Weimholt and I have been working on A005646. Franklin T.
Adams-Watters suggested the importance of the triangle:
N=1 1
N=2 0 1
N=3 0 0 1
N=4 0 0 1 2
N=5 0 0 0 3 3
N=6 0 0 0 3 17 6
N=7 0 0 0 1 36 74 11
N=8 0 0 0 1 60 573 358 23
N=9 0 0 0 0 56 2802 7311 1631 47
N=10 0 0 0 0 50 10087 107938 83170 7563 106
>I've copied in row 10 from a later post - FTAW.
The main diagonal suggests a relation to sequence A000055, unlabaled
unrooted trees.
I am starting to convince myself such a connection is real; detals and
full examples through N=6 are at
http://mrob.com/pub/math/seq-a005646.html#trees
A graph edge corresponds to a binary partition, and each node is one of
the types in the classification. Each edge connects two subgraphs, and
the corresponding partition divides the nodes in the same way the graph
gets divided if that edge is removed.
Can anyone help me prove or disprove this?
--
Robert Munafo -- mrob.com
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list