2 Análise Combinatória
A análise combinatória é o ramo da matemática que trata de métodos de contagem envolvendo conjuntos ou coleções finitas. As técnicas de combinatória encontram aplicabilidade em diversas áreas tais como ciência da computação, engenharia, estatística, probabilidade, economia e administração. Em probabilidade, as técnicas de análise combinatória são empregadas frequentemente para contabilização de elementos do conjunto \(\Omega\) ou de seus subconjuntos.
Tipos de agrupamento
Arranjo
Combinação
Permutação
Para todos esses agrupamentos há a utilização do fatorial como ferramenta básica. O fatorial de um número natural \(n\) pode ser definido da seguinte forma:
\[ n!=\displaystyle{\prod_{k=1}^{n} k}. \]
Exemplos
\(5!=5\cdot4\cdot3\cdot2\cdot1=120\)
\(12=\frac{4!}{2!}=\frac{4\cdot3\cdot2!}{2!}=4\cdot3\)
Alternativamente, podemos expressar o fatorial de acordo com a seguinte relação
\[ n!=n\cdot(n-1)!\Leftrightarrow(n-1)!= \frac{n!}{n}. \tag{2.1}\]
Logo, pela relação da Equação 2.1, podemos obter sequencialmente os valores dos fatoriais da seguinte forma
\[ \begin{split} 4!=&\frac{5!}{5}=\frac{120}{5}=24\\ \searrow&\\ 3!=&\frac{4!}{4}=\frac{24}{4}=6\\ \searrow&\\ 2!=&\frac{3!}{3}=\frac{6}{3}=2\\ \searrow&\\ 1!=&\frac{2!}{2}=\frac{2}{2}=1\\ \searrow&\\ 0!=&\frac{1!}{1}=\frac{1}{1}=1\\ \end{split} \tag{2.2}\]
Desta relação implica que o fatorial de zero é igual a um, \(0!=1\).
Se uma decisão a pode ser tomada de \(n\) formas e uma decisão b pode ser avaliada de \(m\) maneiras, e sendo todas elas independentes, então o número de agregações possíveis entre as duas decisões é obtido pelo produto de \(n\cdot m\).
Sejam \(A_1\), \(A_2,...A_n\) eventos disjuntos dois a dois e cada conjunto \(A_i\) possui \(a_i\) elementos. O princípio aditivo estabelece a relação
\[ \begin{split} A_1 \cup A_2 \cup \cdots \cup A_n \,\, & \longleftrightarrow \,\, \text{ Conjunção Aditiva 'Ou'}\\ \text{Soma-se} & \longleftrightarrow \,\, a_1+a_2+\cdots +a_n \end{split} \]
O princípio multiplicativo estabelece
\[ \begin{split} A_1 \cap A_2 \cap \cdots \cap A_n \,\, & \longleftrightarrow \,\, \text{ Conjunção Aditiva 'E'}\\ \text{Multiplica-se} \,\, & \longleftrightarrow \,\, a_1\cdot a_2 \cdots a_n \end{split} \]
Exemplo 2.1 Uma empresa de logística deve entregar um produto \(\delta\) (delta) localizado na cidade A com destino a cidade B. Um segundo produto \(\alpha\) (alfa) partindo da cidade A foi demandado, com selo de urgência, para a cidade D. A cidade D encontra-se mais afastada, porém equidistante da cidade B e da Capital.
A cidade A possui 3 vias distintas que se conecta com a Capital. Já a cidade B por ter um polo industrial forte apresenta uma malha com 5 ligações diferentes para a Capital. Existem 2 ligações envolvendo a cidade D tanto com destino a B quanto para a Capital.
Quantas maneiras diferentes a empresa de logística pode planejar a distribuição apenas do produto \(\delta\).
Quantas maneiras diferentes a empresa de logística pode planejar a distribuição de ambos os produtos \(\delta\) e \(\alpha\) sabendo-se da urgência da entrega do produto \(\alpha\).
- Para levar o produto \(\delta\), a distribuidora passará pela capital.
\[ \text{( Vias: Cidade A para Capital )}\times \text{( Vias: Capital para Cidade B )} = 3\times 5 = 15. \]
- Para levar os produtos \(\alpha\) e \(\delta\) a distribuidora irá passar primeiramente na cidade D para entrega de \(\delta\) e posteriormente a cidade B.
\[ \text{(Vias: Cidade A para Capital )}\times\text{(Vias: Capital para Cidade D )} \times \text{(Vias: Cidade D para Cidade B )} = 3\times 2 \times 2 = 12. \]
2.1 Arranjo
Estamos aptos agora a introduzir os tipos de agrupamento, iniciando com os arranjos. Um arranjo pode ser definido da seguinte forma:
Definição 2.1 (Arranjo) Seleção de \(k\) elementos dentre um total de \(n\). Ele representa a quantidade de agrupamento ordenado que é possível formar (\(n>k\))
\[ A_{n,k}=\frac{n!}{(n-k)!}. \]
Dentre as \(k\) seleções, temos para a primeira, \(q_{1,k}\), um total de \(n\) possibilidades. Para a segunda seleção \(q_{2,k}\), temos \(n-1\) possibilidades. Para a terceira \(q_{3,k}\), há \(n-2\) possibilidades. O processo segue até a seleção \(q_{k,k}\) onde temos \(n-k+1\) possibilidades. Sendo todas as seleções independentes, podemos recorrer ao princípio fundamental da contagem, para obter a quantidade de arranjos possíveis. Logo, o número de arranjos \(A_{n,k}\) é computado por \[ \begin{split} A_{n,k} =& n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\cdot\frac{1}{1}\\ =&n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\cdot\frac{(n-k)!}{(n-k)!}\\ =&n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\cdot\frac{(n-k)\cdot(n-k-1)\cdots2\cdot 1}{(n-k)\cdot(n-k-1)\cdots2\cdot 1}\\ =&\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\cdot(n-k)\cdot(n-k-1)\cdots2\cdot 1}{(n-k)\cdot(n-k-1)\cdots 2\cdot 1}\\ \end{split} \] Na última linha da equação acima, o numerador é \(n!\) e o denominador \((n-k)!\). Portanto, o arranjo de \(n\) tomado a \(k\) é dado por
\[ A_{n,k}=\frac{n!}{(n-k)!}. \]
Um ponto importante que cabe ressaltar é que no arranjo a ordem dos elementos é fundamental. Para melhor entendermos a ideia de uma arranjo, vamos considerá-lo dentro de um contexto aplicado. Considere o exemplo abaixo que trata de uma empresa interessada nas possibilidades de se fazer investimentos.
Exemplo 2.2 Um fundo de investimento em private equity possui um pipeline composto de 10 startups. Ao montar um ranking delas, somente as três mais promissoras irão receber um aporte financeiro. A primeira irá receber o valor de 5 milhões, a segunda 3 milhões a a terceira colocada o total de 1 milhão. De quantas maneiras o fundo poderá realizar os investimentos antes de estabelecer o ranking?
A empresa tem um total de \(n=10\) startups e precisa selecionar \(k=3\). Como a ordem é importante em virtude da diferença dos recursos investidos então a quantidade de interesse é um arranjo \(A_{10,3}\). Portanto,
\[ \begin{split} A_{10,3}&=\frac{10!}{(10-3)!}=\frac{10!}{7!}\\ &=\frac{10\cdot9\cdot8\cdot7!}{7!}=10\cdot9\cdot8\\ &=720. \end{split} \]
2.2 Combinação
O segundo tipo de agrupamento é a combinação. Este agrupamento é muito similar ao arranjo. No entanto, diferentemente do arranjo para a combinação a ordem não é importante. Como a ordem não importa, então em termos da teoria de conjuntos os elementos do conjunto na combinação é não ordenado. Uma combinação pode ser definida da seguinte forma:
Definição 2.2 (Combinação) A combinação simples \(C_{k,n}\) de elementos tomado \(k\) a \(k\) dentre um total de \(n\) (\(k\leq n\)). Ele representa a quantidade de agrupamento não ordenado que é possível formar
\[ C_{k,n}=\frac{n!}{(n-k)!\cdot k!} \]
Em um arranjo de \(n\) elementos tomados \(k\) a \(k\) contabilizamos os diversos ordenamentos de grupos de \(k\) elementos possíveis. Para cada arranjos \(\boldsymbol{a}_{k,n}=a(a_{1,k},a_{2,k},...,a_{k,k})\) toda a troca de posições dentro de um mesmo arranjo \(\boldsymbol{a}_{k,n}\) é contabilizada. Logo, para cada um arranjo temos \(k!\) possíveis ordenamentos. Como para a combinação as posições são indiferentes então basta descontar os ordenamentos dentre de cada arranjo. Portanto,
\[ \begin{split} C_{n,k}=&\frac{A_{n,k}}{k!}\\ =&\frac{n!}{(n-k)!\cdot k!}. \end{split} \]
Para compreender melhor a ideia de combinação, vamos ver os seguintes exemplos.
Exemplo 2.3 Para comemorar o sucesso em vendas de uma corretora de imóveis, a empresa decidiu sortear, entre os 10 funcionários que mais venderam, 4 deles para viajarem para a cidade de Caldas Novas-GO, com a sua família e todas as despesas pagas. Quantos resultados distintos podemos ter com esse sorteio?
Como a ordem não importa, visto que não faz diferença quem foi o primeiro, segundo etc. Portanto,
\[ \begin{split} C_{10,4}&=\frac{10!}{(10-4)!4!}=\frac{10!}{6!\cdot4!}\\ &=\frac{10\cdot9\cdot8\cdot7\cdot6!}{6!\cdot4!}=\frac{10\cdot9\cdot8\cdot7}{4\cdot3\cdot2\cdot1}\\ &=10\cdot3\cdot7=210 \end{split} \]
Exemplo 2.4 Quantas comissões de 4 elementos podemos formar com 20 alunos de uma turma?
As comissões não possuem ordenamento entre os membros, portanto estamos interessados nas combinações das comissões. Portanto,
\[ \begin{split} C_{20,4}&=\frac{20!}{(20-4)!\cdot4!}=\frac{20!}{16!\cdot4!}\\ &=\frac{20\cdot19\cdot18\cdot17\cdot16!}{16!\cdot4!}=\frac{20\cdot19\cdot18\cdot17}{4\cdot3\cdot2\cdot1}\\ &=19\cdot17\cdot5\cdot3=210 \end{split} \]
2.3 Permutação
2.3.1 Permutação Simples
As permutações são agrupamentos ordenados, em que o tamanho do agrupamento é o mesmo da quantidade de elementos totais disponíveis. Para calcular a permutação \(P_{n}\) de \(n\) elementos, aplicamos simples o fatorial \[ P_{n}=n! \]
Exemplo 2.5 De quantas maneiras 5 pessoas podem se organizar em uma fila?
As comissões não possuem ordenamento entre os membros, portanto estamos interessados nas combinações das comissões. Portanto, \[ P_{n}=5!=120 \]
Exemplo 2.6 Quantos anagramas existem na palavra ALUNO?
\[ P_{n}=5!=120 \] ONULA, LAONU, ALNUO, OUALN,…
Quando ocorre elementos repetidos entre todos os elementos disponíveis, a utilização de permutação simples levará a resultados errôneos. Por exemplo, a palavra ALAH possui uma permutação ALAH tal que conduz ao mesmo resultado. Quando há elementos repetidos nesse conjunto, temos uma permutação com repetição. Para calcular a quantidade de permutações com repetição de um conjunto com \(n\) elementos, calculamos a permutação de \(n\) e dividimos pelo produto do fatorial de quantas vezes cada um dos elementos se repete. Isso é representado pela seguinte fórmula: \[ P_{n}^{r_1,r_2,\cdots r_{i}}=\frac{n!}{r_1!\cdot r_2!\cdots r_{k}!} \]
Quantos anagramas existem na palavra ANAKIN?
\[ \begin{split} P_{6}^{2,2}=&\frac{6!}{2!\cdot2!}\\ =&\frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{4}\\ =&6\cdot5\cdot3\cdot2=180 \end{split} \]
2.3.2 Permutação Círculo e Anel
Um caso especial é a permutação em que os elementos disponíveis estão dispostos em forma circular. Na permutação circular, a ordem em que estão dispostos os elementos no ciclo importa. No círculo a posição do elemento não importa, visto que uma mera rotação do círculo não conduz a uma nova ordenação. Para calcular a permutação em um círculo, utilizamos a fórmula:
\[ PC_{n}=(n-1)! \] calcular a permutação em um anel, utilizamos a fórmula: \[ PR_{n}=\frac{(n-1)!}{2} \]
Exemplo 2.7 De quantas maneiras podem se distribuir 5 crianças em uma roda?
\[ PC_{5}=(5-1)!=4!=24 \]
2.3.3 Permutação Anel
2.3.4 Permutação Caótica
Uma permutação de \(n\) elementos de um conjunto é chamada de permutação caótica, quando nenhum dos elementos da permutação está na posição original e é denotada por \(D_{n}\). Em outras palavras uma permutação dos elementos \(a_1,a_2,...,a_n\) é considerada caótica quando nenhum dos \(a_i's\) se encontra na \(i\)-ésima posição. Uma permutação caótica pode ser computada da seguinte forma:
Definição 2.3 (Arranjo) O número de permutações caóticas de um conjunto com \(n\) elementos distintos, pode ser calculada da seguinte maneira: \[ D_n=n!\cdot\sum_{i=0}^{n}\dfrac{(-1)^i}{i!}. \]
Considere todas as permutações dos elementos \(a_1,a_2,...,a_n\). Indicando por \(A_{i}\) todas as permutações formadas estes elementos onde \(a_{i}\) está em sua posição original, isto é, na \(i\)-ésima posição. A partir da lista composta de todas as permutações \(n!\) iremos retirar as permutações \(\boldsymbol{b}_{j}\) em que uma das suas posições dos elementos encontram na posição original. Para tal considere \(B\) o conjunto de todas permutações distintas \(\boldsymbol{b}_{j}\), com \(j=1,2,...,m\). Logo a permutação caótica é dada por \[ \begin{split} D_{n}=&n!-m\\ \end{split} \] Para \(b_{j}\in B \Leftrightarrow b_{j}\in (A_{1}\cup A_{2}\cup ...\cup A_{n})\). Pelo princípio da aditividade basta somarmos a quantidade de elementos de cada um dos conjuntos \(A_{i}\). No entanto, não podemos empregar o princípio diretamente uma vez que os conjuntos não são disjuntos. Em outras palavras, a soma irá conduzir a contagem de itens mais de uma única vez. Uma maneira de contornar tal problema é retirar os conjuntos em que foram contabilizados mais de uma vez. Iremos também repor os conjuntos em foram retirados mais de uma vez. Desta forma segue-se que
\[ \begin{split} D_{n}=&n!-\#(B)\\ =&n!-\#(A_1\cup A_2\cup \cdots \cup A_n)\\ = & ~ n! - \sum_{i=1}^{n}\#A_i + \sum_{0\lt i\lt j\leq n}\#(A_i\cap A_j)+\cdots \\ =& \quad \cdots +(-1)^{n-1}\#(A_1\cap A_2\cap \cdots\cap A_n). \end{split} \]
O símbolo \(\#W\) denota a quantidade de elementos pertencentes ao conjunto \(W\). Visto que existem \(n\) termos no primeiro somatório, \(C_{2,n}\) termos no segundo, \(C_{3,n}\) termos no terceiro, e assim por diante onde no último \(C_{n,n}=1\). Além disso
\[ \begin{split} \#(A_i) & = (n-1)! \\ \#(A_i\cap A_j) & = (n-2)! \\ \#(A_i\cap A_j\cap A_k) & = (n-3)! \\ \vdots ~~~~~~~~ & = ~~~~~~ \vdots \\ \#(A_1\cap A_2\cap\cdots\cap A_n) & = 1 \end{split} \] Rearranjo os termos \[ \begin{split} D_n &= ~ n!-n\cdot(n-1)!+C_n^2\cdot(n-2)!-C_n^3\cdot(n-3)!+\cdots +(-1)^n\cdot 1 \\ &= ~ n!-\dfrac{n!}{1!}+\dfrac{n!}{2!}-\dfrac{n!}{3!}+\cdots +(-1)^n\cdot \dfrac{n!}{n!} . \end{split} \] Evidenciando \(n!\), obtém-se:
\[ \begin{split} D_n & = ~ n!\cdot\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+(-1)^n\cdot \dfrac{1}{n!}\right) \\ & = ~ n!\cdot\sum_{i=0}^{n}\dfrac{(-1)^i}{i!}. \end{split} \]