What is A007835?

[Frank Ruskey]

I would caution against using "oriented tree" for this
concept since various authors (e.g., Knuth) use
oriented tree to mean "rooted tree".  Other terms
that have been used in the literature for the
tree-with-edges-oriented-in-various-directions concept
include "acyclic poset" (note: different than "cycle-free poset")
and "totally acyclic digraph".
I would guess that "signed tree" (in the spirit of
signed graphs) has also been used, but I don't have a reference.
In the poset case, the meaning is that the Hasse diagram
regarded as a graph (with directions ignored) is acyclic
(and connected is also usually assumed). 
Cheers,
-Frank

On Thu, 18 May 2006, 
Brendan McKay wrote:

> Can't help you with the meaning of this sequence, but I disagree
> with you on terminology.  In the graph theory literature, "directed
> trees" usually have all their edges oriented towards a single
> vertices, or all oriented away from a single vertex.  I think this
> is a lot more common than using "oriented tree" for this meaning.
> I would call a tree with edges oriented in arbitrary directions
> an "oriented tree" as that is consistent with the very common
> "oriented graph" - but of course a few words of clarification
> can never hurt.
>
> Brendan.
>
> * franktaw at netscape.net <franktaw at netscape.net> [060518 09:39]:
>> The entry for this sequence is:
>>
>> %I A007835
>> %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.
>> %H A007835 <a href="http://www.research.att.com/~njas/sequences/Sindx_Tra.html#trees">Index entries for sequences related to trees</a>
>> %Y A007835 Cf. A000238.
>> %K A007835 nonn,more
>> %O A007835 1,3
>> %A A007835 Philippe Aubry (aubry(AT)xlstat.com)
>>
>> I have not been able to make sense out of this.
>>
>> I was able to determine that by "oriented tree" is meant a directed graph (digraph) that, when the directions of the edges are erased, is a (free) tree.  (An unfortunate bit of nomenclature, that, since "oriented tree" is also used as a synonym for "rooted tree" - such as Knuth, The Art of Computer Programming.  "Directed tree" would have been a much better choice.)
>>
>> However that may be, there are 3 of these "oriented trees" with 3 nodes:
>>
>> O-->O-->O, O-->O<--O, and O<--O-->O.
>>
>> The first of these has (in-degree, out-degree) pairs (0,1), (1,1), and (1,0); the second has (0,1) twice and (2,0), and the third has (1,0) twice and (0,2).  If we simply take the set of all such unordered pairs, that would have 3 elements: {(0,1), (0,2), (1,1)}.  However, then for n=4, we get only {(0,1), (0,2), (1,1), (0,3), (1,2)}, for 5, not 8.  (And in general, we would get A024206.)  I don't see any reasonable way to get a larger value for a(4) that does not make a(3) be at least 4.
>>
>> Franklin T. Adams-Watters
>> ___________________________________________________
>> Try the New Netscape Mail Today!
>> Virtually Spam-Free | More Storage | Import Your Contact List
>> http://mail.netscape.com
>

-- 
----------------------
Frank Ruskey         e-mail: (last_name)(AT)cs(DOT)uvic(DOT)ca
Dept. of Computer Science        fax:    250-721-7292
University of Victoria           office: 250-721-7232
Victoria, B.C. V8W 3P6 CANADA    WWW: http://www.cs.uvic.ca/~(last_name)