Revista do Vestibular da Uerj
Uerj DSEA SR-1
Rio de Janeiro, 24/11/2017
Ano 9, n. 25, 2016
ISSN 1984-1604

Inicial » Artigos » Análise combinatória: a importância dos métodos de contagem – parte 2

Artigos

Análise combinatória: a importância dos métodos de contagem – parte 2, por João Carlos Cataldo

Ano 6, n. 18, 2013

Autor: João Carlos Cataldo

Sobre o autor: João Carlos Cataldo é professor do Instituto de Aplicação Fernando Rodrigues da Silveira, da Universidade do Estado do Rio de Janeiro (CAp-UERJ). Tem mestrado em Matemática pela Universidade Federal do Estado do Rio de Janeiro (UNIRIO) e é autor de livros didáticos.

Publicado em: 22/04/2014

Dando continuidade à discussão iniciada na parte 1 deste artigo, abordaremos agora as soluções inteiras e não negativas de equações do seguinte tipo:


Considere-se a equação x1 + x2 + x3 + x4 = 7 (I). Suas soluções são listas de números inteiros não negativos da forma (x1, x2, x3, x4), que, substituídos na equação, tornam a igualdade verdadeira. Algumas soluções dessa são: (0, 0, 3, 4), (1, 0, 0, 6), (2, 0, 5, 0), (1, 2, 1, 3), (0, 0, 0, 7).

Nessa equação xi   0 para todo i do conjunto {1, 2, 3, 4}. Substituindo cada incógnita xi por yi – 1, temos y 1 , isto é, yi é um número inteiro positivo, tendo a equação resultante a forma abaixo (II):


O número de soluções inteiras e não negativas da equação ( I ) de incógnitas xi é igual ao número de soluções inteiras e positivas da equação ( II ) de incógnitas yi. Conforme o estudo anterior esse número é igual a:


Considere agora quatro gavetas distintas – A, B, C e D – para guardar sete objetos iguais a . Vamos calcular de quantos modos diferentes é possível arrumar esses objetos nas quatro gavetas, considerando que cada uma pode ficar sem objetos ou com no máximo até os sete objetos . Observe o exemplo a seguir.


Pode-se então imaginar um objeto colocado em cada uma das três gavetas e distribuir mais 7. Isso corresponde a arrumar 4 + 7 = 11 objetos em quatro gavetas distintas de modo que cada gaveta contenha pelo menos um objeto. Logo, recai-se no problema exposto na parte 1 deste artigo, que é arrumar objetos iguais em gavetas, considerando que cada gaveta deve ficar com pelo menos um objeto. Tem-se assim o número de arrumações igual a .

Pode-se considerar também que as gavetas A, B, C e D vão guardar, respectivamente, x1, x2, x3 x4 objetos, sendo  xi   0. Neste caso, o número de modos de guardar os sete objetos corresponde ao número de soluções inteiras não negativas da seguinte equação, que foi resolvida inicialmente:

x1 + x2 + x3 + x4 = 7

Generalizando, o número de soluções inteiras e não negativas de x1 + x2 + x3 + ... + xn = p é igual ao número de soluções inteiras e positivas de (y1–1) + (y2–1) + (y3–1) + ... + (yn–1) = p ou de y1 + y2 + y3 + ... + yn = p + n. Esse resultado corresponde ao número de modos de guardar p objetos iguais em n gavetas (quando em cada uma delas pode conter até todos os objetos) e corresponde a:


Pela propriedade das combinações complementares, tem-se:


Combinações completas ou com repetição de elementos

Considere os grupos de p objetos, distintos ou não, selecionados de um conjunto de n objetos, que poderão ser escolhidos em um evento, sem que se leve em conta a ordem da escolha. Cada um desses grupos, que pode ter no máximo até p objetos iguais, é uma combinação completa de classe p dos n elementos disponíveis.

As tabelas a seguir mostram combinações dos elementos distintos do conjunto {a, b, c, d}.

Combinações simples de quatro elementos tomados 2 a 2   Combinações completas de quatro elementos tomados 2 a 2
 ab ac ad
 bc bd
 cd
   aa ab ac ad
 bb bc bd
 cc cd
 dd
Combinações simples de quatro elementos tomados 3 a 3   Combinações completas de quatro elementos tomados 3 a 3
 abc abd acd
 bcd
   aaa aab aac aad abb acc add abc abd acd
 bbb bbc bbd bcc bdd bcd
 ccc ccd
 ddd ddc

As combinações são grupos não ordenados e só existe uma combinação simples desses quatro elementos tomados 4 a 4 que é (abcd), entretanto não é possível formar combinações simples dos mesmos elementos com grupos de cinco elementos. Existem combinações completas desses quatro elementos tomados 5 a 5, porque nestas é permitido repetir elementos. Alguns exemplos dessas combinações são aaaaa, abbbb, bbccc, abcda.

Se uma pessoa deseja comprar três refrigerantes em uma loja que vende cinco sabores diferentes – A, B, C, D ou E –, tem-se uma situação em que p = 3 e n = 5. Duas compras são diferentes apenas pela quantidade ou pela diferença dos sabores comprados; assim, AAA, BBE, ABC ou CDD são alguns exemplos de compras diferentes. Para calcular o número total de compras distintas que podem ser feitas, suponha que x1, x2, x3, x4 e x5 sejam os números de refrigerantes, respectivamente, dos tipos A, B, C, D e E, que serão comprados. Então:

x1 + x2 + x3 + x4 + x5 = 3

Observe a tabela com algumas compras que podem ser realizadas:

 Compras  x1  x2  x3  x4 x5 
 AAA 3 0 0 0
 BBE 0 2 0 0 1
 ABC 1 1 1 0 0
 CDD 0 0 1 2 0

Como xi   0, cada compra corresponde a uma solução inteira e não negativa dessa equação. De acordo com o estudo anterior, o número total de possibilidades de efetuar essa compra corresponde a:


Assim, o número de combinações completas ou com repetição de n objetos distintos tomados p a p, representado por , é igual ao número de soluções inteiras não negativas da equação x1 + x2 ... xn = p . Para esta equação,

x1 = número de elementos do 1º objeto,
x2 = número de elementos do 2º objeto,

(...)
xn = número de elementos do enésimo objeto.

Logo, , isto é, o número de combinações com repetição de n elementos tomados p a p corresponde ao número de combinações simples de n + p – 1 elementos tomados p a p.

Gostaríamos de ressaltar que, de uma forma simplificada, a análise combinatória consiste no estudo dos modos de contar agrupamentos de elementos sujeitos a regras específicas e, também, no estudo das propriedades desses agrupamentos. Em problemas simples do cotidiano, usamos argumentos dessa área da matemática discreta, como gostaria de ilustrar. Vinte alunos da minha turma vão votar nos quatro candidatos à presidência do Brasil. Naturalmente, cada pessoa só pode votar em um candidato. Considerando apenas o número de votos dados a cada um dos candidatos, quantas possíveis distribuições de votos existem?

Se x1x2x3 e x4 são, respectivamente, os números de votos dos candidatos A, B, C e D, então x1 + x2 + x3 + x4= 20, e o número de soluções inteiras, não negativas, pode ser descrito pela fórmula a seguir:


Esse valor corresponde ao número total de distribuições de votos que podem ocorrer.

Todos os ramos da matemática têm os seus aspectos combinatórios. Há na aritmética, na topologia, na lógica, na geometria, entre outros, a necessidade de se recorrer à combinatória. Em particular, a análise combinatória é essencial na teoria das probabilidades.

Finalizo estes dois artigos que abordam a importância dos métodos de contagem, lembrando que esse tópico da matemática discreta é tão importante que Gottfried Wilhelm Leibniz (1646-1716), que contribuiu muito com as teorias das probabilidades e da análise combinatória, na sua obra Dissertação sobre a arte da combinatória, concluiu que todo raciocínio dedutivo, tanto na matemática quanto na lógica pura, lida com combinações de símbolos em cadeia, de acordo com as regras de um sistema, que decide se a cadeia é uma proposição válida ou não.

Referências:

- A matemática no ensino médio, de Elon Lages Lima e outros, publicado pela Editora SBM.

- Análise combinatória e probabilidade, de A. C. Morgado, publicado pela Editora SBM.

- Prelúdio à análise combinatória, de Arago de C. Bachx, publicado pela Companhia Editora Nacional.

 

@2008-2017, Universidade do Estado do Rio de Janeiro. Todos os direitos reservados