Análise Combinatória

Pode ser feito por inclusão e exclusão. Digamos que \(B = \{b_1, b_2, ..., b_p\}\) e seja F o conjunto de todas as funções f:A → B. Considere os conjuntos  \(Fk \subset F \) definidos por

\(F_k = \{ f \in F; \, b_k \textrm{ não pertence a imagem de } f\}\)

A união dos \(F_k\) é justamente o conjunto das funções que não são sobrejetoras. Então o objetivo é calcular a cardinalidade de \(F \setminus (F_1 \cup F_2 \cup F_3 \cup \cdots \cup F_n)\). Como temos

\( | F_{i_1} \cap F_{i_2} \cap \cdots \cap F_{i_k}| = (p-k)^n \)

onde \(i_1, i_2, \dots, i_k\) são distintos. Portanto, pelo principio da inclusão e exclusão teremos:

\(\displaystyle |F_1 \cup F_2 \cup \cdots \cup F_p| = \binom p1 (p-1)^n - \binom p2 (p-2)^n + \binom p3 (p-3)^n - \cdots +(-1)^{p+1} \binom pp (p-p)^n\)

Logo, o número de funções sobrejetoras será

\( \displaystyle \binom p0 p^n  - \binom p1 (p-1)^n + \binom p2 (p-2)^n - \binom p3 (p-3)^n - \cdots +(-1)^{p} \binom pp 0^n = \boxed{\sum_{k=0}^p (-1)^k \binom pk (p-k)^n}\)