Help := proc ()
  print (`DTrees(i,n)`);
end:


# DTrees(i,n) returns all directed trees rooted at i with n vertices.
DTrees := proc (i, n)

  if n = 1 then
    if i = 1 then
      return {{}};
    else
      return {};
    fi;
  fi;
  return dfs_DTrees ([i], {seq(j, j=1..n)} minus {i}, 1, n, {});
end:


# dfs_DTrees(S, T, ts, n, edges) return all ways to complete a partially
# constructed tree:
# S -> list of vertices in the partial tree willing to accept new edges
# T -> set of vertices to be added to the tree
# ts -> the smallest vertex allowed to be connected to S[1]
# n -> the total number of vertices
# edges -> set of edges in the partial tree

dfs_DTrees := proc (S, T, ts, n, edges)
  local j, R;

# in case no vertex is left, we have a tree:

  if nops(T) = 0 then
    return {edges};
  fi;

# if none of the vertices in the partial tree accept new connection,
# (and by assumption T is not empty), we are stuck:

  if nops(S) = 0 then
    return {};
  fi;

# enumerate all possible trees:

  R := {};

# connect S[1] to a vertex from T with label greater or equal to ts,
# then use dfs_DTrees to find out all trees satisfying current partial tree.

  for j from 1 to nops(T) do
    if T[j] >= ts then
      R := R union dfs_DTrees ([op(S), T[j]], 
                               T minus {T[j]}, 
                               T[j]+1, 
                               n, 
                               edges union {[S[1], T[j]]}
			      );
    fi;
  od;
 
# another possibility is that nobody from T wants to be connected to S[1],
# then we proceed to find friends for S[2].

  R := R union dfs_DTrees ([op(2..nops(S), S)], T, 1, n, edges);

  return R;
end: