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

Fórum de coletânea das melhores demonstrações de teoremas de matemática.
Se você quiser postar uma demonstração aqui, poste, inicialmente, no fórum correspondente utilizando o título "Demonstração Teorema X" e substitua com o nome do teorema/fórmula que você postou e, depois, envie o link para um moderador pedindo para sua mensagem ser movida para o fórum "Demonstrações". 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: 5114
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 17-04-23
Set 2019 02 09:41

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

Mensagem não lida por csmarcelo »

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] .

Última edição: csmarcelo (Ter 21 Dez, 2021 09:54). Total de 1 vez.



Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Nov 2021 23 09:34

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

Mensagem não lida por Deleted User 23699 »

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




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

Voltar para “Demonstrações”