Let $K_{n,m}$ (m> n) have vertex set $ (V_i: i \in [n])$ and $ (W_i: i \in [m])$. Let f(n) be the number of distinct maximum matchings M in $K_{n,m}$ such that $V_iW_i$ is not in M for any $i \in [n]$
Describe f(n) using the principle of inclusion and exclusion. (So your final answer will be a sum).
I was thinking about using combinatorics but the question is specifically asking for principle of inclusion and exclusion and I am not sure how to invoke that here. Thank you
The total number of maximum matchings is: $\frac{m!}{(m-n)!}$ in a bipartite graph with m and n vertices. Then by the inclusion and exclusion principle (substracting the number of unwanted cases):
M = $ \frac{m!}{(m-n)!}$ - $ {n \choose 1} \frac{(m-1)!}{(m-n)!} $+$ n \choose 2 $ $ \frac{(m-2)!}{(m-n)!} $ + ... - $n \choose n$ $\frac{(m-n)!}{(m-n)!} $ or more concisely:
= $ \sum_{i=0}^n $ $ (-1)^i $ $ n \choose i $ $ \frac{(m-i)!}{(m-n)!} $