Enunciado

Considere a identidade combinatória a seguir:

(c) Mostre agora que

(n k) k3 = 2^n-3 n2 n+3

Passo 1

Opa galeeeeera! Hoje vamos entender um pouco mais sobre contagem.

∑ k = 1 n n k k 3 = 2 n - 3 n 2 ( n + 3 )

c) Para demonstrarmos esta igualdade vamos seguir o mesmo raciocínio do item (b) mas agora queremos escolher um presidente, uma secretaria e um tesoureiro, sendo que uma pessoa pode ocupar mais de um cargo.

Passo 2

Pelo primeiro raciocínio vamos fixar um comitê com número k de pessoas, e escolher essas k pessoas dentre as n disponíveis. Isto pode ser feito de n k maneiras. E depois disto, dentre as k pessoas escolhidas precisamos escolher um presidente ( k opções) e uma secretaria ( k opções) e um tesoureiro ( k opções). Pelo princípio multiplicativo, podemos fazer isto de n k ⋅ k ⋅ k ⋅ k = n k k 3 .

Mas como queremos que este comitê seja de qualquer tamanho, vamos somar todos os tamanhos k de comitês possíveis:

∑ k = 1 n n k k 3

Passo 3

Agora para escolher primeiro os cargos principais e depois decidir quem entra ou não no comitê, precisaremos dividir em 3 casos diferentes:

Ou há 3 pessoas, cada uma com cada cargo, ou há duas pessoas, uma ocupando dois cargos e outra um único cargo, ou há uma única pessoa ocupando os 3 cargos.

Primeiro vamos pensar no caso onde há uma única pessoa para os 3 cargos, teremos que escolher esta pessoa dentre as n pessoas no total ( n possibilidades), e depois decidir quem das n - 1 pessoas restantes vai entrar ou não ( 2 n - 1 formas). Pelo PFC isto poderia ser feito de:

n ⋅ 2 n - 1

Formas de se fazer isto.

Ou a secretaria e o presidente são a mesma pessoa, teríamos n formas de escolher ela e n - 1 formas de escolher o tesoureiro, e 2 n - 2 formas de decidir entre as pessoas restantes quem entra ou não no comitê. Pelo PFC há:

n n - 1 ⋅ 2 n - 2

Formas de se fazer isto.

Ou a secretaria e o presidente NÃO são a mesma pessoa, mas o tesoureiro é um deles, há n formas de escolher o presidente e n - 1 formas de se escolher a secretaria e 2 formas de se escolher o tesoureiro (ou a pessoa que é o presidente ou a secretaria) e ainda há 2 n - 2 pessoas para decidirem se entra ou não no comitê. Pelo PFC há:

n n - 1 2 ⋅ 2 n - 2 = n n - 1 2 n - 1

Formas de se fazer isto.

Ou cada um é uma pessoa diferente, havendo n formas de se escolher o presidente e n - 1 formas de se escolher a secretaria e n - 2 formas de se escolher o tesoureiro e restando n - 3 pessoas que poderiam entrar no comitê de 2 n - 3 formas diferentes. Pelo PFC há:

n n - 1 n - 2 2 n - 3

Formas de se fazer isto.

Como estas são todas as possibilidades, vamos utilizar o princípio aditivo (“ou”) para encontrar o resultado final:

n ⋅ 2 n - 1 + n n - 1 ⋅ 2 n - 2 + n n - 1 2 n - 1 + n n - 2 n - 3 2 n - 3

Colocando n ⋅ 2 n - 3 em evidencia:

n ⋅ 2 n - 3 ( 4 + 2 n - 1 + 4 n - 1 + n - 1 n - 2 )

Fazendo a distributiva e somando:

n ⋅ 2 n - 3 ( n 2 + 3 n )

Colocando n novamente em evidencia:

n 2 2 n - 3 ( n + 3 )

Passo 4

Como tanto no passo 2 quanto no passo 3 estávamos contando a mesma coisa os resultados devem ser iguais, então:

∑ k = 1 n n k k 3 = n 2 2 n - 3 ( n + 3 )

Resposta

Ei, a resposta está no passo a passo :)

Exercícios de Livros Relacionados

E se apenas os garotos sentarem-se juntos?
Uma turma de dança é formada por 22 estudantes, dos quais 10 são mulheres e 12 são homens. Se 5 homens e 5 mulheres forem escolhidos para formar pares, quantas combinações diferentes serão possíveis?
E se duas pessoas do mesmo sexo não puderem se sentar juntas?
Cinco prêmios diferentes (melhor desempenho escolar, melhores qualidades de liderança, e assim por diante) serão dados a estudantes selecionados de uma classe de trinta alunos. Quantos resultados dife
De quantas maneiras 8 pessoas podem se sentar em fila se:(c) houver 4 homens e 4 mulheres e não for permitido que dois homens ou duas mulheres se sentem em posições adjacentes?