[seqfan] Re: Sequence of 2-rooted trees

[Richard J. Mathar]

For the background: If we count trees with positive integer labels,
there is a triangle

1  
1  1
1  1    1
1  2    2    2
1  2    4    4     3
1  3    6   10     9   6
1  3    9    17   24    20    11 
1  4    12   30   50    63    48      23
1  4    16   44   96   146    164     115   47
1  5   20   67   164  315    437     444   286   106 
1  5   25   91   267  592    1022    1300  1204  719   235 
1  6   30   126  408  1059   2126    3331  3899 3328   1842   551 
1  6   36   163  603  1754   4098    7511 10781 11692  ...    4766
1  7   42   213  856  2805   7368   15619 26294 34844  ...   ...
1  7   49   265 1186  4270   12590  30111 58485 91037  ...   ...

where row s>=1 and column n>=1 shows how many trees with n nodes
exist that have label sum s. See A301739 and A301740 for two columns
already submitted; a bit of background in the PDF file in A301740. 
A036250 are the row sums, A000055 is the diagonal.
[I constructed ordinary generating functions up to column 10, which means,
up to trees with 10 nodes.]

The rooted trees A000081 are the sub-diagonal where s =n+1, which means,
to get a label sum which is one larger than the number of nodes,
that "excess" originates from the node with label 2, and that can
be interpreted as the root of an (otherwise un-rooted) tree.

The second sub-diagonal is 1,2,4,10,24,63,164,444 and has
label excess 2; these trees that have either two nodes
labeled with 2 or one node labeled with 3. If we consider the
trees with two labels equal to 2 as bi-rooted, and the one
with the 3 as rooted, we get the bi-rooted trees by subtracting
the 2nd sub-diagonal from the first sub-diagonal of the triangle:

2-1=1
4-2=2
10-4=6
24-9=15
63-20=43
etc.
The same strategy (of avoiding over-counting by partitioning the excess)
extracts 3-rooted trees from sub-diagonal 3 and so on.

These are the 15 bi-rooted trees (n=5 nodes, 4 edges) I think of:

Linear (6 cases):

X-X-0-0-0
X-0-X-0-0
X-0-0-X-0
X-0-0-0-X
0-X-X-0-0
0-X-0-X-0

Twig at end (7 cases):

  X
  |
X-0-0-0

  0
  |
X-X-0-0

  0
  |
X-0-X-0

  0
  |
X-0-0-X

  0
  |
0-X-0-X

  0
  |
0-X-X-0

  0
  |
0-0-X-X

Star (2 cases)

  X
  |
X-0-0
  |
  0

  0
  |
X-X-0
  |
  0


RJM