Question

Boa tarde.
Venho encontrando um problema sobre Contagem:
Imagine um computador que pode receber 2 entradas com valores iguais ou distintos dentre 10 valores numéricos possíveis. No entanto a máquina não diferencia a ordem do input, por exemplo, digitar 2 e então 5 é o mesmo, para o computador, de digitar 5 e então 2 e também é possível digitar dois valores iguais, por exemplo, 2 e 2. No caso de 2 entradas a resposta é mais fácil, no entanto me encontro com problemas ao generalizar para n entradas com k valores possíveis. Existe alguma expressão que ajude na resolução genérica?

Answer 1

Resposta:

$C_{n+k-1,k}=\frac{(n+k-1)!}{k!(n-1)!}$

Explicação passo-a-passo:

Esse é um problema de combinação com repetição, ou seja, combinação que pode repetir os termos iguais ( [1,1] [2,2] [3,3] ).

Para chegar na fórmula, vamos combinar a,b e c em 2 podendo repetir os termos iguais. Temos:

a ⇒ (a,a) (a,b) (a,c)

b ⇒ (b,b) (b,c)

c ⇒ (c,c)

Percebe-se que se aplicarmos a fórmula de combinação simples, não haverá resultados iguais, pois C₃,₂=3 e o número de combinações correto é 6. Devemos achar o número de termos novo da Combinação, nisso devemos aplicar na fórmula.

Temos um total de 6 combinações. Substituindo o 6 na fórmula de combinação simples e substituindo o k por 2, temos:

$C_{n,2}=\frac{n!}{2!(n-2)!}$

Fatorando o n!:

$6=\frac{n(n-1)(n-2)!}{2!(n-2)!}$

Cortando o (n-2)!:

$6=\frac{n^2-n}{2}$

$12=n^2-n$

$n^2-1-12=0$

Aplicando a fórmula de Bhaskara:

$n=\frac{1+\sqrt{1-4*1*(-12)} }{2}$

$n=\frac{1+7}{2}$

$n=4$

Então o novo número de termos é 4.

Percebe-se que 4=3+2-1, que é n+k-1. Esse é o número de termos de uma combinação com repetição.

Substituindo o n por n+k-1 na fórmula:

$C_{n+k-1,k}=\frac{(n+k-1)!}{k!((n+k-1)+k)!}$

Anulando os termos comuns:

$C_{n+k-1,k}=\frac{(n+k-1)!}{k!(n-1)!}$

Essa é a fórmula da combinação composta.

Agora resolvendo a questão de duas maneiras diferentes:

1- Vamos listar as fileiras de combinações:

(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,0)

(2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,0)

(3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,0)

. . .

Observamos um padrão na questão, perdendo um para cada agrupamento de combinação. Então o total de combinações será igual à soma delas, ou seja, 10+9+8+7+6+5+4+3+2+1 = 55.

2- Usando a fórmula de combinação composta:

$C_{10+2-1,2}=\frac{(10+2-1)!}{2!(10-1)!}$

$C_{11,2}=\frac{11!}{2!*9!}$

$C_{11,2}=\frac{11*10*9!}{2!*9!}$

$C_{11,2}=\frac{110}{2}$

$C_{11,2}=55$