# counting full bipartite matchings

My actual question is to find the number of transversal given a collection of set …

After a little bit of study it has come down to:

How can we count the number of matchings in a bipartite graph with parts of size $m$ and $n$ such that it covers all $m$ vertices of the first part, $m \le n$?

I already know that there is a way to count the number of perfect matchings in a bipartite graph with $m=n$ using the permanent of its (square) incidence matrix.

#### Solutions Collecting From Web of "counting full bipartite matchings"

Given an arbitrary bipartite graph $G$ with parts $A,B$ such that $|A|=m \le n = |B|$, the number $M$ of matchings that cover all $m$ vertices in $A$ can be expressed by a summation of $\binom{n}{m}$ permanents:

$$M = \sum_{R\in \mathcal{S}} \operatorname{perm} I_R$$

where the summation is taken over all the incidence matrices $I_R$ for subgraphs $G \cap (A\times R)$ resulting from choosing any $m$-subset $R \subset B$:

$$\mathcal{S} = \{ R \subset B : |R| = m \}$$

Note that in the generality posed in the Question, there is no guarantee that any of these summands will be nonzero. The computation of (binary) permanents is $\#P$-complete, so in most cases these will be difficult computations to perform with large $m,n$.