|
COMMENT
|
The trees in question might also be called unlabeled acyclic connected digraphs, totally acyclic digraphs or acyclic posets.
Comments from Dean Hickerson, May 17 2006: For each directed tree with n nodes, write down the set of pairs (in-degree, out-degree) that occur in the tree. Then count how many different sets you get that way.
For n=3 there are 3 such sets, namely: O-->O-->O {(0,1), (1,0), (1,1)}, O-->O<--O {(0,1), (2,0)}, O<--O-->O {(1,0), (0,2)}.
For n=4 there are 8 directed trees:
O->-O->-O->-O, O->-O->-O-<-O, O-<-O-<-O->-O, O->-O-<-O->-O,
......................
O .... O .... O .... O
| .... | .... | .... |
V .... ^ .... V .... ^
| .... | .... | .... |
O-<--O O->--O O-<--O O->--O
| .... | .... | .... |
^ .... V .... V .... ^
| .... | .... | .... |
O .... O .... O .... O
(see A000238 for the number of them with n nodes). It turns out that all of these give different sets, so a(4)=8.
For n=5 there are 27 directed trees. The following groups of trees give the same set:
O-->O<--O<--O<--O {(0,1), (2,0), (1,1)}
O-->O-->O<--O<--O {(0,1), (2,0), (1,1)}
------------------------------------------------------------
O<--O-->O-->O-->O {(1,0), (0,2), (1,1)}
O<--O<--O-->O-->O {(1,0), (0,2), (1,1)}
------------------------------------------------------------
O-->O<--O<--O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
O-->O-->O<--O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
O-->O<--O-->O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
------------------------------------------------------------
............O
............|
............v
....O<--O<--O-->O {(0,1),.(1,0),.(1,1),.(1,2)}
.............
............O
............^
............|
....O-->O-->O-->O {(0,1),.(1,0),.(1,1),.(1,2)}
------------------------------------------------------------
............O
............^
............|
....O-->O-->O<--O {(0,1),.(1,0),.(1,1),.(2,1)}
.............
............O
............|
............v
....O<--O<--O<--O {(0,1),.(1,0),.(1,1),.(2,1)}
------------------------------------------------------------
There are no other duplications, so a(5)=23, as claimed.
|
