Identidades combinatórias

A análise combinatória pode ser uma bastante divertida quando tentamos entender as identidades combinatórias através de situações problemas. A análise combinatória deixa de ser um jogo complicado de fórmulas complexas e passa ser um jogo de contagem interessante. Logo, a frase de Tales de Mileto passa a fazer todo o sentido:

“A questão primordial, não é o que sabemos, mas como sabemos”

Frase retirada do trabalho Demonstração de Identidades Combinatórias com Teoria de Contagem

Identidade 1

$\binom{n}{k}$ = $\binom{n}{n-k}$

Problema:

De quantas maneiras podemos formar uma comissão com k alunos para representar a turma com n alunos?

O lado esquerdo conta de quantas maneiras podemos formar uma comissão com k alunos em uma turma com n alunos.  Cada comissão com k alunos exclui n-k alunos. O lado direito conta de quantas maneiras diferentes podemos exclui n-k alunos para formar uma comissão com k alunos.

Identidade 2

$\binom{n}{k}$ = $\binom{n-1}{k-1}$ + $\binom{n-1}{k}$

Problema: 

Novamente, o lado esquerdo representa o número de comissões com k alunos em uma turma com n alunos. Escolha um aluno qualquer da turma, este aluno pode pertencer ou não a comissão.
Caso 1: Se o aluno escolhido pertence a comissão então precisamos escolher k-1 alunos entre n-1 alunos restantes.
Caso 2: Se o aluno escolhido não pertence a comissão então precisamos escolher k alunos entre n-1 alunos restantes.

Identidade 3

$\sum_{i=0}^{n} \binom{n}{i}$ = $2^{n}$

Problema:

Precisamos formar uma comissão de alunos de qualquer tamanho em uma turma com n alunos?

O lado direito conta o número de subconjuntos possíveis em uma turma com n alunos. Cada subconjunto representa uma possível comissão formada. O lado esquerdo conta a mesma quantidade mas de uma maneira mais difícil. O lado esquerdo soma a quantidade de maneiras de formar uma comissão considerando todos os tamanhos possíveis.


Identidade 4

$k\binom{n}{k}$ = $n\binom{n-1}{k-1}$

Problema:

Queremos formar uma comissão com k alunos em uma turma com n alunos sendo que um deles é o presidente.

No lado direito, temos o seguinte raciocínio: temos n possibilidade para a escolha do presidente multiplicada pela quantidade de maneiras de escolher k-1 alunos entre n-1 alunos restantes. No lado esquerdo, contamos de quantas maneiras podemos formar uma comissão de k alunos entre n alunos multiplicada pela quantidade de maneiras que podemos escolher o presidente na comissão com k alunos.

Identidade 5

$\sum_{i=0}^{n} i\binom{n}{i}$ = $n2^{n-1}$

Problema:

Precisamos formar um time de futebol de qualquer tamanho com n jogadores sendo que um deles é o capitão.

Solução:

No lado direito, n representa de quantas maneiras podemos escolher o capitão entre n jogadores multiplicado pela quantidade de maneiras que podemos formar um time (subconjunto) entre n-1 jogadores (elementos). No lado esquerdo, realizamos o mesmo cálculo. Primeiramente, formamos um time com i jogadores multiplicamos pela quantidade maneiras que podemos escolher o capitão no time formado.


Exercício

Prove as seguintes identidades:

Identidade

$k(k-1)\binom{n}{k}$ = $n(n-1)\binom{n-2}{k-2}$

Pense em uma comissão com k membros de n possíveis sendo que cada comissão tem um presidente e um vice-presidente.

Identidade

$2\binom{2n-1}{n}$ = $\binom{2n}{n}$


Identidade

$\sum_{i=0}^{n} \binom{x}{i} \binom{y}{n-i}$ = $\binom{x+y}{n}$

Considere uma turma com x homens e y mulheres, precisamos formar uma comissão com n alunos.


Referências

Monografia Demonstração de Identidades Combinatórias com Teoria de Contagem

Bijections

More bijections