Problemas de contagem

Os problemas de contagem prendem-se com a determinação do número de elementos de um conjunto do qual apenas conhecemos algumas propriedades. Aqui apenas iremos concentrar-nos no cálculo do número de maneiras que existem para agrupar n bolas em m caixas. Supomos que tanto as caixas como as bolas estão indexadas por números. A figura seguinte apresenta os arranjos de duas e três bolas em três caixas.

Arranjos de duas e três bolas em três caixasApesar dos problemas parecerem ser de natureza diferente, a solução é a mesma, isto é, existem seis maneiras de arranjar duas bolas em três caixas como arranjar três bolas no mesmo número de caixas, tendo em conta que uma caixa só pode levar uma. De facto, o primeiro problema reduz-se ao segundo se considerarmos que na caixa vazia existe uma bola branca (e invisível).

Imaginemos que a bola azul tem o número 1, a bola vermelha tem o número dois e a amarela, o número 3. Escrevemos (3,1,2) para indicar que a bola 3 está na primeira caixa, a bola 1 está na segunda e a bola 2 se encontra na terceira.

Para contar o número de arranjos de n bolas diferentes em n caixas sabendo que cada caixa apenas pode levar uma bola, começamos por considerar o número de arranjos que existem sabendo que a primeira bola é a número 1. Suponhamos que existem k_1 arranjos. Adicionamos os números de arranjos k_1, k_2, \cdots, k_n que correspondem a considerar as bolas 2, 3, …, n na primeira posição. Contudo, o número de maneiras de agrupar as duas bolas restantes é independente da cor da bola que escolhemos como primeira. Deste modo, temos k_1=k_2=\cdots=k_n=k e o número total é dado por kn. Aplicamos este nosso processo recursivamente para chegarmos à conclusão que o número total de arranjos do género é igual a

n(n-1)(n-2)...2\times 1=n!

Se atentarmos na figura, vemos que este problema é equivalente a considerar todas as trocas de posições ou permutações de n bolas.

Vamos aplicar este nosso princípio ao problema: escolhendo um total de m bolas entre um conjunto de n e colocando-as em m caixas, determinar o número de maneiras que é possível fazê-lo.

Com o mesmo método que utilizámos para resolver o problema anterior, concluímos que podemos colocar n bolas na primeira caixa e considerar o número de maneiras de organizar as n-1 bolas em m-1 caixas. Este princípio permite concluir que a solução procurada é dada por

n(n-1)...(n-m+1)=\frac{n!}{(n-m)!}

Trata-se do número de arranjos de n bolas em m caixas, tendo em atenção que o número m é inferior ou igual a n.

Suponhamos agora que todas as bolas são iguais. Por exemplo, suponhamos que, na figura anterior, as bolas azul e vermelha são a mesma. Entre todas as permutações, existem aquelas em que a bola azul surge antes da vermelha e aquelas em que esta surge depois daquela. Como as bolas são para ser encaradas como iguais, uma permutação onde a bola azul aparece depois da vermelha é igual àquela permutação onde estas bolas aparecem trocadas entre si. Por exemplo, a permutação (vermelha, amarela, azul) é igual à permutação (azul, amarela, vermelha). Facilmente vemos que o número total de arranjos deste tipo é 3 que é igual ao número de permutações de 3 elementos considerando-os todos diferentes a dividir pelo número total de permutações dos elementos que são iguais.

Problema: determinar o número de maneiras que podemos arranjar n bolas em n caixas sabemdo que existem m_1 bolas do tipo 1, m_2 bolas do tipo 2, m_3 bolas do tipo 3, etc, m_k bolas do tipo k onde obviamente temos n=m_1+m_2+\cdots + m_k.

A observação que fizemos atrás permite-nos concluir que este número total é dado pelas combinações multinomiais

\frac{n!}{m_1!m_2!\cdots m_k!}

Se apenas existirem dois subconjuntos com m e n-m elementos, a solução é dada pelo número de combinações binomiais:

\binom{n}{m}=\frac{n!}{(n-m)!m!}

Um problema cuja solução é dada pelas combinações binomiais é o seguinte: determinar o número de maneiras de dispor m bolas escolhidas entre n não importando a ordem em que estas aparecem nas m caixas.

Como vimos atrás, se a ordem importar, o número de maneiras é dado pelos arranjos. Como a ordem não importa temos de o dividir pelo número de permutações de m elementos de acordo com o mesmo raciocínio apresentado no problema anterior. A expressão final corresponde ao número de combinações.

Problema: determinar o número de maneiras de agrupar n bolas diferentes em m>n caixas de modo que cada caixa leve apenas uma bola. Como m>n, terão de existir caixas vazias.
A solução deste problema não é muito diferente do problema anterior, destacando-se duas formas de raciocinar. Na primeira forma, considerarmos m bolas das quais m-n são iguais e representam as caixas que vão ficar vazias. Facilmente vemos que o número procurado é dado por

\frac{m!}{(m-n)!}

Outro método que leva à mesma solução consiste em trocar o papel das caixas com o das bolas, isto é, o problema torna-se equivalente a determinar o número de arranjos de m bolas em n caixas. Esta troca de papeis é possível porque uma caixa leva apenas uma bola e uma bola só pode estar numa caixa.

Se considerarmos que, neste problema, a ordem é irrelevante, o número de possibilidades é dado por

\frac{m!}{(m-n)!n!}=\binom{m}{n}

e é equivalente a considerar a colocação de n bolas iguais em m\ge n caixas. Sabemos que o número de maneiras de arranjar n bolas em n caixas de modo a que cada caixa contenha apenas uma bola é dado por n!. Se quisermos contar o número de maneiras de arranjar essas n bolas em m>n caixas, basta multiplicar n! pelo número de maneiras de colocar n bolas iguais nas m caixas, isto é

n!\binom{m}{n}=\frac{m!}{(n-m)!}

como vimos anteriormente.

Problema: determinar o número de arranjos de n bolas em m caixas de modo que cada caixa possa levar um número arbitrário de bolas.

Escolhemos a bola 1 e atribuímo-la à primeira caixa. Seja k o número de arranjos das restantes n-1 bolas nas m caixas. De seguida, atribuímo-la à segunda posição e consideramos o número de arranjos das outras n-1 bolas. Como o número de arranjos das restantes n-1 bolas nas m caixas não depende da caixa em que se encontra a primeira bola, vemos que o número total de arranjos é dado por mk. Agora, procedemos do mesmo modo para a segunda bola e, se l representar o número de arranjos das n-2 bolas nas m caixas então o número total de arranjos será igual a m^2l. Aplicando o processo recursivamente, obtemos para o número total de arranjos m^n. Tratam-se de arranjos com repetição.

Problema: determinar o número de formas de colocar n bolas diferentes em m caixas de modo que cada caixa possa conter um número arbitrário de bolas, ignorando a ordem de inserção. Este problema é equivalente a considerar a colocação de n bolas iguais em m caixas onde cada caixa pode conter um número arbitrário de bolas.
Este problema é um pouco mais difícil e resulta no número de combinações com repetição. Para o resolver, consideramos as bolas numeradas de 1 até n. Seja f(n,m) o número de combinações de n bolas em m caixas. Colocamos a bola 1 na primeira caixa. Como qualquer outra bola pode ser colocada na primeira caixa, o número total de combinações sabendo que a primeira bola está na primeira caixa é dado por f(n-1,m). Suponhamos que a primeira bola é colocada na segunda caixa tendo em conta que já contámos o caso em que a mesma foi atribuída à primeira caixa. Se considerarmos que uma das restantes bolas é introduzida na primeira caixa, ficamos com uma combinação que já foi contada anteriormente, uma vez que a ordem é irrelevante. Então o número total de combinações ainda por contar onde a primeira bola aparece na segunda caixa é dado por f(n-1, m-1). O raciocínio segue do mesmo modo para as restantes posições. Então

f(n,m)=f(n-1,m)+f(n-1,m-1)+...+f(n-1,1)

Facilmente chegamos à conclusão que f(1,m)=m e f(n,1)=1. No que se segue, inferimos indutivamente sobre o número de bolas para m fixo. Assim,

f(1,m)=m\\  f(2,m)=f(1,m)+f(1,m-1)+...+1=m+m-1+...+2+1=\binom{m+1}{2}\\  f(3,m)=f(2,m)+f(2,m-1)+...+f(2,1)=\binom{m+1}{2}+\binom{m}{2}+...+\binom{2}{2}=\binom{m+2}{3}\\ \cdots\\  f(n,m)=\binom{m+n-1}{n}

Como o resultado foi obtido por intermédio de um argumento indutivo, a sua prova formal é facilmente concebível com o auxílio do método da indução. Suponhamos que existem 3 caixas, as quais representamos pelas letras x, y e z. Consideramos também 5 bolas que pretendemos arranjar nas três caixas. Representamos a combinação (2,2,1) por x^2y^2z, isto é, qualquer combinação consiste num monómio homogéneo cujo grau iguala o número de bolas e com tantas variáveis quantas as caixas. Deste modo, a nossa expressão conta o número de monómios homogéneos de grau n com m variáveis.

Problema: determinar o número de maneiras de colocar n bolas distintas em m caixas sabendo que cada caixa leva, no máximo, duas bolas.

Este problema é um pouco mais complexo que os anteriores. Se n>2m então não há caixas suficientes para todas as bolas e o número de combinações é nulo. Neste ponto, consideramos que todas as bolas têm de ser colocadas nas caixas. Tentemos aplicar o método do problema anterior. Seja f(n,m,k) o número de arranjos de n bolas em m caixas de modo que k caixas suportem no máximo uma bola e m-k caixas suportem duas. Facilmente vemos que f(1,m,k)=m e f(n,m,k)=0 se n>2n-k. Se estivermos na presença de m caixas vazias onde k apenas suportam um bola, temos m hipóteses para colocar a primeira bola. Se esta bola estiver colocada numa das k caixas, ficamos com m-1 caixas disponíveis. Caso contrário, mantemos as caixas disponíveis mas a caixa que levou a bola ficou a suportar apenas uma. Com um raciocínio semelhante àquele utilizado no primeiro problema, obtemos a recorrência:

f(n,m,k)=kf(n-1,m-1,k-1)+(m-k)f(n-1,m,k+1)

Por exemplo, temos

f(1,m,k)=m\\ f(2,m,k)=m^2-k\\ f(3,m,k)=\left(m^2-3k+m\right)(m-1)

e assim sucessivamente. Se fizermos k=0, isto é, se considerarmos que todas as caixas levam duas bolas no máximo, então temos

f(1,m)=m\\ f(2,m)=m^2\\ f(3,m)=m(m-1)(m+1)\\ f(4,m)=m(m-1)(m^2+m-3)\\ f(5,m)=m(m-1)(m-2)(m^2+3m-3)

Apesar de não ser exequível à primeira vista vislumbrar um padrão (observamos que o grau dos polinómios em m é igual a n), uma outra estratégia permite chegar a algumas conclusões. Começamos por observar que

f\left(n,\frac{n}{2}\right)=\frac{n!}{2^{\frac{n}{2}}}

Tal é válido uma vez que se contarmos todas as permutações de n elementos com n par e as caixas estão completamente preenchidas com duas bolas, contamos duas vezes as permutações que envolvem apenas as bolas no interior das caixas. Se acrescentarmos uma caixa, irá sempre existir uma, apenas com uma bola. Se acrescentarmos uma outra caixa, duas delas irão conter apenas uma bola. Se somarmos cada uma destas configurações, obtemos, fazendo \alpha=n/2 se n for par e \alpha=(n-1)/2 se n for ímpar,

f(n,m)=\sum_{k=\alpha}^m{\frac{n!}{2^{n-k}}\binom{k}{n-k}\binom{m}{k}}

Ambos os métodos aqui explorados na resolução deste problema podem ser estendidos ao caso em que cada caixa admita um certo número máximo de bolas.

Problema: determinar o número de combinações de n bolas iguais em m caixas sabendo que cada caixa só pode levar, no máximo, duas bolas.

Este problema é semelhante ao anterior, onde é ignorada a ordem na colocação das bolas nas caixas. Poderia utilizar os métodos anteriores tendo em conta que as bolas são colocadas numa determinada ordem. Contudo, exploraremos aqui um método mais analítico. Vamos transformar a nossa notação. Suponhamos que temos de colocar 5 bolas em 4 caixas. Denotamos por (0,1,2,2) como sendo a combinação tal que encontramos 0 bolas na primeira caixa, 1 na segunda, 2 na terceira e 2 na quarta. Vemos que o nosso problema se resume a distribuir um conjunto de números por quatro espaços mantendo a sua soma igual a 5. Além disso, os números utilizados para colocar na caixa não podem exceder 2.

Consideremos a expansão do produto

\left(1+q+q^2\right)\left(1+q+q^2\right)\left(1+q+q^2\right)\left(1+q+q^2\right)=\left(1+q+q^2\right)^4

Se pretendermos determinar o coeficiente de q^5, com um pouco de perspicácia concluímos que este valor é precisamente igual ao número de maneiras de escrever o número 5 com o recurso aos números 0, 1 e 2. De facto, q^5=1q^2q^2q é uma das contribuições para o coeficiente procurado, escolhendo do primeiro factor 1, do segundo q^2, do terceiro q^2 e do quarto q. Todas as outras combinações surgem das escolhas dos vários graus que surgem nos factores.

Mais geralmente, para n bolas e m caixas, o número de maneiras de combinar as bolas nas caixas de modo que cada caixa leve no máximo k bolas corresponde ao coeficiente de q^n na expansão de

\left(1+q+q^2+...+q^k\right)^m

Este produto pode ser escrito como

\left(1-q^{k+1}\right)^m\frac{1}{\left(1-q\right)^m}

Com o auxílio do teorema do binómio, é possível obter a solução do nosso problema.

É possível imaginar mais problemas de contagem deste género tais como a generalização do penúltimo problema a um número máximo de bolas por caixa diferente ou considerar que cada caixa apenas pode levar um subconjunto específico das bolas podendo cada um dos subconjuntos associados a cada caixa ter intersecções não vazias ou não. A complexidade deste género de problemas começa a complicar bastante.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática. ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s