Lezione 36 — Princípio Fundamental da Contagem

Enunciado rigoroso e principio aditivo

Princípio Multiplicativo (PFC)

"Se você tiver $m$ maneiras de fazer uma coisa e $n$ maneiras de fazer outra, então há $m \cdot n$ maneiras de fazer as duas coisas." — OpenStax College Algebra 2e, §11.5

A justificativa formal: o insieme de todas as sequências é o produto cartesiano $E_1 \times E_2 \times \cdots \times E_k$, e $|A \times B| = |A| \cdot |B|$ (provado por indução). O PFC é exatamente esse teorema.

Princípio Aditivo

"O Princípio da Adição afirma que se há $m$ resultados no evento $A$ e $n$ resultados no evento $B$, e $A$ e $B$ são mutuamente exclusivos, então há $m + n$ resultados no evento $A$ ou $B$." — OpenStax College Algebra 2e, §11.5

Fatorial

Árvore de possibilidades

Uma árvore de decisão com $k$ níveis representa graficamente o PFC: cada nó no nível $i$ gera $n_i$ filhos. O total de folhas é $n_1 \times n_2 \times \cdots \times n_k$.

Funções e subconjuntos via PFC

• Total de funções $f: A \to B$ com $|A| = m,\, |B| = n$: $n^m$ (cada elemento de $A$ tem $n$ imagens independentes).
• Total de subconjuntos de $S$ com $|S| = n$: $2^n$ (cada elemento é incluso ou escluso).
• Funções injetoras $f: A \to B$ ($m \leq n$): $n \cdot (n-1) \cdots (n-m+1) = \frac{n!}{(n-m)!}$ — base do disposizione (Lezione 37).