Análise Combinatória

Ao fim da postagem, coloquei alguns exercícios propostos. Recomendo que tentem fazer, e após isso, acessem este link para conferir as resoluções.

----------------------------------------------------------------------------------------------------------------------------------------------------

Introdução

A Análise combinatória tem aplicações em vários tópicos da Matemática como a probabilidade e a estatística e é muito útil em outros campos, como a programação de computadores, a concepção de experiências, a biologia molecular, a economia, a cristalografia, a geometria combinatória, a teoria dos grafos, a teoria da programação (scheduling theory) para o bom funcionamento de uma empresa, a lógica etc. é, como se vê, um assunto de grande importância.
Vamos iniciar esse estudo resolvendo os seguintes problemas:

1°) Uma urna contém 3 bolas: Uma azul, uma preta e uma vermelha. De quantas maneiras diferentes podemos retirar as 3 bolas sucessivamente, sem reposição?
Usando A para azul, P para preta e V para vermelha, podemos visualizar todas as maneiras por meio de um recurso chamado árvore de possibilidades:

Contando o número de possibilidades, temos 6 maneiras.

2°) Uma fabrica de automóveis produz veículos de 3 tamanhos diferentes (pequeno, médio e grande), com dois tipos de motores ($M_1$ e $M_2$) e em 3 cores diferentes (vinho, prata e vermelho). Quantas opções tem um comprador?

Contando o número de possibilidades, temos 18 opções de compra.

Como vimos, podemos obter a resposta descrevendo e contando todas as possibilidades. Porém, à medida que o número de possibilidades aumenta, tal método vai se tornando impraticável.
O objetivo da análise combinatória é fornecer métodos e fórmulas que nos permitem calcular, em vários tipos de problemas, o número de possibilidades, sem que seja preciso descrevê-las ou enumerá-las.

1. Princípio Fundamental da Contagem

Na resolução do primeiro problema, de acordo coma árvore de possibilidades, observamos duas etapas:

1° etapa: Retirada da 1° bola --> 3 maneiras;

2° etapa: Retirada da 2° bola --> 2 maneiras.

Como resultado da 3° retirada fica determinado pelo resultado da 2°, temos somente duas etapas.

Para cada bola que retiramos na 1° etapa podemos retirar qualquer das duas bolas restantes na 2° etapa, portanto, o número total de possibilidades é o produto:

$$3 \cdot 2=6$$

No segundo problema, temos 3 etapas:

1° etapa: Escolha do tamanho --> 3 opções;

2° etapa: Escolha do motor --> 2 opções;

3° etapa: Escolha da cor --> 3 opções.

O comprador pode escolher qualquer um entre os 3 tamanhos e, para cada tamanho escolhido, pode optar por qualquer dos dois tipos de motor e, ainda, para cada tamanho e tipo de motor escolhidos, decidir por quaisquer das 3 cores oferecidas. Assim, o número total de possibilidades é o produto:

$$3\cdot 2 \cdot 3=18$$

Esse método, em que multiplicamos o número de possibilidades de cada etapa, é chamado de princípio fundamental da contagem ou regra do produto. Podemos enunciá-lo assim:

Se um evento (ou fato) ocorre em $n$ etapas consecutivas e independentes, de maneira que o número de possibilidades:

Na primeira etapa é $k_1$,

Na segunda etapa é $k_2$,

Na terceira etapa é $k_3$,

Na enésima etapa é $k_n$,

Então, o número total de possibilidades de ocorrer o referido evento é o produto:

$$k_1\cdot k_2\cdot k_3\cdots k_n$$

2. Fatorial

Sendo $n \in N$ e $n>1$, definimos fatorial como o produto de $n$ números naturais consecutivos de 1 até $n$ e indicamos $n!$.

Em símbolos:

$$n!=1\cdot 2 \cdot 3\cdots (n-2)\cdot (n-1)\cdot n$$

De modo geral, podemos escrever:

$$n!=(n-1)!\cdot n$$

Essa segunda expressão, nos remete a duas considerações:

Se $n=2$, temos $2!=(2-1)! \cdot 2$ ou $1!\cdot 2$, o que nos sugere a seguinte definição:

$$1!=1$$

Se $n=1$, temos $1!=(1-1)\cdot 1$ ou $0! \cdot 1$, o que nos sugere a seguinte definição:

$$0!=1$$

3. Arranjos Simples

Vamos dar uma ideia do que seja um arranjo simples através dos seguintes exemplos:

1°) Consideremos o conjunto $A={a,b,c}$ e os seguintes agrupamentos de 2 elementos de A, esquematizados na árvore de possibilidades:

Esses agrupamentos diferem entre si ou pela natureza ($ab$ e $ac$, por exemplo) ou pela ordem ($ab$ e $ba$, por exemplo) de seus elementos e são chamados arranjos simples dos 3 elementos de A, tomados 2 a 2.

O termo simples significa que não há repetição de elementos em cada arranjo.

O número de arranjos é indicado por $A_{3,2}$. Note que, observando a árvore de possibilidades ou aplicando a regra do produto, temos $A_{3,2}=3\cdot 2=6$.

2°) Seja o conjunto $A={1,3,5,7}$ e os seguintes agrupamentos de 3 elementos de A esquematizados na árvore de possibilidades

Esses agrupamentos diferem entre si ou pela natureza (135 e 173, por exemplo) ou pela ordem (371 e 137, por exemplo) de seus elementos e são arranjos simples dos 4 elementos de A, tomados 3 a 3.

Note que, observando a árvore de possibilidades ou aplicando a regra do produto, teremos $A_{4,3}=4\cdot 3\cdot 2=24$.

Podemos agora, definir:

Sendo A um conjunto com $n$ elementos distintos e $p$ um número natural, de modo que $p \leq n$, chamamos de arranjos simples dos $n$ elementos de A, tomados $p$ a $p$, os agrupamentos ordenados de $p$ elementos diferentes que é possível formar com os elementos de A.

O número $p$ é chamado de classe ou ordem do arranjo. Indicamos o número de arranjos de $n$ elementos, $p$ a $p$, por $A_{n,p}$ ou $A_n^p$.

Para o cálculo de $A_{n,p}$ podemos usar a seguinte fórmula:

$$A_{n,p}=\frac{n!}{(n-p)!}$$

4. Permutação Simples

Sendo A um conjunto com $n$ elementos distintos, os arranjos simples desses $n$ elementos, tomados $n$ a $n$, são chamados permutações simples.

As permutações são agrupamentos formados pelos mesmos elementos, portanto só diferem entre si pela ordem dos mesmos.

Por exemplo, se $A={1,2,3}$, as permutações simples de seus elementos são 123, 132, 213, 231, 312 e 321.

Indicaremos o número de permutações simples de $n$ elementos por $P_n$.

Pela definição. temos:

$$P_n=A_{n,n}\therefore P_n=\frac{n!}{(n-n)!}\therefore P_n=\frac{n!}{0!}=n!$$

5. Combinações Simples

Vimos que arranjos simples de $n$ elementos distintos de um conjunto A, tomados $p$ a $p$, são agrupamentos que diferem entre si ou pela natureza ou pela ordem de seus elementos e que, quando $n=p$, os arranjos são chamados de permutações simples.

Então, do total de arranjos que podemos formar, existem os que:

Diferem entre si somente pela ordem de seus elementos;

Diferem entre si somente pela natureza de seus elementos.

Os arranjos que diferem entre si somente pela natureza de seus elementos são chamados de combinações simples.

Podemos definir:

Sendo A um conjunto com $n$ elementos distintos e $p$ um número natural de modo que $p \leq n$, chamamos combinações simples dos $n$ elementos, tomados $p$ a $p$, os agrupamentos de $p$ elementos distintos e que diferem entre si somente pela natureza de seus elementos.

O número $p$ é chamado de classe ou ordem da combinação e indicamos o número de combinações de $n$ elementos, $p$ a $p$, por $C_{n,p}$ ou $C_n^p$.

Para o cálculo de $C_n^p$, podemos utilizar a seguinte fórmula:

$$C_n^p=\frac{n!}{p!(n-p)!}$$

----------------------------------------------------------------------------------------------------------------------------------------------------

Exercícios Propostos

1.1)

a) Quantos são os números de 4 algarismos que podemos formar com os algarismos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9?

b) Quantos são os números de 4 algarismos distintos que podemos formar com os algarismos 0, 1, 2, 3, 4, 5. 6, 7, 8 e 9?

1.2) Calcule o total de placas de automóvel, com 3 letras e 4 algarismos, que é possível fabricar com as letras do nosso alfabeto e com os algarismos de 0 a 9.

1.3) Em nosso sistema de numeração, quantos números existem:

a) De 3 algarismos distintos?

b) De 3 algarismos?

c) Pares de 4 algarismos?

1.4) Com os algarismos 1, 2, 4, 7, 8 e 9, quantos números podemos formar:

a) De 4 algarismos distintos?

b) De 3 algarismos e que terminem em 2 ou 8?

c) De 4 algarismos e que comecem por 4 ou 9?

1.5) Com os dígitos 1, 2, 3, 4, 6 e 8 podem-se formar $x$ números ímpares, com 3 algarismos distintos cada um. Determine $x$.

1.6) Um homem possui 5 camisas, 4 calças, 3 paletós e dois pares de sapato. De quantos modos diferentes pode se vestir?

2.1) Calcule $\displaystyle \frac{12!}{10!}$    

2.2) Calcule:

a) $6!$

b) $5!+7!$

c) $\displaystyle \frac{6!+8!}{7!}$

2.3) Simplifique:

a) $\displaystyle \frac{8!}{7!}$

b) $\displaystyle \frac{11!}{12!}$

c) $\displaystyle \frac{9\cdot 10!}{8\cdot 9!}$

3.1) Calcule:

a) $\displaystyle \frac{A_{n,3}}{A_{n,2}}$

b) $\displaystyle A_{7,3}$

c) $\displaystyle A_{10,3}+A_{10,2}$

3.2) Quantas "palavras" (com sentido ou não) de 5 letras distintas podemos formar com as primeiras 20 letras do nosso alfabeto?

4.1) Calcule $\displaystyle \frac{P_5-P_4}{P_3}$

4.2) Determine o número de anagramas da palavra AMOR.

4.3) Quantos anagramas da palavra VESTIBULAR começam e terminam com vogal?

4.4) Quantos anagramas possui a palavra CONTAGEM?

5.1) Calcule o valor de $\displaystyle \frac{C_{8,5}+P_3}{A_5,2}$