Emparejamiento único en un grafo bipartito

Question

Dejemos que $K_{n,m}$ (m> n) tienen un conjunto de vértices $ (V_i: i \in [n])$ y $ (W_i: i \in [m])$ . Sea f(n) el número de coincidencias máximas distintas M en $K_{n,m}$ tal que $V_iW_i$ no está en M para cualquier $i \in [n]$

Describe f(n) utilizando el principio de inclusión y exclusión. (Así, tu respuesta final será una suma).

Estaba pensando en utilizar la combinatoria pero la pregunta pide específicamente el principio de inclusión y exclusión y no estoy seguro de cómo invocarlo aquí. Gracias

Answer 1

El número total de coincidencias máximas es: $\frac{m!}{(m-n)!}$ en un grafo bipartito con m y n vértices. Entonces por el principio de inclusión y exclusión (restando el número de casos no deseados):

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)!} $ o de forma más concisa:

\= $ \sum_{i=0}^n $ $ (-1)^i $ $ n \choose i $ $ \frac{(m-i)!}{(m-n)!} $