Número de soluções inteiras positivas de uma equação linear
Enviado: 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 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] .
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] .