What is A007835?

[Dean Hickerson]

Mostly to Franklin T. Adams-Watters:

> The entry for this sequence is:
...
> %S A007835 1,1,3,8,21,52,124,284,629,1352,2829
> %N A007835 Number of unordered sets of pairs (in-degree, out-degree) for nodes of oriented  trees.
...
> %O A007835 1,3
...
> I have not been able to make sense out of this.

I think this is what is meant:  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.

You showed that 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.  (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.  I haven't checked all of them, but
here are some groups of trees that 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)}

If there are no other duplications, then a(5)=23, as claimed.

Dean Hickerson
dean at math.ucdavis.edu