Enunciado

De um grupo de n pessoas, deve-se escolher um comitê de tamanho j. Deste comitê, também será escolhido um subcomitê de tamanho i, i 5 j.

(a) Deduza uma identidade combinatória para calcular, de duas maneiras, o número de escolhas possíveis para o comitê e o subcomitê - inicialmente supondo que o comitê seja escolhido antes do subcomitê, e depois supondo que o subcomitê seja escolhido antes

do comitê.

(b) Use a letra (a) para demonstrar a seguinte identidade combinatória:

(c) Use a letra (a) e o Exercício Teórico 1.13 para mostrar que

Passo 1

Opa galeeeeera! Hoje vamos contar as formas de se formar um grupo com vários subgrupos.

a) Para isso vamos seguir a dica do enunciado e contar de quantas formas podemos formar um grupo de j pessoas dentre n pessoas, e depois quantas formas podemos formar um grupo com i peassoas das j pessoas que já foram escolhidas.

Isto pode ser contado utilizando os números binomiais que exprimem exatamente esta ideia de formar um grupo:

n j j i

Passo 2

Agora vamos escolher primeiramente as i pessoas do subgrupo, dentre as n pessoas e depois escolher as j - i pessoas faltantes dentre as n - i pessoas que ainda não foram escolhidas. Isto pode ser feito de:

n i n - i j - i

Já que contamos a mesma coisa de duas formas diferentes, as respostas devem ser iguais.

n j j i = n i n - i j - i

Passo 3

b) Agora vamos demonstrar a igualdade:

∑ j = i n n j j i = n i 2 n - i ,   i ≤ n

Para provar isto vamos aplicar o somatório na identidade descoberta no item a:

∑ j = i n n j j i = ∑ j = i n n i n - i j - i

Como o termo n i é constante, vamos colocá-lo fora do somatório.

∑ j = i n n j j i = n i ∑ j = i n n - i j - i

Vamos fazer uma substituição de variável no somatório, de j para k = j - i :

= n i ∑ k = 0 n - i n - i k

Substituindo esta identidade na anterior:

∑ j = i n n j j i = n i 2 n - i

Como queríamos provar.

Passo 4

c) Agora vamos provar a identidade:

∑ j = i n n j j i - 1 n - j = 0 ,               i < n

Para isto vamos utilizar a mesma estratégia do item anterior, vamos manipular o resultado do item “a” para ficar igual a identidade pedida:

n j j i = n i n - i j - i

Multiplicando ambos os lados por - 1 n - j :

n j j i - 1 n - j = n i n - i j - i - 1 n - j

Agora aplicando o somatório em ambos os lados:

∑ j = i n n j j i - 1 n - j = ∑ j = i n n i n - i j - i - 1 n - j

Como o termo n i é constante, vamos colocá-lo fora do somatório:

= n i ∑ j = i n n - i j - i - 1 n - j

Vamos fazer uma substituição de variável no somatório, de j para k = j - i :

= n i ∑ k = 0 n - i n - i k - 1 n + i - k

Note que este somatório é o que aparece no teorema binomial para x = 1 e y = - 1 :

∑ k = 0 n - i n - i k ⋅ 1 n - i ⋅ 1 n - i - k = 1 - 1 n - i =   0

Substituindo isto na identidade:

∑ j = i n n j j i - 1 n - j = 0

Assim provamos a identidade inicial.

Resposta

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

Exercícios de Livros Relacionados

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 mo
Considere uma função f(x ,,..., x,) de n variáveis. Quantas derivadas parciais de ordem r a função f possui?
Determine o número de vetores (x1, ..., xn) tais que cada um seja um inteiro não negativo e
Mostre que Dica: Use um argumento similar aquele empregado para estabelecer a Equação (4.1).
Mostre que, para n0, Somatório i=0 n -1^i (n i) = 0