Princípios matemáticos
Listas
Ao se deparar com um problema de contagem, normalmente será preciso determinar quantos elementos existem em um conjunto finito. Determinar essas quantidades de recursos finitos podem gerar questões difíceis de serem respondidas (GERSTING, 2017). Por isso, vamos inicialmente nos familiarizar com o conceito de lista.
Uma lista é uma sequência ordenada de objetos (SCHEINERMAN, 2015). Costumamos representar uma lista abrindo parênteses e apresentando cada elemento da lista, separando-os por vírgula. Por exemplo, a lista (2, 4, 8, 16) é uma lista cujo primeiro elemento é o número 2, o segundo elemento é o número 4, o terceiro elemento é o número 8 e o quarto elemento é o número 16. A ordem com a qual os elementos figuram na lista é significativa. Assim, a lista (2, 4, 8, 16) não é a mesma que a lista (4, 2, 16, 8). Embora os elementos que compõem a lista sejam os mesmos, a forma pela qual foram arranjados (ordem) é diferente. Também é importante destacar que uma lista pode conter elementos repetidos, como (3, 4, 5, 5, 6), em que o número 5 aparece duas vezes.
Em uma lista, chamamos de comprimento ao número de elementos que a compõe. Quando a lista tem apenas dois elementos ela recebe o nome de par ordenado. E uma lista vazia é uma lista cujo comprimento é igual a zero.
Outro tipo de lista que podemos ter, são listas de dois elementos em que há n escolhas para o primeiro elemento e, para cada uma dessas escolhas, há m escolhas do segundo elemento. Então o número de tais listas é n×mn×m.
Um caso especial envolvendo a contagem de listas consiste no problema de se determinar quantas listas de comprimento n extraídas de um universo de n objetos, em que não se permitem repetições, podem ser formadas. Em outras palavras, de quantas maneiras diferentes podemos dispor n objetos em uma lista, usando cada objeto exatamente uma única vez?
Podemos estender o princípio da multiplicação para listas com dois elementos para esta situação, determinando o total de listas como:
n⋅(n−1)⋅(n−2)…(n−n+1)=n⋅(n−1)⋅(n−2)…(2)⋅(1)n⋅(n−1)⋅(n−2)…(n−n+1)=n⋅(n−1)⋅(n−2)…(2)⋅(1)
Essa expressão ocorre com frequência em matemática e recebe um nome e símbolo especiais: chama-se fatorial de n e representamos por n!n!. Por exemplo, 6!=6⋅5⋅4⋅3⋅2⋅1=7206!=6⋅5⋅4⋅3⋅2⋅1=720. Por definição, considera-se que 1!=11!=1 e 0!=10!=1 (SCHEINERMAN, 2015).
Árvore de decisão
Outra forma de representarmos os possíveis resultados de uma ordenação (listas) é a utilização de um diagrama chamado Árvore de Decisão. Uma árvore de decisão é uma estrutura hierárquica que representa um mapeamento de possíveis resultados de uma série de escolhas relacionadas. A árvore de decisão é uma importante ferramenta para auxiliar na tomada de decisões, bem como visualizar as ramificações e as consequências. Elas podem ser usadas tanto para conduzir diálogos informais quanto para mapear um algoritmo que prevê a melhor decisão (escolha), matematicamente, além de auxiliar na criação de planos de ação.
Em geral, uma árvore de decisão inicia a partir de um único nó de origem (chamado de nó raiz), que se divide em possíveis resultados. O nó raiz é representado por um elemento no topo da árvore e representa o todo ou uma amostra de alguma categoria e expressa nós de decisão, em que, a partir do nó raiz, temos ramificações que levam a escolhas de um resultado (decisão).
Combinatória
Em Combinatória, existem diferentes tipos de agrupamentos (ordenados ou não) que recebem os nomes específicos de Arranjos, Permutações e Combinações. Apesar de ser possível determinar esses agrupamentos de maneira intuitiva, existem fórmulas matemáticas que nos auxiliam a realizar essa tarefa. Vamos, então, aprender a utilizá-las, considerando os agrupamentos (Arranjos, Permutações e Combinações) simples, isso é, formados por elementos distintos.
Arranjo
De acordo com Iezzi et al. (2004), dado um conjunto com n elementos distintos, chama-se arranjo dos n elementos, tomados p a p, a qualquer sequência ordenada de p elementos distintos escolhidos entre os n existentes. Para determinar o número de arranjos podemos utilizar a fórmula
Exemplo: Considere o conjunto A={1,2,3,4}A={1,2,3,4}. Vamos determinar o número de arranjos desses quatro elementos (n=4)(n=4) tomados dois a dois (p=2)(p=2). Utilizando a fórmula para determinação do número de arranjos, temos que:
Permutação
Um caso especial de arranjo, denominado permutação, é obtido quando dado um conjunto com n elementos distintos, selecionamos exatamente n elementos para formar a sequência ordenada.
Exemplo: Considere o problema de se determinar de quantas maneiras seis pessoas A, B, C, D, E e F podem ser dispostas em uma fila indiana. Cada maneira de compor a fila é uma permutação das seis pessoas, pois qualquer fila obtida é uma sequência ordenada na qual comparecem sempre as seis pessoas. Ao utilizarmos a fórmula do número de arranjos, percebemos que neste caso n=pn=p.
Ou seja, existem 720 maneiras distintas para organização dessa fila.
Combinação
Há ainda outra forma de agrupamento, denominada combinação, que considera cada sequência obtida como um conjunto não ordenado. Dado um conjunto com n elementos distintos, chama-se combinação dos n elementos, tomados p a p, a qualquer subconjunto formado por p elementos distintos escolhidos entre os n existentes. Para determinar o número de combinações, podemos utilizar a fórmula
Exemplo: Considere que dos cinco funcionários A, B, C, D e E de uma empresa do setor de Tecnologia da Informação, três serão promovidos. Queremos determinar todas as combinações desses cinco funcionários, tomados dois a dois. Podemos calcular o número de combinações utilizando a fórmula
