Análise Combinatória e Probabilidade: Com Aplicações no SageMath

Denote cada sabor por um número entre \(1\) e \(6\text{.}\) Note que este problema é equivalente ao de encontrar o número de soluções inteiras da equação:

na qual, cada \(x_i, i\in\{1, 2, 3, 4, 5, 6\}\) representa a quantidade de bolas de sorvete com sabor \(i\text{.}\) Claramente, temos a restrição \(x_i\geq 0\text{,}\) pois não podemos pegar uma quantidade negativa de bolas de sorvete.

Vamos mostrar que o problema de encontrar o número de soluções (1.7.1) é equivalente a encontrar o número de permutações com repetições de uma sequência com \(3\) elementos de um tipo e \(5\) elementos de outro tipo.

Escreva de \(x_1\) até \(x_6\text{,}\) entre uma incógnita e outra coloque na linha de baixo um traço vertical. Para representar a quantidade bolas de sorvete com sabor \(1\) ou \(6\text{,}\) coloque a respectiva quantidade de bolas antes do primeiro traço ou depois do último traço, respectivamente. Para representar a quantidade de bolas de sorvete com sabor \(i\text{,}\) com \(i\in \{2, 3, 4, 5\}\text{,}\) coloque a quantidade de bolas abaixo de \(x_i\text{,}\) entre dois traços consecutivos. Assim, a solução

é representada por:

Observe que cada permutação dessa representação de traços e bolas é uma solução da Equação (1.7.1) e que cada solução da Equação (1.7.1) pode ser representada com traços de bolas (Existe uma bijeção entre as duas coisas).

Portanto, para encontrar o número de soluções da Equação (1.7.1), basta calcular

pois, temos 5 traços e 3 bolas, então estamos permutando um total de 8 elementos, sendo 5 de um tipo e 3 de outro tipo.

O número de soluções desta equação, com \(x_i\in \mathbb{Z} \text{ e } x_i\geq 0, i\in\{1, 2, \ldots, 10\}\) é o número de combinações completas de 10 elementos, tomados 20 a 20:

Defina

Fazendo a substituição na equação do problema, temos

ou seja,

Desta forma, o número de soluções interias e não negativas de (1.7.2) será o número de soluções da equação original, pois, quando \(x\geq0\) teremos \(x_1\geq1\text{,}\) quando \(y\geq0\) teremos \(x_2\geq2\) e quando \(z\geq0\) teremos \(x_3\geq4\text{.}\) Portanto, a resposta é

Observe que uma possibilidade seria calcular o número de soluções de cada um dos casos:

A soma do número de soluções de cada um dos casos é a resposta, no entanto, é inviável fazer tal cálculo. Felizmente temos outra forma de resolver este problema.

Observe que existe uma bijeção entre o conjunto das soluções de (1.7.3) com o conjunto das soluções da equação (1.7.5):

Para entender a bijeção, observe o seguinte. Somando \(50-i, i\in \{0, 1, 2, \ldots, 50\}\text{,}\) nos dois lados da igualdade, na linha \(i, i\in \{0, 1, 2, \ldots, 50\}\) de (1.7.4), não mudamos absolutamente nada e ficamos com:

Cada solução da linha \(i\text{,}\) é uma solução de (1.7.5) com o valor de \(y\) igual a \(50-i\text{.}\) E para cada \(y\in \{0, 1, 2, \ldots, 50\}\) a solução de (1.7.5) vai ser a solução da linha \(y\) de (1.7.4) .

Portanto a resposta é o número de solução da equação (1.7.5) que é dado por:

Observe que os números estão em disposição circular, então vamos separar as peças em três tipos:

1. Todos os lados com o mesmo valor. Cada peça pode ser formada de uma única forma.
2. Dois lados possuem um valor e o terceiro lado possui um valor diferente. Cada peça pode ser formada de uma única forma, pois o número de permutações circulares com 3 elementos é 2, mas como temos duas entradas iguais, precisamos dividir por 2.
3. Cada lado possui um valor diferente. Cada peça pode ser formada de duas formas, pois o número de permutações circulares com 3 elementos é 2.

Inicialmente, vamos contar como se em cada tipo, as peças só pudessem ser formadas de uma forma, depois vamos acrescentar a quantidade de peças do terceiro tipo, que fica faltando nessa contagem inicial.

Temos que escolher os valores de cada um dos 3 lados de cada peça do trominó. Como os valores vão de 1 até 6 e são 3 lados, o número de peças do trominó (sem contar as permutações circulares) para \(n=6\) é o número de soluções inteiras não negativas da equação:

que é dado por \(CR_6^3\text{.}\)

Agora precisamos contar as peças, do terceiro tipo, que estão faltando. Como os três valores são diferentes, temos 6 opções de valores para escolher 3 e para cada escolha, temos duas formas de organizar na peça do trominó, portanto o número de peças desse tipo é:

Já que, a metade das peças do terceiro tipo foram contadas uma vez pela combinação completa, \(CR_6^3\text{,}\) a quantidade total de peças é: