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

franktaw at netscape.net franktaw at netscape.net
Tue Dec 29 12:21:35 CET 2009

Looking at your web site, it appears that the size 6 line graph is 
mislabeled.  It should be f-d-b-a-c-e, not f-e-d-c-b-a.

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 by induction - remove the point, find the graph for the 
remainder by induction, and there will be one point that is not 
distinguished from the removed point; join the edge to that point.

I'm also interested in a question that is much less approachable with 
the development path you are following.  That is what happens at the 
"bottom" of each column -- just before it becomes zeros.  Does this 
have a limit?  If so, it would be 1,1,3,...., reading up the columns.  
You would have to go to at least N=14 to get a clue to whether anything 
of this sort is happening (presumably the cases N=15 and N=16 can 
readily be shown to be 1).

One can also ask about the column sums: 1,1,2,10,???

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 

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


More information about the SeqFan mailing list