Given a set of $n$ nodes, how can I count the number of possible functional di-graphs whose biggest connected component contains k node? With a restriction that no node can have an edge point to itself. That is f(x)!= x.
More specifically, given n nodes, I would like to know how many different functional digraphs are there. The biggest connected component(s) in the group is of size k(meaning k nodes). The connected component in this questions is defined in a sense that all edges are replaced by the undirected version. So if a node A connects to a node B and another node C connect to node B, then two nodes are consider connected.
For example, if I am given 4 nodes, then there are $3^4=81$ different types of functional digraph in total. This is because everyone has (4−1)=3 choices(cannot choose itself). Now, considered the size of biggest connected components contained in the graph, there are two types of functional digraphs. A graph can either have two connected components of size 2 or one component of size 4.
There are three different functional di-graph with two size-2 components.
A↔B, C↔D A↔C, B↔D A↔D, C↔B And 78 different functional digraph of size-3 components.
I've been thinking of this for like three days but has no idea how to crack it.
Observation: 1. If you have (n+1) nodes in total, then you can have a group of (k+1) nodes by adding one node to the k-node group in the same question with n nodes. 2. Reference may be two papers "The number of functional digraphs" and "The number of structures of finite relations". But I cannot understand them very well. 3. In general, there should be $(n-1)^n$ different functional digraphs in total.
Appreicate any directions!