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
Moderador: [ Moderadores TTB ]
Set 2019
02
09:41
Número de soluções inteiras positivas de uma equação linear
Última edição: csmarcelo (Ter 21 Dez, 2021 09:54). 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
- Respostas
- Exibições
- Última msg
-
- 1 Respostas
- 1024 Exibições
-
Última msg por Cardoso1979
-
- 1 Respostas
- 3654 Exibições
-
Última msg por deOliveira
-
- 1 Respostas
- 2957 Exibições
-
Última msg por Carlosft57
-
- 1 Respostas
- 3085 Exibições
-
Última msg por Carlosft57
-
- 1 Respostas
- 3000 Exibições
-
Última msg por Carlosft57