DemonstraçõesNúmero de soluções inteiras positivas de uma equação linear

Fórum de coleânea das melhores demonstrações de teoremas de matemática.
Se você quiser postar uma demonstração, poste no fórum correspondente com o títuo "Demonstração Teorema X" e substitua com o nome do teorema/fórmula que você postou. Somente moderadores poderão mover sua mensagem para este fórum.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
csmarcelo
6 - Doutor
Mensagens: 4259
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 19-10-19
Agradeceu: 342
Agradeceram: 2615
Set 2019 02 09:41

Número de soluções inteiras positivas de uma equação linear

Mensagem não lida por csmarcelo » Seg 02 Set, 2019 09:41

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 entre os [tex3]k-1[/tex3] quadrados 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] .




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Demonstrações”