Analise combinatoria introdução

UNIVERSIDADE FEDERAL DA BAHIA- UFBA DISCIPLINA: Matemática Discreta I –Prof: Michele Novais

1. FATORIAL
Um professor comprou 5 novos livros e quer colocá-los lado a lado

Análise combinatória- aula 1

em uma estante. Quantos maneiras diferentes existem de colocar os 5 livros? Para o primeiro espaço, existem 5 escolhas possíveis, uma para cada livro. Uma vez colocado o primeiro livro, restam 4 escolhas para o segundo espaço e assim por diante. Então o número de escolhas diferentes é: 5.4.3.2.1 = 120. Este tipo especial de multiplicação tem um símbolo próprio: 5!. De um modo geral se dispomos de um número n, então o produto acima é representado por n! e é lido “ene fatorial”, isto é: n! = n(n - 1)(n - 2) ... 3.2.1 e têm-se também que 0! = 1 A relação n! = n(n -1)! poderá ser útil em algumas situações.

1. INTRODUÇÃO
A combinatória é o ramo da Matemática que trata da contagem. Tratar a contagem é importante, sempre que temos recursos finitos (Quanto espaço um banco de dados consome? Quantos usuários a configuração de um computador pode suportar?) ou sempre que estamos interessados em eficiência (Quantos cálculos um determinado algoritmo envolve?). Problemas de contagem normalmente se resumem em determinar quantos elementos existem em um conjunto finito. Esta questão que parece trivial pode ser difícil de ser respondida. Já respondemos algumas questões do tipo "quantos" — quantas linhas existem na tabela-verdade com n símbolos proposicionais, e quantos subconjuntos existem em um conjunto com n elementos? (Na verdade, como já vimos, essas podem ser a mesma pergunta.)

2. PRINCÍPIO FUNDAMENTAL DA CONTAGEM
Se uma tarefa tem k etapas, e cada etapa pode ser feita de maneiras diferentes, então o número total de alternativas é

n1n2 ...nk

1

2.1. O problema da multiplicação
Resolvemos o problema da tabela-verdade, desenhando uma árvore de possibilidades. Essa árvore sugere um princípio mais geral que pode ser usado para resolver diversos problemas de