Contagem, probabilidade

Probabilidade e contagem aparecem juntos com frequência em matemática discreta.

Por exemplo, imagine que temos um conjunto de objetos \(A\), e que alguns deles têm certa propriedade. Vamos dizer um objeto é bom se tem a propriedade e ruim caso contrário.

Uma maneira de demonstrar a existência de objetos bons é construir um (claro!). Se isso for difícil, podemos abordar o problema indiretamente. Se conhecemos o tamanho \(|A|\) de \(A\) ou se conseguimos limitar \[\frac{\text{# objetos ruins}}{|A|}<1,\] então sabemos que existem objetos bons!

De modo geral, seja \(R\subseteq A\) o conjunto dos objetos ruins. Se encontramos uma cobertura de \(R\) por subconjuntos  \(R_i\subseteq R\), para \(i\in\{1,\ldots,n\}\) (isto é,  \(\bigcup_i R_i \supseteq R\)), tal que \(\sum_i |R_i|<|A|\), então certamente existe \(B=A \setminus \bigcup_i R_i\) que é não-vazio: esse é um conjunto de elementos bons.