import matplotlib.pyplot as plt
plt.style.use('../styles/gcpeixoto-book.mplstyle')

Introdução¶

Considere o seguinte problema:

Túlio é um jovem que gosta de comer pizza. Ele então pega seu aplicativo preferido de delivery e pede uma pizza de calabresa da pizzaria Tutta Massa que fica no mesmo bairro onde mora a poucos quarteirões de sua casa. O mapa da figura abaixo mostra que a pizzaria está localizada no ponto $P$ e a residência de Túlio no ponto $T$ . Considerando que para chegar até a casa de Túlio o entregador se desloque apenas nas direções norte ou leste, quantos caminhos possíveis o entregador pode percorrer?

Figure 1:Quarteirões do bairro de Túlio.

Modelagem do problema¶

Considere o ponto $P$ como a origem de um plano cartesiano $(0,0)$ . Para ir de $P$ até $T$ , o entregador deve se deslocar por até 4 quarteirões para leste (L) e até 3 quarteirões para norte (N). Ou seja, ele no máximo terá se deslocado por 4 + 3 = 7 quarteirões. Mas isso é o mesmo que procurar todos os caminhos possíveis do ponto $(0,0)$ até o ponto $(4,7)$ seguindo as restrições de deslocamento (como veremos mais à frente, o plano cartesiano aqui é formado pelo produto cartesiano $\mathbb{Z^{+}} \times \mathbb{Z^{+}}$ ). Um dos caminhos possíveis, por exemplo, seria $\{L,L,L,L,N,N,N\}$ .

Antes de passarmos a parte matemática, faça um exercício e tente escrever manualmente todos os caminhos possíveis. Você consegue determinar qual deles seria o mais próximo?

Bem, como resolver?

Este problema pertence ao domínio da Análise Combinatória. Especificamente, é um problema de permutações com repetição. Matematicamente, o número de caminhos será dado por:

P_{n}^{n_1,n_2} = \frac{n!}{n_1!n_2!},

(1)

onde $n$ é o número total de passos, $n_1$ o número máximo de passos na direção $L$ e $n_2$ o número máximo de passos na direção $N$ .

Resolvendo o problema de modo matemático¶

Fazendo $n = 7$ , $n_1 = 4$ e $n_2 = 3$ , chegamos a:

P_{7}^{4,3} = \frac{7!}{4!3!} = \frac{7.6.5.4!}{4!3.2} = \frac{7.6.5}{6} = 35

(2)

OK, mas eu não sei (ou não me recordo) o que significa esse ponto de exclamação aí na conta...

Este é o fatorial de um número inteiro. O fatorial de um inteiro $n$ é dado por:

n! = n(n-1)(n-2)...(n-p)1

(3)

Ou ainda, como você aprenderá, podemos representar esta operação com a seguinte notação:

n! = \prod_{k=1}^n k

(4)

Resolvendo o problema de modo computacional¶

Para resolver este pequeno problema, precisamos ensinar o computador a calcular o fatorial de um número inteiro e depois calcular a permutação. Note que, a bem da verdade, o computador teria que aprender a fazer coisas mais básicas, tais como multiplicar e dividir. Porém, vamos aproveitar o fato de que ele já sabe fazer operações elementares e usar a linguagem Python para escrevermos um programa computacional para resolver este problema. Em resumo, temos que fazer duas coisas:

Escrever uma função que calculará o fatorial de um número inteiro
Escrever uma segunda função que calculará a permutação

Passo 1: calculando o fatorial¶

A primeira função pode ser desenvolvida através da ideia de recursão (vamos aprender isso mais adiante no curso). O código é mais ou menos da forma a seguir:

def fatorial(n):
    """Calcula o fatorial de um número inteiro positivo.

    Parâmetros:
        n (int): Número inteiro não negativo.

    Retorna:
        int: O fatorial de n.
    """
    if n == 0:
        return 1  # 0! = 1
    else:
        return n * fatorial(n - 1)

O código acima possui uma instrução condicional. Uma vez que, por definição, $0! = 1$ , a primeira declaração if (“se”), trata deste caso particular. A declaração else (“senão”), utiliza a própria função para calcular os novos produtos. Vamos fazer uns testes.

fatorial(0)

1

fatorial(1)

1

fatorial(2)

2

fatorial(3)

6

fatorial(5)

120

fatorial(8)

40320

Hmmm... Parece que o código está fazendo sentido. Vamos verificar se os valores de 5! e 8! estão corretos.

5*4*3*2*1

120

8*7*6*5*4*3*2*1

40320

Ótimo! Parece que está funcionando legal! Pois é... mas o nosso código ainda não está “perfeito” para o computador. Por quê? O que aconteceria se $n = 3.2$ ?

fatorial(3.2)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[13], line 1
----> 1 fatorial(3.2)

Cell In[4], line 13, in fatorial(n)
     11     return 1  # 0! = 1
     12 else:
---> 13     return n * fatorial(n - 1)

Cell In[4], line 13, in fatorial(n)
     11     return 1  # 0! = 1
     12 else:
---> 13     return n * fatorial(n - 1)

    [... skipping similar frames: fatorial at line 13 (2975 times)]

Cell In[4], line 13, in fatorial(n)
     11     return 1  # 0! = 1
     12 else:
---> 13     return n * fatorial(n - 1)

RecursionError: maximum recursion depth exceeded

Opsss... Temos um erro aí... Por que isso aconteceu? Porque 3.2 não é um número inteiro! E como verificamos isso em Python? Podemos usar a função type. Veja:

type(3.2)

float

Ou seja, 3.2 é um número cujo tipo de dado é float (ponto flutuante). Por outro lado, veja:

type(3)

int

Ou seja, 3 é um número cujo tipo de dado é int (inteiro). Aí sim! Este número pode ser usado em nossa função fatorial, como testamos acima. Por enquanto, vamos deixar em aberto esse probleminha com a nossa função e transferir essa discussão para o seu curso de Estrutura de Dados.

Voltemos ao segundo passo do projeto...

Passo 2: calculando a permutação¶

Para calcular a permutação com repetição que aprendemos, precisamos criar uma função que possua 3 argumentos: os inteiros $n$ , $n_1$ e $n_2$ . Isto pode ser feito mais ou menos assim:

def permutacao_repeticao(n, n1, n2):
    """Calcula o número de permutações com repetição.

    Considera n elementos, dos quais n1 e n2 são repetidos.

    Parâmetros:
        n (int): Número total de elementos.
        n1 (int): Quantidade de repetições do primeiro tipo.
        n2 (int): Quantidade de repetições do segundo tipo.

    Retorna:
        float: Número de permutações distintas possíveis.
    """
    return fatorial(n) / (fatorial(n1) * fatorial(n2))

Vamos testar?

permutacao_repeticao(7,4,3)

35.0

Interessante, certo? Parece tudo OK. Ah, mas temos um pequeníssimo detalhe ainda... 35.0 é um número inteiro para o computador?? Sabemos que não (verifique). Então, o que aconteceu?

Note que ao fazermos fatorial(n) / ( fatorial(n1)*fatorial(n2) ), o computador usou a divisão /, a qual produz um resultado do tipo float (em Python 3). Para corrigir este ponto, podemos usar um operador de divisão inteira

def permutacao_repeticao(n, n1, n2):
    """Calcula o número de permutações com repetição.

    Considera n elementos, dos quais n1 e n2 são repetidos.

    Parâmetros:
        n (int): Número total de elementos.
        n1 (int): Quantidade de repetições do primeiro tipo.
        n2 (int): Quantidade de repetições do segundo tipo.

    Retorna:
        flointat: Número de permutações distintas possíveis.
    """
    return fatorial(n) // (fatorial(n1) * fatorial(n2))

Vamos testar de novo?

permutacao_repeticao(7,4,3)

35

Agora sim! Temos um resultado inteiro.

A solução “mais fácil”¶

Graças a vários desenvolvedores e programadores, muitas coisas já estão prontas para nosso uso. Em Python, podemos calcular o fatorial de um número inteiro diretamente através da biblioteca de matemática usando a função factorial. Para isso, devemos fazer o seguinte.

from math import factorial

A linha de código acima diz, literalmente: “importe a função factorial do módulo math”. Valendo-se disto, podemos reescrever a nossa função de permutação da seguinte forma:

def permutacao_repeticao(n, n1, n2):
    """Calcula o número de permutações com repetição.

    Considera n elementos, dos quais n1 e n2 se repetem.
    Utiliza o operador de divisão inteira (//) e a função math.factorial.

    Parâmetros:
        n (int): Número total de elementos.
        n1 (int): Quantidade de repetições do primeiro tipo.
        n2 (int): Quantidade de repetições do segundo tipo.

    Retorna:
        int: Número de permutações distintas possíveis.
    """
    from math import factorial
    return factorial(n) // (factorial(n1) * factorial(n2))

Já aprendemos bastante coisa até aqui. Vamos prosseguir com um passo a mais e “generalizar” um pouco o que implementamos.

O problema genérico¶

O problema acima torna-se mais genérico quando impomos mais “opções”. Então, se estendêssemos o número de direções, poderiamos montar o problema como:

P_{n}^{n_1,n_2,\ldots,n_f} = \frac{n!}{n_1!n_2!\ldots n_f!}.

(5)

Valendo-se da função importada factorial, podemos criar uma nova função da seguinte forma:

from math import factorial
from numpy import prod

def permutacao_repeticao_generalizada(n, N):
    """Calcula o número de permutações com repetição generalizada.

    Considera n elementos, dos quais N = [n1, n2, ..., nf] se repetem.
    Utiliza o operador de divisão inteira (//), math.factorial e numpy.prod.

    Parâmetros:
        n (int): Número total de elementos.
        N (list[int]): Lista com as quantidades de repetições de cada tipo.

    Retorna:
        int: Número de permutações distintas possíveis.
    """
    f = [factorial(i) for i in N]
    p = factorial(n) // prod(f)
    return p

Na função acima, generalizamos os elementos de repetição através de um tipo de dado list e computamos o denominador como um produto dos n elementos em N. Por exemplo:

N = [3,2,1]
permutacao_repeticao_generalizada(6,N)

np.int64(60)