Demonstre a relação de Stifel, isto é:
Solução
Consideremos um conjunto A com
elementos, e consideremos um deteminado elemento
. Vamos calcular o número de combinações dos elementos de A, tomados p a p, de dois modos:
1: modo: Diretamente pela fórmula, isto é,
2? modo: Calculamos o número de combinações que não possuam o elemento
.
Tal número é
.
Em seguida, calculamos o número de combinações que possuem o elemento
a. Tal número é
.
Ao todo, o número de combinações será:
De (1) e (2) concluímos que:
2? modo: Calculamos o número de combinações que não possuam o elemento
Em seguida, calculamos o número de combinações que possuem o elemento
a. Tal número é
De (1) e (2) concluímos que:
Passo 1
O enunciado pede para provar a relação de Stifel para coeficientes binomiais, ou seja, mostrar que, para todo
com
e todo
tal que
,
O conteúdo envolvido é contagem de combinações e a ideia é usar uma argumentação combinatória (princípio da partição) para contar, de dois modos, o número de subconjuntos de tamanho
de um conjunto de
elementos.
Passo 2
Escolha um elemento fixo
em um conjunto
com
. Todo subconjunto de
que tem exatamente
elementos cabe em uma das duas categorias mutuamente exclusivas: ou contém
, ou não contém
.
Passo 3
Contagem dos subconjuntos de tamanho
que não contêm
!: basta escolher
elementos entre os
restantes, o que fornece
subconjuntos.
Passo 4
Contagem dos subconjuntos de tamanho
que contêm
!: como
já está incluído, restam
vagas a preencher com elementos dos
restantes, o que dá
subconjuntos.
Passo 5
Pelo princípio da adição, o total de subconjuntos de
de tamanho
é a soma das duas contagens: