[seqfan] Re: Sequence of 2rooted trees
Richard J. Mathar
mathar at mpiahd.mpg.de
Mon Apr 30 17:25:41 CEST 2018
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 subdiagonal 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 unrooted) tree.
The second subdiagonal 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 birooted, and the one
with the 3 as rooted, we get the birooted trees by subtracting
the 2nd subdiagonal from the first subdiagonal of the triangle:
21=1
42=2
104=6
249=15
6320=43
etc.
The same strategy (of avoiding overcounting by partitioning the excess)
extracts 3rooted trees from subdiagonal 3 and so on.
These are the 15 birooted trees (n=5 nodes, 4 edges) I think of:
Linear (6 cases):
XX000
X0X00
X00X0
X000X
0XX00
0X0X0
Twig at end (7 cases):
X

X000
0

XX00
0

X0X0
0

X00X
0

0X0X
0

0XX0
0

00XX
Star (2 cases)
X

X00

0
0

XX0

0
RJM
More information about the SeqFan
mailing list