ESTATISTICA I STA13813

class: center, middle, inverse, title-slide

.title[
# ESTATISTICA I STA13813
]
.subtitle[
## Análise Combinatória
]
.author[
### Nátaly A. Jiménez Monroy
]
.institute[
### LECON/DEST - UFES
]

---

[//]: <> (https://pkg.garrickadenbuie.com/extra-awesome-xaringan/intro/index.html#1)
[//]: <> (https://pkg.garrickadenbuie.com/xaringanthemer/articles/xaringanthemer.html)
[//]: <> (https://www.biostatistics.dk/talks/CopenhagenRuseRs-2019/index.html#1)
[//]: <> (https://rstudio-education.github.io/sharing-short-notice/#1)
[//]: <> (https://www.kirenz.com/slides/xaringan-demo-slides.html#1)
[//]: <> (https://github.com/yihui/xaringan/issues/26)
[//]: <> (https://github.com/emitanaka/anicon)
[//]: <> (https://github.com/mitchelloharawild/icons)
[//]: <> (https://slides.yihui.org/2020-genentech-rmarkdown.html#1)
[//]: <> (https://github.com/gadenbuie/xaringanExtra)
[//]: <> (class: center, middle, animated, slideInRight)

class: animated, slideInRight

# Análise Combinatória - I

| ✍️ **O que é análise combinatória?** |            |
|:-------------------------------------:|
| É um ramo da Matemática que permite resolver problemas envolvendo contagem, como o número de possibilidades de ocorrência de um evento, o número de subconjuntos de um conjunto finito, mas sem que seja necessário recorrer a contagem direta; em outras palavras, sem enumerar seus elementos. |

`$\phantom{****}$`

Dois tipos de problemas que frequentemente aparecem em análise combinatória:

* Demonstrar a existência de conjuntos finitos.
 
 * Contar e classificar os subconjuntos de um conjunto finito.

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

# Análise Combinatória - II

|❗  Importante   |
|:--------------------------|
| Embora a Análise Combinatória disponha de técnicas gerais que permitam atacar alguns problemas, é verdade que a solução de um problema de Análise Combinatória exige, quase sempre, engenhosidade e a compreensão plena da situação descrita pelo problema. |

`$\phantom{***}$`

| 📝 Definição 23 |
|:---------------------------|
| A primeira técnica matemática que aprendemos é a **contagem**. Em outras palavras, enumerar os elementos de um conjunto de forma a determinar quantos elementos ele possui.|

`$\phantom{***}$`

| ✍️ Nota |
|:-------------------|
| O símbolo **#A** será usado para representar o número de elementos de um conjunto `$A$`, isto é, a *cardinalidade* de A. |

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Princípio Aditivo

| 📝 Definição 24 |
|:---------------------------|
| Se **A** e **B** são dois conjuntos disjuntos (intersecção vazia), com *p* e *q* elementos, respectivamente, então a cardinalidade de `$A\cup B$` é dada por *p + q* elementos.|

#### Exemplo 10

Numa classe existem 18 rapazes e 12 garotas. De quantas maneiras podemos selecionar 1 estudante?

#### Exemplo 11

Em uma viagem, podemos escolher entre os meios de transporte de ônibus ou de trem. Se existem 3 rodovias e 2 ferrovias, quantos caminhos disponíveis há para a viagem?

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Princípio Fundamental da Contagem ou Princípio Multiplicativo - I

| 📝 Definição 25            |
|:---------------------------|
| Se uma decisão `$\bf\color{orange}{D_1}$` pode ser tomada de `$\color{orange}{x}$` maneiras e se, uma vez tomada a decisão `$\bf\color{orange}{D_1}$`, a decisão `$\bf\color{orange}{D_2}$` puder ser tomada de `$\color{orange}{y}$` maneiras, então o número de maneiras de se tomarem as decisões `$\bf\color{orange}{D_1}$` e `$\bf\color{orange}{D_2}$` é `$\color{orange}{x y}$`. |

#### Exemplo 12 - I

Maria vai sair com suas amigas e, para escolher a roupa que usará, separou 2 saias e 3 blusas. De quantas maneiras ela pode se arrumar?

Duas decisões precisam ser tomadas: qual blusa `$({\bf\color{orange}{D_1}})$` e qual saia `$({\bf\color{orange}{D_2}})$` usar:

- `$\bf\color{orange}{D_1}$`: escolher uma dentre as 3 blusas

- `$\bf\color{orange}{D_2}$`: escolher uma dentre as 2 saias.

Assim, Maria dispõe de `$3 \times  2 = 6$` maneiras de tomar as decisões `$\bf\color{orange}{D_1}$` e `$\bf\color{orange}{D_2}$`, ou seja, 6 possibilidades diferentes de se vestir.

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Princípio Fundamental da Contagem ou Princípio Multiplicativo - II

#### Exemplo 12 - II

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Princípio Fundamental da Contagem ou Princípio Multiplicativo - III

#### Exemplo 12 - III

Diagrama de árvore:

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

#### Exemplo 13

Numa sala há 3 homens e 4 mulheres. De quantos modos é possível selecionar um casal homem-mulher?

#### Exemplo 14

Uma bandeira é formada por 7 listras que devem ser coloridas usando-se apenas as cores verde, azul e cinza. Se cada listra deve ter apenas uma cor e não podem ser usadas cores iguais em listras adjacentes, de quantos modos se pode colorir a bandeira?

#### Exemplo 15

Quantos são os números de 3 dígitos distintos?

#### Exemplo 16

De quantos modos 3 pessoas podem sentar em 5 cadeiras colocadas em fila?

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Princípio Fundamental da Contagem ou Princípio Multiplicativo - IV

|❗  Importante   |
|:--------------------------|
| Você deve ter percebido que a estratégia adotada é a essência dos problemas de combinatória; para isso é preciso quase sempre de:|
|    |
| **Postura**: devemos sempre nos colocar no papel da pessoa que deve fazer a ação. No exemplo 12, no lugar da pessoa que irá se vestir; no exemplo 14 no lugar da pessoa que irá colorir as listras da bandeira, por exemplo. **Divisão**:  sempre que possível, dividir as decisões a serem tomadas em decisões mais simples. Formar um casal foi dividido em escolher o homem e escolher a mulher. |

> Alguns problemas de Análise Combinatória aparecem com bastante frequência na literatura.
>
> * Embora eles sejam meras aplicações do Princípio Multiplicativo, vale a pena saber como esses procedimentos funcionam particularmente. 
>
> * São eles: permutação/arranjo e combinação

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Permutações e arranjos - I

Suponha que nós temos `$n$` objetos **diferentes**. De quantas maneiras podemos ordenar estes objetos?

Para os objetos **a**, **b** e **c** temos as seguintes ordenações:

`$$\begin{equation*}
\left\{
\begin{array}{cccc}
a & b & c  & \\
a & c & b  & \\
b & a & c  & \\
b & c & a  & \\
c & a & b  & \\
c & b & a  & 
\end{array}
\right.
\end{equation*}$$`

Portanto, há **6** ordenações.

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Permutações e arranjos - II

O número de modos de ordenar `$n$` objetos **distintos** chama-se **Permutação Simples**. Veja que temos:

- `$n$` opções para o 1º objeto que irá compor o conjunto.

- `$n - 1$` opções para o 2º objeto que irá compor o conjunto.

- `$n - 2$` opções para o 3º objeto que irá compor o conjunto, e assim por diante.

Pelo princípio multiplicativo temos que:

`$$n \times (n-1) \times (n-2) \times \cdots \times 1$$`

| 📝 Definição 26 |
|:---------------------------|
| O número de permutações de `$n$` objetos **distintos** é dado por `$n!$` `$\phantom{*************************}$`|

> * `$n! = n (n-1) (n-2) \cdots 1$`.
>
> * Uma notação adotada para fatorial é `${}_n \mathrm{ P }_n$`.

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Permutações e arranjos - III

#### Exemplo 17

Quantos são os anagramas da palavra "PRÁTICO"?

#### Exemplo 18

Quantos são os anagramas da palavra "PRÁTICO" que começam e terminam por consoante?

#### Exemplo 19

De quantos modos 5 rapazes e 5 moças podem se sentar em 5 bancos de dois lugares cada, de modo que em cada banco fiquem um rapaz e uma moça?

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Permutação de elementos nem todos distintos - I

Vamos começar com um exemplo. Quantos anagramas tem a palavra "JACA"?

AAJC AACJ JCAA CJAA AJCA ACJA JAAC CAAJ JACA CAJA AJAC ACAJ

Analisando caso a caso, obtemos 12 anagramas. O que aconteceria se usássemos a fórmula de permutação?

`$${}_4 \mathrm{ P }_4 = 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24.$$`

**Observações:**

* A letra "A" aparece duas vezes e não há distinção entre esses “A”.

* A formula da permutação faz a contagem como se tivéssemos 4 letras **distintas**.

* Sabemos que na troca de um "A" por outro "A" na mesma posição não fornece uma nova composição de palavras. Então existem 2! = 2 trocas que não resultam em nada, logo o número de anagramas da palavra "JACA" é:

$$ \frac{4!}{2!} = \frac{4 \cdot 3 \cdot 2!}{2!} = 12.$$

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Permutação de elementos nem todos distintos - II

| 📝 Definição 27            |
|:---------------------------|
| **Permutações com elementos repetidos**: Temos `$n$` objetos tais que `$n_1$` são do tipo 1, `$n_2$` são do tipo 2, ..., `$n_k$` são do tipo `$k$`, tal que `$n_1 + n_2 + \cdots + n_k = n$`. O número de permutações possíveis é dado por: `$${}_n \mathrm{ P }_n^{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!}.$$`|

#### Exemplo 20

Quantos são os anagramas da palavra "MATEMÁTICA", desconsiderando o acento na letra "A"?

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Arranjo

Considere novamente `$n$` objetos **distintos** do conjunto. Agora desejamos escolher *r* desses objetos, `$0 \leq r \leq n$` e ordenar os *r* escolhidos.

`$\phantom{*********}$`

| 📝 Definição 28 |
|:---------------------------|
| Um arranjo de `$n$` objetos distintos tomados *distintas* a *distintas* é dado por: `$\phantom{**********************}$`
`$${}_r \mathrm{ P }_n = n \times (n-1) \times (n-2) \times \cdots \times (n - r + 1) = \frac{n!}{(n-r)!}.$$`|

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Combinação - I

* A palavra combinação refere-se a seleção de **r** objetos dentre **n** objetos **distintos**, **sem considerarmos a ordem**.

* Por exemplo, considere os objetos **a**, **b**, **c** e **d**. Seja `$r = 2$`

`$$\begin{equation*}
\left\{
    \begin{array}{lll}
    a & b & \\
    a & c & \\
    a & d & \\
    b & c & \\
    b & d & \\
    c & d & \\
    \end{array}
\right.
\end{equation*}$$`

Como a ordem não importa, **a b** = **b a** e, portanto, contamos uma única vez! Logo, há 6 possibilidades.

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Combinação - II

| 📝 Definição 29 |
|:---------------------------|
| O número de maneiras de se escolher *r* objetos dentre *n* objetos diferentes, sem se considerar a ordem, é chamado de combinação de `$n$` objetos tomados `$r$` a `$r$`, e é dado por: `$$\binom{n}{r} = \frac{n!}{r! (n - r)!}$$`|

#### Exemplo 21

Há 10 estudantes em uma sala. De quantas maneiras pode o professor formar um comitê com 4 estudantes?

#### Exemplo 22

Dos 10 alunos, 6 são homens e 4 são mulheres. De quantas maneiras o comitê pode possuir dois homens e duas mulheres?

---
[//]: <> (class: center, middle, animated, slideInRight/ class: animated slideInRight fadeOutLeft)
class: animated, fadeIn

## Combinação - III

#### Exemplo 23

J, S, R , D e M foram ao cinema. Eles escolheram uma fileira onde haviam exatamente 5 lugares vazios próximos um ao outro.

* De quantas maneiras os amigos podem sentar juntos?
 
 * J e M querem se sentar um ao lado do outro. Quantas são as possibilidades?

#### Exemplo 24

De quantas maneiras podemos escolher 6 pessoas, incluindo pelo menos duas mulheres, em um grupo de 7 homens e 4 mulheres?

---
class: animated, hide-logo, bounceInDown
## Política de proteção aos direitos autorais

> O conteúdo disponível consiste em material protegido pela legislação brasileira, sendo certo que, por ser
o detentor dos direitos sobre o conteúdo disponível na plataforma, o **LECON** e o **NEAEST** detém direito
exclusivo de usar, fruir e dispor de sua obra, conforme Artigo 5o, inciso XXVII, da Constituição Federal
e os Artigos 7o e 28o, da Lei 9.610/98.
A divulgação e/ou veiculação do conteúdo em sites diferentes à plataforma e sem a devida autorização do
**LECON** e o **NEAEST**, pode configurar violação de direito autoral, nos termos da Lei 9.610/98, inclusive podendo
caracterizar conduta criminosa, conforme Artigo 184o, §1o a 3o, do Código Penal.
É considerada como contrafação a reprodução não autorizada, integral ou parcial, de todo e qualquer
conteúdo disponível na plataforma.

.pull-left[
<img src="images/logo_lecon.png" width="50%" style="display: block; margin: auto;" />
]
.pull-right[
<img src="images/logo_neaest.png" width="50%" style="display: block; margin: auto;" />
]

.center[
[https://lecon.ufes.br](https://lecon.ufes.br/)
]

Material elaborado pela equipe LECON/NEAEST: 
Alessandro J. Q. Sarnaglia, Bartolomeu Zamprogno, Fabio A. Fajardo, Luciana G. de Godoi 
e Nátaly A. Jiménez.