[Análise combinatória] dúvida

por **Tiego** » Qua Mai 09, 2012 10:32

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?

por **fraol** » Qui Mai 10, 2012 22:41

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.

$C_{n,k}$ 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 $C_{n-1, k}$ ( 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 $C_{n-1, k-1}$ ( veja que subtraímos 1 do total

e do total de

pois como o

sempre aparece então restam n-1

elementos para serem combinados em subconjuntos de k-1

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 é:

$C_{n,k} = C_{n-1, k} + C_{n-1, k-1}$ .

.

por **joaofonseca** » Qui Mai 17, 2012 08:32

Existe uma propriedade do triangulo de pascal que afirma:

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

A soma de dois termos consecutivos da mesma linha, k-1