Combinatória elementar e o binômio de Newton

Os princípios de contagem

Contar os elementos de um conjunto finito é a operação mais elementar da aritmética enquanto o conjunto pode ser percorrido elemento a elemento. Ora, quando os elementos são as maneiras de realizar uma escolha composta, como ordenar dez livros numa estante ou escolher três representantes entre trinta pessoas, a enumeração se torna impraticável, e o número se obtém decompondo a escolha em partes ou em etapas. Toda a combinatória elementar repousa sobre dois princípios, que se demonstram a partir de uma definição precisa do que significa contar.

Contar os elementos de um conjunto é numerá-los: atribuir a cada número de $1$ até $n$ um elemento, sem repetir nenhum e sem omitir nenhum. Diz-se que um conjunto $A$ tem $n$ elementos, com $n$ natural, quando existe uma bijeção do conjunto $\{1, 2, \ldots, n\}$ em $A$, isto é, uma função que leva números distintos a elementos distintos e alcança todos os elementos de $A$; o conjunto vazio tem $0$ elementos, e um conjunto é finito se é vazio ou tem $n$ elementos para algum natural $n$. As bijeções, sua composição e sua inversa são estudadas na aula sobre conjuntos, relações e funções.

Fato admitido (número de elementos). Admite-se sem demonstração que o número de elementos de um conjunto finito está bem definido: um conjunto não pode ter ao mesmo tempo $m$ elementos e $n$ elementos se $m \neq n$. Admite-se também que todo subconjunto de um conjunto finito é finito.

Ambos os fatos se demonstram por indução sobre $n$; o primeiro é, no fundo, o princípio da casa dos pombos, segundo o qual não há uma função que leve os $n + 1$ números de $\{1, \ldots, n + 1\}$ a números distintos de $\{1, \ldots, n\}$. Suas demonstrações são longas e não trazem ideias que se usem depois, e por isso se admitem. Sem o primeiro, a expressão “o número de elementos” não teria sentido, e uma demonstração combinatória, que conta um mesmo conjunto de duas maneiras, não poderia concluir que os dois resultados são iguais.

Por indução sobre o número de partes, o princípio se estende a qualquer número finito de conjuntos sem elementos comuns dois a dois: a união de $A_1, \ldots, A_r$, com $n_1, \ldots, n_r$ elementos, tem $n_1 + \cdots + n_r$ elementos, porque a união dos $r + 1$ primeiros é a dos $r$ primeiros com o último, que não tem elementos comuns com eles. Dele se deduz o segundo princípio, que conta as escolhas feitas por etapas.

Do mesmo modo, por indução sobre o número de etapas, o princípio multiplicativo se estende a qualquer número finito delas: uma escolha em $r$ etapas, que podem realizar-se de $n_1, n_2, \ldots, n_r$ maneiras respectivamente, pode realizar-se de $n_1 n_2 \cdots n_r$ maneiras. Por exemplo, no sistema decimal estudado na aula sobre os sistemas de numeração posicional há $9 \cdot 10 \cdot 10 = 900$ números de três algarismos, porque o primeiro algarismo não pode ser $0$ e os outros dois são livres. Convém advertir que o princípio multiplicativo exige que o número de opções de cada etapa não dependa do que foi escolhido antes, ainda que as próprias opções dependam; se essa condição falha, separam-se casos em que ela se cumpre e somam-se seus resultados com o princípio aditivo.

As etapas sucessivas de uma escolha se representam com um diagrama de árvore: de um ponto inicial, a raiz, saem tantos ramos quantas opções tem a primeira etapa; da extremidade de cada ramo, tantos quantas opções tem a segunda, e assim sucessivamente. Cada percurso da raiz até uma extremidade final, ou folha, é uma escolha completa, e o princípio multiplicativo conta as folhas sem desenhá-las.