I am attempting to determine the number of distinct possible directed graphs (conversations) with N nodes (statements) colored with P colors (P people conversing.) (This seems to be the number of list-improper colorings, but I may have the terms confused.)
Question: How many distinct P-colorings exist for N nodes, over all connected directed acyclic graphs with N nodes?
BONUS: How many distinct P-colorings exist if the maximum out-degree is 2?
Alternatively, if it is easier, how many distinct conversations (trees plus distinct colorings) exist given N total statements, for up to N colors, with out-degree no greater than 2? An algorithm to generate and count the possible cases would also suffice, but an algebraic expression would be far nicer.
Background / Explanation: A conversation, in this case, is a set of nodes representing statements, where each statement is made by a person. The person making the statement is represented by coloring the node, and each person can respond to any other statement, including their own. The tree is connected, so that all but the root statement is a response (edge,) to another statement, and statements can have more than one response. (In the specific context I'm looking at, statements cannot respond to more than 2 other statements, but I can probably ignore this for the sake of generality.)
In this framing, the statement contents do not matter, but the speaker does, up to isomorphism. For two nodes, for example, either A speaks and B responds (A-B), or A speaks and A responds (A-A). B speaking and A responding, is the same as A speaking and B responding, with roles reversed (a recoloring,) so it is not distinct. I am looking for the number of unlabeled colorings for each different graph.
Clearly, all distinct tree structures are different, so the final answer is not just unlabeled colorings on a single graph. We can count the number for graphs of size 2 and 3 as an example, with letters representing different colors.
Size 2 has 2 possible graphs: A-A, and A-B.
Restricting ourselves to allowing statements to reply to only one other statement, size 3 has 2 graphs with one color, A<-AA and A<-A<-A. In this list, the conversation A<-A<-A is different than A<-AA, which could also be written A->A<-A. In the second case, A responds to his first statement twice, instead of the third statement being a response to the second. There are also 5 distinct graphs with 2 colors, A<-AB, A<-BB, A<-A<-B, A<-B<-A, A<-B<-B. Notice that B<-A<-B is a recoloring of A<-B<-A, so is not a different conversation type. Finally, there are another 2 graphs with 3 colors, A<-BC, A<-B<-C. This gives a total of 9 graphs. If we change the reply-assumption to allow responses to more than one statement, we also have AA<-A, AB<-A, AA<-B, and AB<-C, giving 3, 7, and 3 graphs for a total of 13.
Size 4, however, begins to get far larger, (and harder to represent graphically with text.) Even with only one color and replying to a single statement, we have 4 graphs, A<-AAA, A<-AA<-A, A<-A<-AA, and A<-A<-A<-A. (Where a single statement replies to more than one, because there is only one color the graphs are identical. This is no longer true with multiple colors, where there are 2 different graphs A<-AB<-A, since the final node could be responding to either A or B, i.e. only one of either A<-A<-A or A<-B<-A is a subgraph, and these are different conversations.