Enunciado

Seja Hk(n) o número de vetores x1, ... , xk, para os quais cada x, é um inteiro positivo satisfazendo 1

(a) Sem quaisquer cálculos, mostre que H1(n) = sum n Hk-1

Dica: Existem quantos vetores nos quais x, = j?

(b) Use a recursão anterior para calcular H3(5).

Dica: Primeiro calcule H2(n) para n = 1,2,3,4,5.

Passo 1

Opa galeeeeera! Hoje vamos contar as formas de se criar um vetor.

H 1 n é o número de vetores ( x 1 ) que 1 ≤ x 1 ≤ n . Então há n diferentes vetores possíveis:

H 1 n = n

a) Agora vamos pensar que ( x 1 ,   … ,   x k ) é um vetor em que x i é um número positivo inteiro, e x k = j. Assim podemos conseguir o vetor correspondente ( x 1 ,   … ,   x k - 1 ) com x k - 1 ≤ x k = j , então 1 ≤ x 1 ≤ … ≤ x k - 1 ≤ j . Então x 1 ,   … ,   x k - 1 , j = ( x 1 ,   … ,   x k ) .

Então podemos notar que o número de vetores ( x 1 ,   … ,   x k ) tal que 1 ≤ x 1 ≤ … ≤ x k ≤ n e x k = j é precisamente igual a quantidade de vetores ( x 1 ,   … ,   x k - 1 ) tal que   1 ≤ x 1 ≤ … ≤ x k - 1 ≤ j e por definição esse número seria H k - 1 ( j ) .

Passo 2

Lembrando que ( x 1 ,   … ,   x k ) para 1 ≤ x 1 ≤ … ≤ x k ≤ n and x k pode ser qualquer valor entre 1 e n , e cada um desses casos são disjuntos de cada um, então:

H k n = ∑ j = 1 n n º   d e   v e t o r e s     x 1 ,   … ,   x k ,   t a l   q u e   1 ≤ x 1 ≤ … ≤ x k ≤ n   e   e   x k = j      

Aplicando a igualdade do número de vetores:

H k n = ∑ j = 1 n n º   d e   v e t o r e s     x 1 ,   … ,   x k - 1 ,   t a l   q u e   1 ≤ x 1 ≤ … ≤ x k - 1 ≤ j        

Então:

H k n = ∑ j = 1 n H k - 1 ( j )

Passo 3

b) Vamos utilizar essa equação recursiva para descobrir o valor de H 3 ( 5 ) :

Lembrando que H 1 n = n , e utilizando H k n = ∑ j = 1 n H k - 1 ( j ) :

H 3 5 = H 2 ( 1 ) + H 2 ( 2 ) + H 2 ( 3 ) + H 2 ( 4 ) + H 2 ( 5 )

Calculando H 2 :

H 3 5 = H 1 1                                                                                                                                                                                                                                                                       + H 1 1 + H 1 2                                                                                                                                                                                           + ( H 1 1 + H 1 2 + H 1 3                                                                                                                                                               + H 1 1 + H 1 2 + H 1 3 + H 1 4 + H 1 1 + H 1 2 + H 1 3 + H 1 4 + H 1 5

Substituindo o valor de H 1 :

H 3 5 = 1   + 1 + 2 + ( 1 + 2 + 3 )   + 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 + 5

H 3 5 = 35

Resposta

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

Exercícios de Livros Relacionados

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
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 m