5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you include the no-good cut that you use? $\endgroup$ Nov 20 '20 at 21:05
  • 3
    $\begingroup$ 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? $\endgroup$
    – prubin
    Nov 20 '20 at 21:54
  • 1
    $\begingroup$ @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. $\endgroup$
    – Djames
    Nov 21 '20 at 15:35
3
$\begingroup$

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 ?

$\endgroup$
3
  • $\begingroup$ You count infeasible matchings (meaning that a vertex can be covered by several edges) in your calculation. Lars brought some insights above. $\endgroup$ Nov 21 '20 at 9:54
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Nov 21 '20 at 11:24
  • $\begingroup$ you’re right. We probably should have commented and fixed the question itself first, before commenting and fixing answers. $\endgroup$ Nov 21 '20 at 11:58
8
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ Welcome, @Lars H. +1 This is OEIS sequence A002720. $\endgroup$
    – RobPratt
    Nov 21 '20 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.