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](http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199707)10%3A4%253C487%3A%3AAID-RSA4%253E3.0.CO;2-Q/abstract), 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](http://cs.anu.edu.au/~bdm/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?](https://math.stackexchange.com/questions/131722) However, I tried to make this question self-contained.)



In how many ways can we generate a given bipartite multigraph via the bipartite configuration model?
Hi,
I'm going to try to answer your first question, which is: Given a bipartite multigraph on $set(A)\cup set(B)$, in how many ways could it have resulted from the described procedure?


I think that your question is related to Barvinok's work on contingency tables. In particular, take a look at theorem 1.2 here: 


<http://www.math.lsa.umich.edu/~barvinok/newtab.pdf>


Let's say that $set(A)$ has $k$ elements and $set(B)$ has $m$ elements, and let $M$ be the adjacency matrix of the resulting bipartite multigraph. That is, $m\_{ij}$ is the number of edges between the $i$'th element of $set(A)$ and the $j$'th element of $set(B)$.
Furthermore, let $r\_1, ... ,r\_k$ be the degrees of the vertices in $set(A)$ and let $s\_1, ... ,s\_m$ be the corresponding degrees for $set(B)$.


Consider the following $n \times n$ block matrix $X$: There are $k \times m$ blocks, and the size of the $i,j$-th block is $r\_i$ by $s\_j$. Each row of $X$ corresponds to an element of $A$, and each column of $X$ corresponds to an element of $B$, and so the perfect matching $\alpha$ is a permutation matrix. This permutation matrix corresponds to the original graph iff there are $m\_{ij}$ ones in the $i,j$-th block of $X$.


Thus, your question is equivalent to: How many order $n$ permutation matrices are there with $m\_{ij}$ ones in the $i,j$-th block of $X$?
You have to choose $m\_{i,j}$ rows of $r\_i$ for the $i,j$-th block for every $j$, and do the same for the columns. Then, once you know which rows and columns correspond to which blocks, you have to choose a permutation matrix of order $m\_{i,j}$ for each block, so the answer is:


$$ \prod\_i{\binom{r\_i}{m\_{i,1}, ... ,m\_{i,m}}} \prod\_j{\binom{s\_j}{m\_{1,j}, ... ,m\_{k,j}}} \prod\_{i,j}{m\_{i,j}!} = $$
$$ \frac{\prod\_i{r\_i!} \prod\_j{s\_j!} }{\prod\_{i,j}{m\_{i,j}!}} .$$


This counting argument is very well presented in Barvinok's paper.


