How many perfect matchings does a complete k-partite graph have? Suppose I have a complete k-partite graph $G = K_{n_1, n_2, ..., n_k}$ such that $\sum_{i=1}^k n_i = n$ is even.
How many perfect matchings does $G$ have?
E.g. $K_{1,1,2}$ has 2 perfect matchings; $K_{1,1,4}$ has no perfect matchings; $K_{2,2,2}$ has 8 perfect matchings.
I have attempted tackling this problem by the inclusion exclusion principle - considering the number of matchings in a complete $K_n$ graph and then subtracting the number of matchings with a pair in one part of the partition multiplied by $K_{n-2}$, adding the number of matchings with a pair in two parts of the partition multiplied by $K_{n-4}$, etc. etc.
However, I struggled to count the number of matchings of $K_{n}$ which contain a pair in one part of the partition. E.g. if we consider $K_{2,2,4}$, then there are $7*5*3$ matchings for $K_8$. Then there are $5*3$ matchings that pair two values from the first partition, $5*3$ that pair from the second partition. To count how many pair two values from the third, we first choose a pair, $4C2 = 6$, and multiply by $5*3$. However, we then count pairs that include two pairs in the third partition twice, so we need to subtract $4C2/2 * 5 * 3$. We then end up with $5*5*3$ matchings with a repeat in at least one partition. We then need to add matchings with pairs in two partitions, and subtract matchings with pairs in 3 partitions, etc.
This seems like a really really long sum, which is fine for small $n$, but not so much as it increases. I am hoping there is a more elegant solution to this problem?
 A: A more straightforward option is to break things down into cases based on the number of edges between the parts of size $n_1$ and $n_2$.
If there are $i$ such edges, then there are $\binom{n_1}{i} \binom{n_2}{i} i!$ ways to pick them. After that, there are $n_1 + n_2 - 2i$ vertices left in those parts combined, and by assumption we will take no more edges between them, so we can combine them together into one big part.
Therefore if $f(n_1, n_2, \dots, n_k)$ denotes the number of perfect matchings in $K_{n_1, n_2, \dots, n_k}$ then we have the recurrence
$$
   f(n_1, n_2, \dots, n_k) = \sum_{i=0}^{\min\{n_1, n_2\}} \binom{n_1}{i} \binom{n_2}{i} i!\, f(n_1 + n_2 - 2i, n_3, \dots, n_k).
$$
One possible base case is $f(n_1, n_2)$, which is $0$ if $n_1 \ne n_2$, and $n!$ if $n_1 = n_2 = n$.
This still gets pretty recursive for large $k$, but it's not too bad for small $k$, because the number of parts decreases by $1$ every time we recurse. Looking at the situation for $k = 4$, it doesn't look like there's a general closed form, but there is one for $k=3$:
$$
   f(n_1, n_2, n_3) = \frac{n_1!\,n_2!\,n_3!}{(\frac{n_1+n_2-n_3}{2})!\,(\frac{n_1+n_3-n_2}{2})!\,(\frac{n_2+n_3-n_1}{2})!}
$$
where, to be clear, the whole expression should be $0$ if any of the factorials are undefined. This can be shown from the general recurrence above, but there's also a direct reason.
First of all, $\frac{n_1+n_2-n_3}{2}$ tells us how many edges must be taken between the parts of size $n_1$ and $n_2$ (and similarly for the other expressions like this). Suppose we define a perfect matching in $K_{n_1, n_2, n_3}$ by ordering the vertices within each part in $n_1!\,n_2!\,n_3!$ ways, then:

*

*Match the first $\frac{n_1+n_2-n_3}{2}$ vertices in the first part to the first $\frac{n_1+n_2-n_3}{2}$ vertices in the second part, going in order.

*Match the last $\frac{n_1+n_3-n_2}{2}$ vertices in the first part to the first $\frac{n_1+n_3-n_2}{2}$ vertices in the third part, going in order.

*Match the last $\frac{n_2+n_3-n_1}{2}$ vertices in the second part to the last $\frac{n_2+n_3-n_1}{2}$ vertices in the third part, going in order.

Then each possible perfect matching is obtained $(\frac{n_1+n_2-n_3}{2})!\,(\frac{n_1+n_3-n_2}{2})!\,(\frac{n_2+n_3-n_1}{2})!$ times: for the edges taken in each step, we can permute the vertices from one part if we permute the vertices from the other part in the same way, and get the same perfect matching again. So we divide to correct for the overcount, and get the formula for $f(n_1, n_2, n_3)$ shown above.
