Suppose I have two multisets, $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. We can construct a (random) bipartite multigraph with the vertex bipartition $\text{set}(A) \cup \text{set}(B)$ by the following process:

• start with the null graph on vertex multiset $A \cup B$,
• pick a (random) permutation $\alpha$ of $\{1,2,\ldots,n\}$,
• draw edges from $a_i$ to $b_{\alpha(i)}$ for all $i \in \{1,2,\ldots,n\}$,
• identify vertices $a_i$ and $a_j$ whenever $a_i=a_j$, and similarly, identify vertices $b_i$ and $b_j$ whenever $b_i=b_j$.

This could be described as a version of the configuration model for bipartite graphs (although, usually the configuration model restarts if parallel edges occur, and I don't want to do that).

For example, if $A=\{1,2,2,2,3\}$ and $B=\{4,4,5,5,5\}$, and $\alpha=\text{id}$ then we generate the multigraph with bipartition $\{1,2,3\} \cup \{4,5\}$ and edge multiset $\{14,24,25,25,35\}$. We could also have generated the same multigraph with $\alpha=(12)$, and $\alpha=(23)$ and a variety of other ways.

Question: Given a bipartite multigraph, in how many ways could it have been generated by the above process?

A related problem, the enumeration of contingency tables, is #P-complete (this gives the number of distinct bipartite graphs that could have arisen). See: M. Dyer, R. Kannan, J. Mount, Sampling Contingency Tables, Random Structures & Algorithms 10 (1997), 487–506.

Presumably, the problem I mention above is "hard" (although, feel free to prove me wrong!), which suggests an algorithmic approach is required to answer the question in general.

This leads me to the sub-questions:

Sub-question: Is there an efficient way to compute these numbers (other than some kind of backtracking algorithm)?

and

Sub-question: Does there exist a graph whose automorphisms correspond (naturally) to the different ways of generating a given bipartite multigraph by the above method?

If it is possible to do the above, then we could use e.g. nauty to compute it easily.

(Note: This question is "the other side of the coin" of a math.SE question: What is the number of bijections between two multisets? However, I tried to make this question self-contained.)

Suppose I have two multisets, $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. We can construct a (random) bipartite multigraph with the vertex bipartition $\text{set}(A) \cup \text{set}(B)$ by the following process:

• start with the null graph on vertex multiset $A \cup B$,
• pick a (random) permutation $\alpha$ of $\{1,2,\ldots,n\}$,
• draw edges from $a_i$ to $b_{\alpha(i)}$ for all $i \in \{1,2,\ldots,n\}$,
• identify vertices $a_i$ and $a_j$ whenever $a_i=a_j$, and similarly, identify vertices $b_i$ and $b_j$ whenever $b_i=b_j$.

This could be described as a version of the configuration model for bipartite graphs (although, usually the configuration model restarts if parallel edges occur, and I don't want to do that).

For example, if $A=\{1,2,2,2,3\}$ and $B=\{4,4,5,5,5\}$, and $\alpha=\text{id}$ then we generate the multigraph with bipartition $\{1,2,3\} \cup \{4,5\}$ and edge multiset $\{14,24,25,25,35\}$. We could also have generated the same multigraph with $\alpha=(12)$, and $\alpha=(23)$ and a variety of other ways.

Question: Given a bipartite multigraph, in how many ways could it have been generated by the above process?

A related problem, the enumeration of contingency tables, is #P-complete (this gives the number of distinct bipartite graphs that could have arisen). See: M. Dyer, R. Kannan, J. Mount, Sampling Contingency Tables, Random Structures & Algorithms 10 (1997), 487–506.

Presumably, the problem I mention above is "hard" (although, feel free to prove me wrong!), which suggests an algorithmic approach is required to answer the question in general.

This leads me to the sub-questions:

Sub-question: Is there an efficient way to compute these numbers (other than some kind of backtracking algorithm)?

and

Sub-question: Does there exist a graph whose automorphisms correspond (naturally) to the different ways of generating a given bipartite multigraph by the above method?

If it is possible to do the above, then we could use e.g. nauty to compute it easily.

(Note: This question is "the other side of the coin" of a math.SE question: What is the number of bijections between two multisets? However, I tried to make this question self-contained.)