Há um tempo atrás, nosso colega MateusQqMD demonstrou que o número de soluções inteiras e não negativas de uma equação linear é dado por [tex3]P_{ \, m + k -1}^{ \, m, \,\, k-1}[/tex3]
.
Aqui, irei demonstrar que o número de soluções inteiras e positivas de uma equação linear é dado por [tex3]C^{k-1}_{m-1}[/tex3]
.
----------------------------------------------------------------------------------------------
Qual o número de soluções inteiras e positivas da equação linear [tex3]x_1+x_2+x_3+...+x_m=k[/tex3]
?
Imaginemos que tenhamos [tex3]k[/tex3]
quadrados enfileirados e queiramos separá-los em [tex3]m[/tex3]
grupos, com pelo menos um quadrado em cada um dos grupos.
[tex3]\underbrace{\underbrace{\square...\square}_{x_1\text{ quadrados}}|\underbrace{\square...\square}_{x_2\text{ quadrados}}|...|\underbrace{\square...\square}_{x_m\text{ quadrados}}}_{k\text{ quadrados},\ m\text{ grupos}}[/tex3]
Percebamos que tudo se resume à posição das barras entre os quadrados e que:
1) se temos [tex3]k[/tex3]
quadrados, há [tex3]k-1[/tex3]
espaços entre quadrados.
2) se queremos [tex3]m[/tex3]
grupos, teremos que inserir [tex3]m-1[/tex3]
barras entre quadrados, de forma que duas barras quaisquer estejam separadas por pelo menos um quadrado.
Podemos dispor as [tex3]m-1[/tex3]
barras nos [tex3]k-1[/tex3]
espaços de [tex3]C^{k-1}_{m-1}[/tex3]
maneiras.
----------------------------------------------------------------------------------------------
Exemplificando, qual o número de soluções inteiras e positivas da equação linear [tex3]x_1+x_2+x_3=5[/tex3]
?
Se temos 5 quadrados, há [tex3]5-1=4[/tex3]
espaços entre quadrados.
[tex3]\square\ \underbrace{\_}_{\text{espaço 1}}\ \square\ \underbrace{\_}_{\text{espaço 2}}\ \square\ \underbrace{\_}_{\text{espaço 3}}\ \square\ \underbrace{\_}_{\text{espaço 4}}\ \square[/tex3]
Se queremos dividi-los em 3 grupos (um com [tex3]x_1[/tex3]
, outro com [tex3]x_2[/tex3]
e outro com [tex3]x_3[/tex3]
quadrados), então precisaremos inserir [tex3]3-1=2[/tex3]
barras entre os quadrados.
Podemos dispor as 2 barras entre os 4 quadrados de [tex3]C^2_4=6[/tex3]
maneiras.
Citando uma das maneiras, se colocarmos as barras nos espaços 1 e 3, o resultado será
[tex3]\square\ |\ \square\ \square\ |\ \square\ \square[/tex3]
o que se reflete em [tex3]x_1=1,x_2=2,x_3=2[/tex3]
.
Demonstrações ⇒ Número de soluções inteiras positivas de uma equação linear
- csmarcelo
- Mensagens: 5114
- Registrado em: 22 Jun 2012, 22:03
- Última visita: 17-04-23
- Agradeceu: 355 vezes
- Agradeceram: 2801 vezes
Set 2019
02
09:41
Número de soluções inteiras positivas de uma equação linear
Editado pela última vez por csmarcelo em 21 Dez 2021, 09:54, em um total de 1 vez.
-
- Última visita: 31-12-69
Nov 2021
23
09:34
Re: Número de soluções inteiras positivas de uma equação linear
Outro raciocínio:
x1 + ... + xp = n
posso escrever n como uma soma de vários 1
1 + 1 + 1 ... + 1
são n-1 sinais de +
mas x1 + ... + xp tem p-1 sinais de +
então tenho que escolher p-1 sinais de + dentre os n-1 sinais de +
e feito
x1 + ... + xp = n
posso escrever n como uma soma de vários 1
1 + 1 + 1 ... + 1
são n-1 sinais de +
mas x1 + ... + xp tem p-1 sinais de +
então tenho que escolher p-1 sinais de + dentre os n-1 sinais de +
e feito
-
- Tópicos Semelhantes
- Resp.
- Exibições
- Últ. msg
-
- 4 Resp.
- 1869 Exibições
-
Últ. msg por 2657922
-
- 0 Resp.
- 763 Exibições
-
Últ. msg por bia11
-
- 2 Resp.
- 4473 Exibições
-
Últ. msg por csmarcelo
-
- 1 Resp.
- 1541 Exibições
-
Últ. msg por snooplammer