|
|
When indexing trees from the root as the number 1, the second vertex must be
always connected to the root. The planar indexed trees can be represented as
the unit matrices in the lower triangular form having always 1 in the first
column and on the diagonal. The other places are filled with 0 till (n - 2)
ones. The unit elements 1(ij) represent vertices on the path from the root
to the vertex j.
There are 2 such matrices (3x3) meeting these demands
|
1 |
0 |
0 |
|
1 |
1 |
0 |
|
1 |
1 |
1 |
It corresponds to the tree 1--2--3. The other possible matrix
|
1 |
0 |
0 |
|
1 |
1 |
0 |
|
1 |
0 |
1 |
corresponds to the tree 3--1--2.
Six matrices (4x4) meeting these demands correspond to 4 indexed linear
chains
1--2--3--4
2--1--3--4
3--1--2--4
4--1--2--3
and to 2 stars with roots 1 and 2.
Since the trees have (n - 1) edges, the planar indexed trees can be indexed
by permutations of (n - 1) symbols, too. Using the alphabet, the string (1,
1, 1) means ab; the string (1, 0, 1) means the permutation ba. The string
(1, 0, 0, 1) means c before both a and b; the string (1, 0, 1, 1) means c
before a, and the string (1, 1, 0, 1) means c before b.
This interpretations connects the planar indexed trees with the Stirling
numbers of the first kind counting the matrices in the lower triangular form ccording to the number of ones in columns.
Counting the number of ones in all columns of all possible matrices, we get the following table
|
n |
1 |
2 |
3 |
4 |
5 |
S |
|
m=1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
2 |
0 |
1 |
0 |
0 |
0 |
1 |
|
3 |
0 |
1 |
1 |
0 |
0 |
2 |
|
4 |
0 |
2 |
3 |
1 |
0 |
6 |
|
5 |
0 |
6 |
11 |
6 |
1 |
24 |
The elements of the table are n!/j. The row sums are
|
n |
1 |
2 |
3 |
4 |
5 |
S |
|
m=1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
2 |
2 |
1 |
0 |
0 |
0 |
3 |
|
3 |
6 |
3 |
2 |
0 |
0 |
11 |
|
4 |
24 |
12 |
8 |
6 |
0 |
50 |
|
5 |
120 |
60 |
40 |
30 |
24 |
274 |
The elements t(ij) of this table are i!/j. Their row sums are
Sm = S i!/j = nSn-1 + (n-1)!.
The rooted trees can be classified according to their diameter. This classification gives the following table
|
Length |
1 |
2 |
3 |
4 |
5 |
S |
|
n=2 |
1 |
0 |
0 |
0 |
0 |
1 |
|
3 |
0 |
2 |
0 |
0 |
0 |
2 |
|
4 |
0 |
2 |
4 |
0 |
0 |
6 |
|
5 |
0 |
2 |
14 |
8 |
0 |
24 |
|
6 |
0 |
2 |
36 |
66 |
16 |
120 |
Its elements t(ij), except the first one, are
t(ij) = (n-l+1)l(i-1,j-1) + (l-1)t(i-1,j)
where l is the length of the parent tree. The first term prolongates the tree, and corresponds to the number of leaves. The second term corresponds to the number of inner vertices of the parent tree. For example, 36 = (6-3+1)x2 + 2x14 = 8 + 28,
66 = ((6-4+1)x14 + 3x8 = 42 + 24, etc..