A007835 Number of unordered sets of pairs (in-degree, out-degree) for nodes of directed trees on n unlabeled nodes (the edges are directed in arbitrary directions, the tree is unrooted).

1, 1, 3, 8, 21, 52, 124, 284, 629, 1352, 2829, 5777, 11544

Offset: 1

Author

Philippe Aubry (philippe.aubry(AT)oncfs.gouv.fr), Oct 02 1994

Keywords

• nonn
• more

Comments

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), (0,1), (2,0), (1,1), (1,1)}

O-->O-->O<--O<--O {(0,1), (0,1), (2,0), (1,1), (1,1)}

------------------------------------------------------------

O<--O-->O-->O-->O {(1,0), (1,0), (0,2), (1,1), (1,1)}

O<--O<--O-->O-->O {(1,0), (1,0), (0,2), (1,1), (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,0), (1,1), (1,2)}

.............

............O

............^

............|

....O-->O-->O-->O {(0,1), (1,0), (1,0), (1,1), (1,2)}

------------------------------------------------------------

............O

............^

............|

....O-->O-->O<--O {(0,1), (0,1), (1,0), (1,1), (2,1)}

.............

............O

............|

............v

....O<--O<--O<--O {(0,1), (0,1), (1,0), (1,1), (2,1)}

------------------------------------------------------------

There are no other duplications, so a(5)=23, as claimed.

Links

• P. Aubry, Letter to N. J. A. Sloane with attachment, Feb. 1994
• Index entries for sequences related to trees

Crossrefs

Cf. A000238.

Extensions

Edited by N. J. A. Sloane, May 17 2006

a(12)-a(13) from and example in comment clarified by Sean A. Irvine, Feb 04 2018