cp's OEIS Frontend

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).

%I A007835 #22 Feb 05 2018 03:20:24
%S A007835 1,1,3,8,21,52,124,284,629,1352,2829,5777,11544
%N 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).
%C A007835 The trees in question might also be called unlabeled acyclic connected digraphs, totally acyclic digraphs or acyclic posets.
%C A007835 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.
%C A007835 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)}.
%C A007835 For n=4 there are 8 directed trees:
%C A007835 O->-O->-O->-O, O->-O->-O-<-O, O-<-O-<-O->-O, O->-O-<-O->-O,
%C A007835 ......................
%C A007835 O .... O .... O .... O
%C A007835 | .... | .... | .... |
%C A007835 V .... ^ .... V .... ^
%C A007835 | .... | .... | .... |
%C A007835 O-<--O O->--O O-<--O O->--O
%C A007835 | .... | .... | .... |
%C A007835 ^ .... V .... V .... ^
%C A007835 | .... | .... | .... |
%C A007835 O .... O .... O .... O
%C A007835 (see A000238 for the number of them with n nodes). It turns out that all of these give different sets, so a(4)=8.
%C A007835 For n=5 there are 27 directed trees. The following groups of trees give the same set:
%C A007835 O-->O<--O<--O<--O {(0,1), (0,1), (2,0), (1,1), (1,1)}
%C A007835 O-->O-->O<--O<--O {(0,1), (0,1), (2,0), (1,1), (1,1)}
%C A007835 ------------------------------------------------------------
%C A007835 O<--O-->O-->O-->O {(1,0), (1,0), (0,2), (1,1), (1,1)}
%C A007835 O<--O<--O-->O-->O {(1,0), (1,0), (0,2), (1,1), (1,1)}
%C A007835 ------------------------------------------------------------
%C A007835 O-->O<--O<--O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
%C A007835 O-->O-->O<--O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
%C A007835 O-->O<--O-->O-->O {(0,1), (1,0), (2,0), (1,1), (0,2)}
%C A007835 ------------------------------------------------------------
%C A007835 ............O
%C A007835 ............|
%C A007835 ............v
%C A007835 ....O<--O<--O-->O {(0,1), (1,0), (1,0), (1,1), (1,2)}
%C A007835 .............
%C A007835 ............O
%C A007835 ............^
%C A007835 ............|
%C A007835 ....O-->O-->O-->O {(0,1), (1,0), (1,0), (1,1), (1,2)}
%C A007835 ------------------------------------------------------------
%C A007835 ............O
%C A007835 ............^
%C A007835 ............|
%C A007835 ....O-->O-->O<--O {(0,1), (0,1), (1,0), (1,1), (2,1)}
%C A007835 .............
%C A007835 ............O
%C A007835 ............|
%C A007835 ............v
%C A007835 ....O<--O<--O<--O {(0,1), (0,1), (1,0), (1,1), (2,1)}
%C A007835 ------------------------------------------------------------
%C A007835 There are no other duplications, so a(5)=23, as claimed.
%H A007835 P. Aubry, <a href="/A007835/a007835.pdf">Letter to N. J. A. Sloane with attachment, Feb. 1994</a>
%H A007835 <a href="/index/Tra#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 (philippe.aubry(AT)oncfs.gouv.fr), Oct 02 1994
%E A007835 Edited by _N. J. A. Sloane_, May 17 2006
%E A007835 a(12)-a(13) from and example in comment clarified by _Sean A. Irvine_, Feb 04 2018