Contagem, permutações e combinação
16 pág.

Contagem, permutações e combinação


DisciplinaFundamentos de Teoria da Computação128 materiais529 seguidores
Pré-visualização6 páginas
Contagem, permutac¸o\u2dces e combinac¸a\u2dco
Edna A. Hoshino
Facom - UFMS
junho de 2015
E. Hoshino (Facom-UFMS) Contagem junho de 2015 1 / 63
To´picos
1 Contagem
Princ´\u131pios Ba´sicos de Contagem
Princ´\u131pio da Inclusa\u2dco-Exclusa\u2dco
Princ´\u131pio da Casa dos Pombos
2 Permutac¸a\u2dco e combinac¸a\u2dco
Permutac¸o\u2dces
Combinac¸a\u2dco
Permutac¸o\u2dces e Combinac¸o\u2dces Generalizadas
3 Coeficientes Binomiais
4 Relac¸o\u2dces de Recorre\u2c6ncia
E. Hoshino (Facom-UFMS) Contagem junho de 2015 2 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Regra do produto
E´ usada quando um procedimento pode ser quebrado em uma sequ¨e\u2c6ncia
de duas tarefas. Se existem n1 meios de realizar a primeira tarefa e, para
cada um destes meios, existirem n2 meios de realizar a segunda tarefa,
enta\u2dco existem n1n2 meios de realizar o procedimento.
Exemplo 1
Uma pequena empresa com apenas dois empregados, Joa\u2dco e Paulo, alugou
um andar de um pre´dio com 12 salas. De quantas formas diferentes
pode-se associar os empregados a salas diferentes?
O procedimento de associar os empregados a`s salas consiste em associar
uma sala a Joa\u2dco, que pode ser feito de 12 formas, e enta\u2dco associar Paulo a
uma das 11 salas diferentes que a de Joa\u2dco. Pela regra do produto, existem
12x11 = 132 meios de associar as salas aos dois empregados.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 3 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Exemplos
Exemplo 2
As cadeiras de um audito´rio sa\u2dco rotuladas com uma letra e um inteiro
positivo nao excedendo 100. Qual e´ o nu´mero ma´ximo de cadeiras que
podem ser rotuladas desta forma (na\u2dco se admite ro´tulos iguais)?
O procedimento de rotular as cadeiras consiste em associar uma das 26
letras e enta\u2dco associar um dos 100 inteiros poss´\u131veis. Pela regra do
produto existem, no ma´ximo, 26x100 = 2600 ro´tulos diferentes.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 4 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Regra do Produto (cont.)
A regra do produto pode ser estendida para o caso em que o procedimento
consiste em n tarefas consecutivas T1,T2, . . . ,Tn. Pode-se provar por
induc¸a\u2dco matema´tica que se cada tarefa Ti pode ser realizada em mi meios
diferentes depois que as tarefas anteriores foram realizadas enta\u2dco existem
m1m2 . . .mn meios de realizar o procedimento.
Exemplo 3
Quantas cadeias diferentes de 7 bits existem?
Cada cadeia pode ser formada escolhendo-se cada um dos 7 bits por vez.
Cada um dos bits pode ser escolhido de duas formas diferentes, ou seja, 0
ou 1. Logo, pela regra do produto existem 27 = 128 diferentes cadeias de
bits de comprimento 7.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 5 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Exemplos
Exemplo 4
Quantas placas de ve´\u131culos existem se cada placa conte´m uma sequ¨e\u2c6ncia
de 3 letras seguida por 4 d´\u131gitos?
Existem 26 escolhas para cada letra e 10 escolhas para cada um dos
quatro d´\u131gitos. Portanto, pela regra do produto existem
26x26x26x10x10x10x10 = 175.760.000 placas veiculares diferentes.
Exemplo 5
Quantas func¸o\u2dces f : A 7\u2192 B existem se |A| = m e |B | = n?
Cada func¸a\u2dco f associa um elemento do dom´\u131nio a algum dos n elementos
do contra-dom´\u131nio. Logo, pela regra do produto, existem nm func¸o\u2dces
diferentes de A para B .
E. Hoshino (Facom-UFMS) Contagem junho de 2015 6 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Regra da soma
E´ usada quando um procedimento pode ser realizado ou de uma das n1
formas diferentes ou de um dos n2 meios alternativos, onde nenhuma das
n1 formas e´ igual a algum dos n2 meios. Neste caso, existem n1 + n2
meios de realizar o procedimento.
Exemplo 1
Suponha que ou um professor ou um estudante da Faculdade e´ escolhido
para ser representante da Faculdade em um comite\u2c6 da Universidade.
Quantas escolhas diferentes existem para o representante se existem 37
professores e 83 estudantes?
Existem 37 meios de escolher um professor e 83 para um estudante. Como
nenhum professor e´ estudante da faculdade, a regra da soma diz que
existem 37 + 83 meios diferentes para a escolha do representante.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 7 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Exemplos mais complexos
Exemplo 2
Em uma linguagem de programac¸a\u2dco, o nome de uma varia´vel e´ formada
por um ou dois caracteres alfanume´ricos. Ale´m disso, o nome deve
comec¸ar com uma letra e deve ser diferente de 5 palavras reservadas de 2
caracteres. Quantos nomes distintos de varia´veis podem existir nesta
linguagem?
O nome da varia´vel ou e´ formada por 1 letra ou por 2 caracteres sendo o
primeiro obrigatoriamente uma letra. Como os dois casos sa\u2dco exclusivos,
temos pela regra da soma que o total de nomes diferentes e´ n1 + n2, sendo
n1 o total de nomes com 1 letra e n2 o total de nomes formados por 2
caracteres. Temos um total de 26 poss´\u131veis escolhas para a letra logo
n1 = 26. Pela regra do produto, existem 26x36 nomes diferentes formados
por 2 caracteres sendo o primeiro uma letra. Como 5 deles sa\u2dco reservados,
temos que n2 = 26x36 \u2212 5. Logo, existem 26 + 26x36 \u2212 5 nomes
diferentes.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 8 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Mais exemplos
Exemplo 3
Um enderec¸o IP consiste em uma cadeia de 32 bits. Ele comec¸a com um
netid, que identifica a rede, e e´ seguido por um hostid, que identifica um
computador particular da rede. Existem 3 formas de enderec¸amento.
Classe A e´ usada para redes grandes e consiste de um 0 seguido por um
netid de 7 bits e um hostid de 24 bits. Classe B e´ usada para redes de
tamanho moderado e consiste da cadeia 10 seguindo por um netid de 14
bits e um hostid de 16 bits. Classe C e´ usada para redes pequenas e
consiste da cadeia 110 seguindo por um netid de 21 bits e um hostid de 8
bits. Existem outras classes, mas estas sa\u2dco reservadas. O netid 1111111
na\u2dco e´ permitido na classe A e os hostids formados por apenas 0s ou 1s
tambe´m na\u2dco esta\u2dco dispon´\u131veis em qualquer uma das classes. Quantos
enderec¸os de IPs sa\u2dco suportados?
Soluc¸a\u2dco: Exerc´\u131cio!
E. Hoshino (Facom-UFMS) Contagem junho de 2015 9 / 63
Contagem Princ´\u131pios Ba´sicos de Contagem
Mais Exemplos
Exemplo 4
Suponha um sistema que admite senhas de 6 a 8 caracteres, onde cada
caracter e´ uma letra ou um d´\u131gito e senhas sem nenhum d´\u131gito na\u2dco seja
permitido. Quantas senhas diferentes sa\u2dco admitidas neste sistema?
Seja P o total de senhas poss´\u131veis e sejam P6, P7 e P8 o total de senhas
de 6, 7 e 8 caracteres, respectivamente. Pela regra da soma,
P = P6 + P7 + P8. Para calcular P6 e´ mais fa´cil encontrar o total de
senhas formadas por letras e d´\u131gitos, incluindo aqueles com nenhum d´\u131gito
e subtrair destes o total de senhas formadas com nenhum d´\u131gito. Logo,
P6 = 36
6 \u2212 266. Analogamente, P7 = 36
7 \u2212 267 e P8 \u2212 36
8 \u2212 268.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 10 / 63
Contagem Princ´\u131pio da Inclusa\u2dco-Exclusa\u2dco
Princ´\u131pio da Inclusa\u2dco e Exclusa\u2dco
E´ usado nos casos em que uma tarefa pode ser feita em n1 ou em n2
meios, mas alguns de n1 tambe´m esta\u2dco em n2. Nesta situac¸a\u2dco, a regra da
soma na\u2dco pode ser usada!
Consiste em adicionar os meios de realizar n1 e n2 e enta\u2dco subtrair o total
de meios em comum entre n1 e n2.
Exemplo 1
Quantas cadeias de 8 bits que comec¸am com 1 ou que terminam com 00
existem?
Seja n1 as cadeias de 8 bits que comec¸am com 1 e n2 as que terminam
com 00. Note que n1 e n2 te\u2c6m cadeias em comum. Pelo princ´\u131pio da
inclusa\u2dco-exclusa\u2dco, pode-se somar o total de elementos em n1 e em n2 e
subtrair aqueles que esta\u2dco tanto em n1 quanto em n2. Logo, o total de
cadeias e´ 27 + 26 \u2212 25.
E. Hoshino (Facom-UFMS) Contagem junho de 2015 11 / 63
Contagem Princ´\u131pio da Inclusa\u2dco-Exclusa\u2dco
Princ´\u131pio da Inclusa\u2dco e Exclusa\u2dco (cont.)
Note que ja´ hav´\u131amos