This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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, 1, 3, 8, 21, 52, 124, 284, 629, 1352, 2829, 5777, 11544 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 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 CROSSREFS Cf. A000238. Sequence in context: A322059 A259714 A096770 * A152086 A014396 A170881 Adjacent sequences:  A007832 A007833 A007834 * A007836 A007837 A007838 KEYWORD nonn,more AUTHOR Philippe Aubry (philippe.aubry(AT)oncfs.gouv.fr), Oct 02 1994 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 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 21 00:17 EDT 2019. Contains 327252 sequences. (Running on oeis4.)