[seqfan] Re: Help wanted on A005646 connection to A000055

[franktaw at netscape.net]

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/