# Counting the number of matchings in a complete bipartite graph

I am trying to count the number of matchings in a complete bipartite graph (perfect as well as imperfect). It's relatively easy for me to convince myself that there is $$n!$$ perfect matchings in the graph $$\mathcal{K}_{n,n}$$. However, I cannot seem to figure out how many matchings this graph contains. I have experimented a bit, and the number seems to be very large. I have repeatedly solved the IP \begin{align} \min &\ \sum_{i=1}^n\sum_{j=1}^n x_{ij }\\ \mbox{s.t.:}\ & \sum_{i =1}^n x_{ij}=1,&&\forall j=1,\dots,n\\ \ & x_{ij}\in\{0,1\},&&\forall i,j=1,\dots,n \end{align} and then added no-good'' inequalities to remove the current solution until the solver (CPLEX) declared the problem infeasible. For $$n=1,2,3,4$$ I have gotten the numbers $$1,4,27,256$$ which suggests that the number of matchings should be $$n^n$$. But $$n=5$$ gave me $$3174$$ matchings (not the expected $$5^5=3125$$).

Can anyone guide me to the number of mathings in $$\mathcal{K}_{n,n}$$?

Edit: The no-good inequalities I use are the following $$$$\sum_{(i,j):\bar{x}_{ij}=1}x_{ij}\leq n-1$$$$ where $$\bar{x}$$ is the solution I want to cut out.

It turns out that @Kuifje was right and that I had a bug in my code. After fixing that, I get that there is $$n^n$$ solutions to my IP.

• Can you include the no-good cut that you use? Nov 20, 2020 at 21:05
• To get a valid matching, shouldn't you constraint $\sum_j x_{ij} \le 1$ for all $i$ (no repetitions of left endpoint)? Also, by making your constraint equality rather than inequality, aren't you skipping (imperfect) matchings that miss some right endpoints?
– prubin
Nov 20, 2020 at 21:54
• @prubin obviously I'm using the wrong terminology. The IP is the corret one, so maybe what I am counting is the number of semi-assignments. The idea is to count how many ways $n$ jobs can be assigned to $n$ agents if each agent in principle can handle all items, and all items need to be handled. Nov 21, 2020 at 15:35

If the bipartite graph is $$K_{n,n}$$, then all $$n$$ vertices of the left hand size have exactly $$n$$ possible matches (each node of the right layer is a candidate). So the total number of matchings is $$n^n$$ indeed.

Maybe you can try and detect if there are identical matchings among the $$3174$$ found by CPLEX ?

• You count infeasible matchings (meaning that a vertex can be covered by several edges) in your calculation. Lars brought some insights above. Nov 21, 2020 at 9:54
• Yes indeed, thanks for the clarification. I was just trying to match the OP's sequence and proposed LP. I think @prubin's comment sheds some light on the question which seems to be ill-posed. Nov 21, 2020 at 11:24
• you’re right. We probably should have commented and fixed the question itself first, before commenting and fixing answers. Nov 21, 2020 at 11:58

A matching of size $$m$$ in $$\mathrm{K}_{n,n}$$ is uniquely identified by (i) the set of covered vertices in the left partition, for which there are $$\binom{n}{m}$$ choices, (ii) the set of covered vertices in the right position, ditto $$\binom{n}{m}$$ choices, and (iii) a bijection from the covered vertices on the left onto the covered vertices on the right, for which there are $$m!$$ choices. This means there are $$\binom{n}{m}^2 m!$$ matchings of size $$m$$, and thus $$\sum_{m=0}^n \binom{n}{m}^2 m!$$ matchings altogether. For example, for $$n=2$$ there are $$7$$ matchings: $$2$$ perfect matchings, $$4$$ matchings of size $$1$$ (choose one out of two vertices to match on each side), and $$1$$ empty matching. Small table: $$\begin{array}{rr} n & \sum_{m=0}^n \binom{n}{m}^2 m! \\ 1 & 2 \\ 2 & 7 \\ 3 & 34 \\ 4 & 209 \\ 5 & 1546 \\ 6 & 13327 \\ 7 & 130922 \end{array}$$

• Welcome, @Lars H. +1 This is OEIS sequence A002720. Nov 21, 2020 at 1:00