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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you include the no-good cut that you use? $\endgroup$
    – Kevin Dalmeijer
    Commented Nov 20, 2020 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 ♦
    Commented Nov 20, 2020 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
    Commented Nov 21, 2020 at 15:35

2 Answers 2

Reset to default
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 ?

Improve this answer
$\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$
    – Hexaly
    Commented Nov 21, 2020 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
    Commented Nov 21, 2020 at 11:24
  • $\begingroup$ you’re right. We probably should have commented and fixed the question itself first, before commenting and fixing answers. $\endgroup$
    – Hexaly
    Commented Nov 21, 2020 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} $$

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Welcome, @Lars H. +1 This is OEIS sequence A002720. $\endgroup$
    – RobPratt
    Commented Nov 21, 2020 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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