[Análise combinatória] dúvida

[Tiego]

Olá pessoal, estou com dúvida na seguinte questão:

Utilizando um argumento combinatório, mostre que

Cn,k= Cn-1,k-1 + Cn-1,k

Dica: fixe um elemento do conjunto, e conte o total de subconjuntos de tamanho k que contém o elemento e o total de subconjuntos de tamanho k que não o contém.

R.: Eu mostrei usando valores numéricos mas não sei se pode ser assim:

C5,2 = C4,1 + C4,2

C5,2 = 5!/(3!.2!) = 10
C4,1 = 4!/(3!.1!) = 4
C4,2 = 4!/(2!.2!)= 6

Portanto: Cn,k= Cn-1,k-1 + Cn-1,k

será que está correto?

[fraol]

Creio que a resposta que se quer para esse problema deva ser genérica, isto é deve-se usar argumentos genéricos e não um exemplo específico que é o que você apresentou. Assim uma possível resposta poderia ser a seguinte:

Utilizando um argumento combinatório, mostre que

Cn,k= Cn-1,k-1 + Cn-1,k

Dica: fixe um elemento do conjunto, e conte o total de subconjuntos de tamanho k que contém o elemento e o total de subconjuntos de tamanho k que não o contém.

representa o número de subconjuntos distintos contendo elementos de um total de elementos.

Vamos fixar um elemento dentre os elementos.

O número de subconjuntos de elementos em que não aparece é igual a ( veja que subtraímos 1 do total pois é como-se combinássemos o conjunto sem o ).

O número de subconjuntos de k elementos em que o aparece é igual a ( veja que subtraímos 1 do total e do total de pois como o sempre aparece então restam elementos para serem combinados em subconjuntos de elementos cada ).

Em suma, o total de subconjuntos contendo elementos é igual ao total de subconjuntos que não possuem um certo elemento somado com o total de subconjuntos que possuem esse certo elemento, isto é:

.


.

[joaofonseca]

Existe uma propriedade do triangulo de pascal que afirma:



A soma de dois termos consecutivos da mesma linha, e respetivamente, é igual ao termo de ordem da linha seguinte ().

Seja , logo: