Enunciado

Considere a identidade combinatória a seguir:

(b) Verifique a identidade a seguir para n = 1,2,3,4,5: Para uma demonstração combinatória

da identidade anterior, considere um conjunto de n pessoas e mostre que ambos os lados da identidade representam o número de seleções diferentes de um comitê, seu presidente e seu secretário (que possivelmente acumula a função de presidente).

Dica:

(i) Quantas seleções diferentes resultam em um comitê contendo exatamente k pessoas?

(ii) Existem quantas seleções diferentes nas quais o presidente e o secretário são os mesmos?

(Resposta: n2"-'.)

(iii) Quantas seleções diferentes resultam no presidente e no secretário sendo pessoas diferentes?

Passo 1

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

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

b) Vamos testar esta igualdade para n = 1,2 , 3,4 , 5

Para n = 1 :

1 1 1 2 = 2 1 - 2 1 1 + 1 = 1

Para n = 2 :

∑ k = 1 2 2 k k 2 = 2 2 - 2 2 2 + 1 = 6

Para n = 3 :

∑ k = 1 3 3 k k 2 = 2 3 - 2 3 3 + 1 = 24

Para n = 4 :

∑ k = 1 4 4 k k 2 = 2 4 - 2 4 4 + 1 = 80

Para n = 5 :

∑ k = 1 5 5 k k 2 = 2 5 - 2 5 5 + 1 = 240

Passo 2

Agora ele pede para provarmos esta igualdade, para isso vamos utilizar as dicas do enunciado:

Vamos escolher dentre n pessoas um comitê com qualquer número de pessoas e dentre elas um presidente e um secretario (sendo que o presidente pode ser secretário também).

Vamos dizer que formamos um comitê com k membros, poderíamos fazer isto de n k diferentes formas. E depois dentre estas k   pessoas escolhidas precisamos decidir quais delas vão ser o presidente ( k possibilidades ) e qual delas vai ser o secretario ( k possibilidades ), pelo princípio multiplicativo seriam   n k k 2 formas diferentes de fazer estas escolhas sucessivas.

Mas como queremos fazer isto para um comitê com qualquer numero de membros (Ele pode ter ou 1 único membro ou 2 membros ... ou n membros ), pelo princípio aditivo vamos somar todas estas possibilidades:

∑ k = 1 n n k k 2

Passo 3

Com o raciocínio que vamos escolher primeiro o presidente do comitê, teremos n opções para presidente. E para a escolha da secretaria teremos temos que dividir em 2 casos, ou ela é a mesma pessoa que o presidente ( 1 única possibilidade), ou ela não é o presidente ( n - 1 possibilidades)

Caso a secretaria e o presidente sejam a mesma pessoa, sobram n - 1 pessoas que tem 2 opções ou estar ou não no comitê. Ou seja, a primeira pessoa tem 2 opções e a segunda também e ... e a pessoa n - 1 também, totalizando 2 ⋅ 2 ⋅ … ⋅ 2 = 2 n - 1 .

Então teríamos pelo princípio multiplicativo n ⋅ 1 ⋅ 2 n - 1 possibilidades caso o presidente e a secretaria sejam a mesma pessoa.

Quando eles não são a mesma pessoa, restariam n - 2 pessoas que poderiam estar no comitê, e elas poderiam estar ou não no comitê de 2 n - 2 diferentes formas, pelo mesmo argumento do penúltimo paragrafo. E finalmente, pelo princípio multiplicativo teríamos n ⋅ n - 1 ⋅ 2 n - 2 possibilidades onde o presidente e a secretaria são pessoas diferentes.

Como queremos ambos os casos utilizaremos o principio aditivo para encontrar o total de possibilidades:

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

Utilizando a propriedade de potência:

2 n - 1 = 2 n - 2 ⋅ 2

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

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 2 = 2 n - 2 n ( n + 1 )

Resposta

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