Buscar

LK-Fund.CC-Combinatoria.pdf

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

Fundamentos Matema´ticos para Computac¸a˜o
Sistemas de Informac¸a˜o
Luis Antonio Kowada
UFF-Instituto de Computac¸a˜o
2017-2
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 1 / 9
Ana´lise Combinato´ria
Conceitos e propriedades importantes
Definic¸a˜o
Fatorial de n ∈ N, denotado por n!, e´ o valor dado pela seguinte expressa˜o
n! =

1 se n = 0
1 se n = 1
n · (n − 1)! se n > 1
.
De forma equivalente temos que
0! = 1
n! = Πni=1i
= 1 · 2 · 3 · · · (n − 1) · n.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 2 / 9
Ana´lise Combinato´ria
Conceitos e propriedades importantes
Lembrete
Uma Permutac¸a˜o de um conjunto A e´ uma bijec¸a˜o de A para A.
Proposic¸a˜o
Dado um conjunto A finito, seja n = |A|, tem-se que exisitem n! poss´ıveis
permutac¸o˜es de A.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 3 / 9
Ana´lise Combinato´ria
Conceitos e propriedades importantes
Princ´ıpio multiplicativo
Se existem n1 poss´ıveis resultados para um primeiro evento e n2 para um
segundo, enta˜o existem n1 · n2 resultados poss´ıveis para a sequeˆncia dos
dois eventos.
Princ´ıpio aditivo
Se A e B sa˜o eventos disjuntos com n1 e n2 resultados poss´ıveis,
respectivamente, enta˜o o nu´mero total de possibilidades para o evento A
ou B e´ n1 + n2.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 4 / 9
Ana´lise Combinato´ria
Conceitos e propriedades importantes
Princ´ıpio das casas de pombo
Se mais de k itens sa˜o colocados em k caixas, enta˜o pelo menos uma
caixa possui mais de um item.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 5 / 9
Ana´lise Combinato´ria
Conceitos e propriedades importantes
Definic¸a˜o
Dado um conjunto A, chama-se arranjo com repetic¸a˜o de A, tomado r a r ,
a qualquer r -upla ordenada de A× A× · · · × A.
A quantidade de poss´ıveis arranjos com repetic¸a˜o de um conjunto com n
elementos tomados r a r e´ ARn,r = n
r .
Definic¸a˜o
Dado um conjunto A, chama-se arranjo sem repetic¸a˜o de A, tomado r a r ,
a qualquer r -upla ordenada de A× A× · · · × A, formada por elementos
distintos.
A quantidade de poss´ıveis arranjos sem repetic¸a˜o de um conjunto com n
elementos tomados r a r e´ ASn,r =
n!
(n−r)! .
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 6 / 9
Ana´lise Combinato´ria
Conceitos e propriedades importantes
Definic¸a˜o
Seja A um conjunto com n elementos, chama-se combinac¸a˜o dos n
elementos, tomado r a r , a qualquer sub-conjunto de A que possua r
elementos.
A quantidade de poss´ıveis combinac¸o˜es de um conjunto com n elementos
tomados r a r e´
(
n
r
)
:= Cn,r =
n!
r !(n−r)! .
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 7 / 9
Ana´lise Combinato´ria
Triaˆngulo de Pascal
(
0
0
)
(
1
0
)(
1
1
)
(
2
0
)(
2
1
)(
2
2
)
(
3
0
)(
3
1
)(
3
2
)(
3
3
)
...(
n
0
)
· · ·
(
n
n
)
...
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 8 / 9
Ana´lise Combinato´ria
Algumas propriedades
1
(
n
0
)
=
(
n
n
)
= 1
2
(
n
1
)
=
(
n
n − 1
)
= n
3
(
n
r
)
=
(
n
n − r
)
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 9 / 9
	Análise Combinatória

Outros materiais