DemonstraçõesDemonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação

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
MateusQqMD
5 - Mestre
Mensagens: 1512
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 17-08-19
Localização: Fortaleza
Agradeceu: 765
Agradeceram: 994
Mai 2019 04 16:49

Demonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação

Mensagem não lida por MateusQqMD » Sáb 04 Mai, 2019 16:49

Durante o desenvolvimento de alguns problemas que comumente aparecem no fórum é exigido que sejam contadas as soluções inteiras e não negativas de uma equação linear. Por isso, resolvi deixar uma redação que possa ajudar na interpretação desses enunciados.

Exemplo 1. Quantas são as soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + x_3 + x_4 = 9.[/tex3]

Solução. Para contarmos as soluções dessa equação, escrevemos [tex3]9[/tex3] como a soma de nove [tex3]1'\text{s}:[/tex3]

[tex3]1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9.[/tex3]

E separamos o lado esquerdo da igualdade em [tex3]4[/tex3] partes. Isso pode ser feito acrescentando três barras entre os [tex3]1'\text{s}.[/tex3] Por exemplo:

[tex3]1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 = 9.[/tex3]

Cada barra é utilizada para separar duas incógnitas, sendo que cada disposição de barras gera uma solução para a equação. A divisão feita acima corresponde à solução:

[tex3]\begin{array}{ccccccccc}
x_1 &&& &&& x_2 &&& &&& x_3 &&& &&& x_4 &&& \\
3 &&& | &&& 3 &&& | &&& 2 &&& | &&& 1 \\
\end{array}[/tex3]

Isto é, [tex3]x_1 \, = \, 3, \,\,\,\, x_2 \, = \, 3, \,\,\,\, x_3 \, = \, 2 \,\,\, \text{e} \,\,\, x_4 \, = \, 1.[/tex3]


Outras soluções são as seguintes:


[tex3]1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 \, = \, 9 \,\,\,\,\,\,\,\,\,\,\,\,\, (2, \,\, 4, \,\, 2, \,\, 1)[/tex3]

[tex3]| \hspace{0,4cm} 1 + 1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 + 1 + 1 = \, 9 \,\,\,\,\,\,\,\,\,\,\,\,\, (0, \,\, 4, \,\, 0, \,\, 4)[/tex3]


O valor de [tex3]x_1[/tex3] será o número de [tex3]1'\text{s}[/tex3] à esquerda da primeira barra; o de [tex3]x_2,[/tex3] o número de [tex3]1'\text{s}[/tex3] entre a primeira e a segunda barra; o de [tex3]x_3,[/tex3] o número de [tex3]1'\text{s}[/tex3] entre a segunda e a terceira barra e, por fim, o de [tex3]x_4,[/tex3] o número de [tex3]1'\text{s}[/tex3] à direita da última barra.

Daí, podemos concluir que o número de soluções inteiras e não negativas da equação mostrada é dado pelo número de modos de arrumarmos em fila [tex3]12[/tex3] elementos dos quais [tex3]3[/tex3] são barras iguais e [tex3]9[/tex3] são [tex3]1' \text{s}[/tex3] iguais. Isto é, podemos fazer isso de [tex3]P_{\,12}^{\,3,9} = \frac{12!}{3!9!} = 220[/tex3] modos.

Logo, há [tex3]220[/tex3] soluções inteiras e não negativas para [tex3]x_1 + x_2 + x_3 + x_4 = 9.[/tex3]




Caso geral. Calcular o número de soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + \, ... \, + x_k = m,[/tex3] onde [tex3]k[/tex3] e [tex3]m[/tex3] são naturais dados.

Solução. A ideia, novamente, é expressar o inteiro [tex3]m[/tex3] em função da soma de [tex3]1'\text{s}[/tex3] e utilizar barras para separá-los:

[tex3] \underbrace{ 1 + 1 + 1 + \,\, ... \,\,+ 1 }_{ \text{m} \,\, 1'\text{s} } \,\,\, \underbrace{ | \,\, | \,\, | \,\, ... | \,\, | \,\, }_{ k -1 \,\, \text{barras} } [/tex3]

Logo, como temos [tex3]\text{m} \,\, 1'\text{s}[/tex3] e [tex3]k -1[/tex3] barras para separar [tex3]k[/tex3] incógnitas, o número de soluções é [tex3]P_{ \, m + k -1}^{ \, m, \,\, k-1} = \frac{(m + k -1)!}{m!(k-1)!}.[/tex3]




Exemplo 2. De quantos modos podemos comprar [tex3]3[/tex3] carros de um mesmo modelo onde a cor de cada um deles pode ser amarela, branca, laranja ou verde?

Solução. A resposta desse problema é equivalente ao número de soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + x_3 + x_4 = 3.[/tex3] Onde [tex3]x_1[/tex3] é a quantidade de carros comprados da cor amarela, [tex3]x_2[/tex3] a quantidade de carros comprados da cor branca, [tex3]x_3[/tex3] a quantidade de carros comprados da cor laranja e [tex3]x_4[/tex3] a quantidade de carros comprados da cor verde.

A resposta é [tex3]P_{3 + 4 -1}^{3, \,\, 4-1} = \frac{(3 + 4 -1)!}{3!(4-1)!} = \frac{6!}{3!3!} = 20[/tex3] modos.


Nota: o número de permutações de [tex3]n[/tex3] objetos dos quais [tex3]n_1[/tex3] são iguais a [tex3]\alpha, \,\,[/tex3] [tex3]n_2[/tex3] são iguais a [tex3]\beta, \, ... \,\, [/tex3] e [tex3]n_n[/tex3] são iguais a [tex3]\gamma [/tex3] [tex3](n_1 + n_2 + \, .... \, + n_n = n)[/tex3] é:

[tex3]P_{\,n}^{ \,n_1, \, n_2, \, ... \,, \, n_n} = \frac{n!}{n_1!\,n_2! \, ... \, n_n!}[/tex3]

Última edição: MateusQqMD (Dom 05 Mai, 2019 07:48). Total de 2 vezes.
Razão: acrescentar exemplo


~I.H

Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 4073
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 15-08-19
Agradeceu: 323
Agradeceram: 2469
Jul 2019 19 18:23

Re: Demonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação

Mensagem não lida por csmarcelo » Sex 19 Jul, 2019 18:23

De outra forma, [tex3]CR^k_m=C^{k+m-1}_m[/tex3]




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

Voltar para “Demonstrações”