Enunciado

Considere a identidade combinatória a

seguir:

(a) Apresente um argumento combinatório para essa identidade considerando um conjunto de n pessoas e determinando, de duas maneiras, o número de possíveis seleções de um comitê de qualquer tamanho e de um presidente para o comitê.

Dica:

(i) Existem quantas seleções possíveis para um comitê de tamanho k e seu presidente?

(ii) Existem quantas seleções possíveis para um presidente e os

demais membros do comitê?

Passo 1

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

a) Vamos escolher k pessoas dentre um grupo de n pessoas, isso pode ser feito de n k formas, esse numero binomial expresse exatamente esta ideia, podemos calcular isto pela equação:

n k = n ! n - k ! k !

Passo 2

E depois de escolhermos estas k pessoas, precisamos escolher quem delas será a presidente e temos k possibilidades para escolhermos este presidente. Então pelo Princípio Fundamental da Contagem há n k k possibilidades de se fazer esta escolha.

Se pensarmos agora que queremos saber de quantas formas podemos fazer este grupo de qualquer tamanho, podemos “varrer” todos os k ≤ n . Então seriam:

∑ k = 1 n k n k

Comitês possíveis de k pessoas e um presidente.

Passo 3

Também podemos pensar que primeiro vamos escolher o líder, e temos n formas de fazer isto e depois escolher os outros, cada um dos restantes podem estar ou não no comitê, havendo 2 opções para cada um das n - 1 pessoas restantes. Então pelo princípio fundamental da contagem:

n ⋅ 2 n - 1

Então:

∑ k = 1 n k n k = n ⋅ 2 n - 1

Resposta

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

Exercícios de Livros Relacionados

Mostre que, para n0, Somatório i=0 n -1^i (n i) = 0
Mostre que existem exatamente (r k) (n-1 n-r-k) soluções de x 1 + x 2 + … + x r = n
De quantas maneiras n bolas idênticas podem ser distribuídas em r urnas de forma que a i-ésima urna contenha pelo menos bolas, para cada i = 1, ..., r? Suponha que
Demonstre o teorema multinomial.
Considere um torneio com n competidores no qual o resultado é uma ordenação desses competidores, sendo permitidos empates. Isto é, o resultado divide os jogadores em grupos, com o primeiro grupo sendo