5

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 \begin{equation} \sum_{(i,j):\bar{x}_{ij}=1}x_{ij}\leq n-1 \end{equation} 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.

Djames
  • 1,143
  • 6
  • 13
  • Can you include the no-good cut that you use? – Kevin Dalmeijer Nov 20 '20 at 21:05
  • 3
    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 '20 at 21:54
  • 1
    @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. – Djames Nov 21 '20 at 15:35

2 Answers2

8

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} $$

Lars H
  • 201
  • 1
  • 3
3

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 ?

Hexaly
  • 2,976
  • 1
  • 11
  • 17
Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • You count infeasible matchings (meaning that a vertex can be covered by several edges) in your calculation. Lars brought some insights above. – Hexaly Nov 21 '20 at 09: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. – Kuifje Nov 21 '20 at 11:24
  • you’re right. We probably should have commented and fixed the question itself first, before commenting and fixing answers. – Hexaly Nov 21 '20 at 11:58