I have the complete bipartite graph $K_{k,k}$ and I want a formula for the number of perfect matchings in it. I tried to do this by drawing them out to see a trend and came up with $k(k-1)$ which works for $K_{2,2}$ and $K_{3,3}$ but not for $K_{1,1}$.
How I derived this is by looking at a single vertex in one partition and fixing the first edge in the matching and seeing how many perfect matchings I can derive by trying alternate paths, then fixing the second edge and repeating. I found that there are $k-1$ perfect matchings for the vertex and since the number of vertices are the same in each partition and they all have the same degree there is no need to check the other vertices.
I wanted to make sure whether the formula I constructed can be used to generalize.
Best Answer
A perfect matching in $K_{k,k}$ simply matches the vertices from the first part to the vertices from the second in some order, and because all the edges are there, any order is permitted. So what you are looking for is just the number of different orderings of the second part, i.e. $k!$.
Equivalently you can say there are $k$ ways to match the first vertex from the first part; once you have done that there are $(k-1)$ ways to match the second vertex from the first part (if $k>1$), and so on.