Determine o número de vetores (x1, ..., xn)

tais que cada um seja um inteiro não negativo e

Passo 1

Opa galeeeeera! Hoje vamos contar as soluções não inteiras não negativas de uma inequação.

∑ i = 1 n x i ≤ k

Note que como x i tem que ser um inteiro não negativo, k também será um inteiro não negativo. Ou seja:

∑ i = 1 n x i ≤ k → ∑ i = 1 n x i = k ∑ i = 1 n x i = k - 1 … ∑ i = 1 n x i = 0

Passo 2

Já sabemos como contar o numero de soluções não negativas de uma equação

A equação genérica:

∑ i = 1 n x i = k

N º   d e   s o l u ç õ e s = P k + n - 1 k , n - 1   = n + k - 1 k

Mas como na nossa inequação, todos os valores entre 0 e k são validos basta adicionarmos um somatório a nossa resposta.

∑ i = 0 k n + i - 1 i

E este será o numero de soluções da nossa inequação.

Resposta

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

Exercícios de Livros Relacionados