Discreta_100812 (1)

Prévia do material em texto

Faculdade de Engenharia 
Departamento de Cadeiras Gerais 
Licenciatura em Engenharia Informática 
 
Matemática Discreta I 
 
 
TEMA: ANÁLISE COMBINTATORIA 
 
Discentes: Docente: 
Falaque, Dalton Gomes Lauter Carmen Nassone Cumbi 
Júnior, Venâncio Salustiano 
Melo, Lucas José 
Machatine, Lélio Leonardo 
Nhamutole, Sérgio Alexandre 
 
Maputo, Abril de 2024 
 
2 
 
. 
Índice 
Introdução ............................................................................................................................................. 3 
Analise Combinatória............................................................................................................................ 4 
Princípio de contagem ........................................................................................................................... 4 
Factorial ................................................................................................................................................ 5 
Arranjos ................................................................................................................................................ 5 
Permutação ........................................................................................................................................... 6 
Combinação .......................................................................................................................................... 7 
Conclusão ............................................................................................................................................. 9 
 Bibliografia ........................................................................................................................................ 10 
 
 
3 
 
 Introdução 
 
Neste trabalho focaremos quatro tipos de agrupamentos: arranjos, factorial, permutações e 
combinações. Qual a diferença entre cada um deles? Esta será uma das principais dúvidas a serem 
sanadas neste trabalho. Veremos que se você possuir n objectos e p lugares disponíveis para guardar 
exactamente 1 desses objectos em cada lugar, isso será um arranjo de n objectos tomados p a p. Em 
particular, se o número de objectos for igual ao número de lugares disponíveis, teremos uma 
permutação de n objectos. Notaremos que nos arranjos, portanto nas permutações, a ordem é importa. 
Contudo, se você possuir n objectos e p e lugares disponíveis, mas a ordem cujos objectos são 
escolhidos não for importante, isso será uma combinação de n objectos tomados p a p. Trataremos 
ainda dos casos cuja escolha repetida de objectos é permitida e também das permutações circulares.
4 
 
 ANALISE COMBINATÓRIA OU CONTAGEM 
Trata da determinação do número de possibilidades lógicas de algum evento sem necessariamente 
identificar todos os casos. 
Princípio de contagem 
Há duas ferramentas importantes para a solução de problemas de problemas de copntagem: O princípio aditivo e o princípio 
multiplicativo 
 
Sejam A e B conjuntos que não possuem elementos em comum. O princípio aditivo garante que o número de 
elementos da união é igual ao número de elementos do conjunto A somado ao número de elementos do conjunto B, 
ou seja, 
n(A ∪ B ) = n(A) + n(B ), quando A ∩ B = ∅. 
Podemos estender o princípio aditivo para um número finito de conjuntos. 
Dados n conjuntos A1, A2, …, An, tais que Ai ∩ A j = ∅ para todo i ≠ j, temos: 
n(A1 ∪ A2 ∪ … ∪ An )= n(A1) + n(A2 ) + ⋯ + n(An). 
Ex: Ana deseja participar da Semana Universitária. Foram oferecidos 3 palestras e 2 seminários que interessavam 
a Ana, todos no mesmo horário. Note que ela tem três maneiras distintas para a escolha da palestra n(P ) = 3 e duas 
maneiras distintas para a escolha do seminário n(S) = 2, como os eventos são mutuamente excludentes, visto 
que Ana não poderá assistir a uma palestra e participar de um seminário que são eventos distintos no mesmo 
horário, o número de possibilidades de escolhas será: 
n(P ) + n(S) = 3 + 2 = 5. 
Dados dois conjuntos A e B, o princípio multiplicativo nos garante que o número de maneiras de escolher um 
primeiro elemento do conjunto A e um segundo elemento do conjunto B é igual ao número de elementos de A 
multiplicado pelo número de elementos de B. Em outras palavras, o número de elementos do produto cartesiano 
de A por B satisfaz: 
n(A ⨯ B ) = n(A) ∙ n(B ). 
Estendendo para um número finito de conjuntos, temos que: 
n(A1 ⨯ A2 ⨯ …⨯ An ) = n(A1) ∙ n(A2 )∙ …∙ n(An ). 
Ex: Os organizadores da Semana Universitária, observando o interesse dos alunos em participar de palestras e 
seminários resolveram oferecer as palestras em um horário e os seminários em outro. Ana poderá participar de 
dois eventos escolher uma palestra e um seminário. Aplicando o princípio multiplicativo temos que ela poderá 
fazer essa escolha de 6 maneiras distintas: 
n(P ) ∙ n(S ) = 3 ∙ 2 = 6. 
5 
 
Existem situações mais complexas em que podemos utilizar simultaneamente os princípios aditivos e 
multiplicativo. 
Ex: Os alunos que apresentarem trabalhos na Semana Universitária serão classificados e premiados com 2 
livros de disciplinas diferentes. Sabemos que existem 7 livros diferentes de informática (I), 4 livros 
diferentes de matemática (M) e 5 livros diferentes de didáctica (D). Ana foi a primeira colocada. Podemos 
determinar o número de escolhas que Ana poderá fazer: Ana poderá escolher as disciplinas de três maneiras 
diferentes: 
 
 Informática e Matemática, pelo princípio multiplicativo: 
n(I ⨯ M ) = n(I ) ∙ n(M ) = 7 ∙ 4 = 28. 
 Informática e Didáctica, pelo princípio multiplicativo: 
n(I ⨯ D ) = n(I ) ∙ n(D ) = 7 ∙ 5 = 35. 
 Matemática e Didáctica, pelo princípio multiplicativo: 
n(M ⨯ D ) = n(M ) ∙ n(D ) = 4 ∙ 5 = 20. 
Utilizando o princípio aditivo determinamos o total de escolhas: 28+35+20=83 possibilidades de escolha 
 
 FACTORIAL 
 Factorial de um número natural n, representado por n!, sendo n> 1 é: 
 n! = n ∙ (n −1) ∙ (n −2) ∙…∙ 3 ∙ 2 ∙ 1. 
Ex: 5! = 5.4.3.2.1 = 120 
Observação 
0! =1, 1! =1, 5! = 5. 𝟒. 𝟑. 𝟐. 𝟏 = 5. 𝟒! , Ex:
6!
3!
=
6.5.4.3!
3!
= 6.5.4 = 120 
 ARRANJOS 
É uma organização de elementos de uma determinada ordem, ou seja uma combinação de n elementos 
tomados p a p, onde a ordem de elementos importa. E é denotado por A 𝑛
𝑝
 
Chamamos de arranjo simples cada uma das lista ordenadas, sem repetição, formadas a partir da 
escolha de p elementos de um conjunto com n elementos distintos. 
Ex: Considerando o conjunto A= {1,2,3,4}, quantos números de 3 algarismos distintos ou iguais 
podem ser formados? 
Solução: Os arranjos simples de 3 elementos formados por elementos de A são: (1, 2, 3), (1, 2, 4), (1, 3, 2), 
(1, 3, 4), (1, 4,2), (1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3,1,4), (3, 2, 1), 
(3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2). 
6 
 
Para determinar o número total de arranjos simples tomado p a p de um dado conjuntos de n elementos, 
usamos a seguinte formula: 
A 𝑛
𝑝
 = 
𝑛!
(𝑛−𝑝)!
 Com n, p ∈ ℕ; 𝑒 𝑛 ≥ p 
 A 4
3
 = 
4!
(4−3)!
 = 
4.3.2.1 
1!
 = 4.3.2 =24 
Chamamos de arranjo com repetição a todos aqueles em que os elementos podem aparecer repetidos em 
cada grupo de p elementos. Para determinar o número total de arranjos com repetição tomado p a p de um 
dado conjuntos de n elementos, usamos a seguinte formula: 
 A 𝑛
𝑝
= 𝑛𝑝 Com n, p ∈ ℕ; 𝑒 𝑛 ≥ p 
Solução A 𝑛
𝑝
= 𝑛𝑝 
A 4
3
= 43 = 64 
Chamamos de arranjo condicional a aqueles em que todos elementos aparecem em cada grupo de p elementos, mas 
existe uma condição que deve ser satisfeita sobre alguns elementos. 
 
PERMUTAÇÕESÉ uma técnica de contagem utilizada para determinar quantas maneiras existe para ordenar os 
elementos de um conjunto finito. 
Uma Permutação simples é a ordenação dos elementos de um conjunto finitos, quando seus elementos 
não se repetem, são distintos. Ė Utilizada para determinar a quantidade dessas ordenações. 
A quantidade 𝑝𝑛 de permutações de um conjunto de n elementos é igual a n! 
Para determinar a quantidade de permutações simples usamos a seguinte formula: 
𝑝𝑛 = 𝑛! 
EX: Quantos ANAGRAMAS podemos formar permutando as letras da palavra FILA? 
Resolução: FILA-FIAL-FALI-FAIL-FLIA-FLAI 
 IFLA-IFAL-ILFA-ILAF-IAFL-IALF 
 LFIA-LFAI-LAFI-LAIF-LIFA-LIAF 
 AFIL-AFLI-ALFI-ALIF-AILF-AIFL 
Através da palavra FILA podemos formar 24 ANAGRAMAS permutando as letras. 
Usando a formula: 
7 
 
 𝑝𝑛 = 𝑛! 
𝑝4 = 4! = 24 
 
Uma Permutação com repetição acontece quando em um conjunto de n elementos, alguns destes são 
iguais. 
Para determinar o número de permutações com repetição, dividimos o factorial do número total n de 
elementos, pelo produto entre os factoriais dos elementos que repetem: 
P
𝑛
(𝑎, 𝑏, 𝑐)
=
n!
a!. b!. c!
 
EX: Quantos ANAGRAMAS podemos formar permutando as letras da palavra BANANA? 
Resolução: 
P
𝑛
(𝐴, 𝑁)
=
6!
3! .2!
=
6.5.4.3!
3! .2!
= 6.5.2 = 60 
O número de permutações para as letras da palavra BANANA é igual a 60. 
Uma Permutação circular é uma situação que ocorre quando temos grupos com elementos distintos 
formando uma circunferência de círculo. 
 Formula: 
 𝑝𝑛 = (𝑛 − 1)! 
COMBINAÇÃO 
A combinação é um processo matemático utilizado para contar a quantidade de subconjuntos 
diferentes, possíveis de serem formados, ao escolher elementos de um conjunto maior, não importando 
a ordem dos elementos. 
Cada subconjunto formado por elementos distintos de um conjunto maior, sem considerar a ordem com 
que estão organizados, é uma combinação. 
Existem dois tipos de combinações: as simples e as com repetição. 
Uma combinação simples é aquela que não possui elementos repetidos no conjunto maior. Desta 
forma, também não há elementos repetidos nas combinações formadas. 
Fórmula da combinação simples 
 C 𝑛
𝑝
 = 
𝑛!
𝑝!(𝑛−𝑝)!
. 
8 
 
Ex: Quantas combinações são possíveis de serem formadas se em um conjunto de cinco frutas distintas 
escolhermos três para montar uma salada? 
Mesmo sem saber quais são as frutas, o problema anuncia serem distintas, sendo uma questão de 
combinação simples. 
 C 𝑛
𝑝
 = 
𝑛!
𝑝!(𝑛−𝑝)!
 
 C 5
3
 = 
5!
3!(5−3)!
=
5.4.3!
3!.2!
= 5.2 = 10. 
 Portanto, há 10 combinações possíveis de serem formadas. 
A Combinação com repetição ocorre quando há elementos que se repetem, por isso, também é 
conhecida por combinação com repetição. 
Na combinação com repetição, o número p, que representa a quantidade de elementos no conjunto a ser 
combinado, é maior que a quantidade n de elementos disponíveis no conjunto original. Como o número 
p é maior que o número n, alguns elementos deverão ser repetidos. 
Fórmula da combinação com repetição 
 𝐂 𝒏
𝒑 = 
(𝒏+𝒑−𝟏)!
𝒑!(𝒏−𝟏)!
. 
Ex: De quantos modos um cliente pode compor uma salada com seis frutas (unidades), onde o cardápio 
oferece apenas cinco opções? 
O n, número total de frutas é 5, mas seis irão para o potinho de salada, obrigando a repetição de uma. 
Com n = 5 e p = 6. 
C 5
6 = 
(5+6−1)!
6!(5−1)!
=
10!
6!.4!
=
10.9.8.7.6!
6!.4.3.2.1
= 7.5.3.2 = 210 
Combinações complementares 
Observe que 
C 𝑛
𝑝
 = 
𝑛!
𝑝!(𝑛−𝑝)!
 = 
𝑛! 
(𝑛−𝑝!(𝑛−𝑝)!
= C 𝑛−𝑝
𝑝
 
Chamamos C 𝑛−𝑝
𝑝
 de combinação complementar de C 𝑛
𝑝
 
 
 
 
9 
 
CONCLUSÃO 
Definirmos arranjo, factorial, permutação e combinação. Vimos que a diferença entre arranjo simples e 
combinação simples está no facto de ser ou não importante a ordem dos objectos escolhidos no 
agrupamento. Tratamos ainda como obter fórmulas fechadas e simples para problemas de arranjo, 
permutação e combinação com repetição. Para completar o trabalho, definimos permutação circular, 
que é um pouco diferente da permutação simples (em fila), mas que possui relação íntima com esta, 
como pode ser visto pela própria fórmula obtida. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
10 
 
 
BIBLIOGRAFIA 
CABRAL, Raquel Pinheiro. Computação. M. Discreta.1ª edição. Fortaleza ceara. 2017 
Santos, Wagner Ferreira. M. Discreta.CESAD.2010 
BARBOSA, R.M. Combinatória e Grafos. Vol.1. Nobel: São Paulo, 1974. 
SANTOS, J.P.O., et al. Introdução à Análise Combinatória. Moderna: Rio de Janeiro, 2007. 
ASTH, Rafael C.. Analise combinatória. Toda matéria. 28/4/24 
	Introdução
	Fórmula da combinação simples
	Fórmula da combinação com repetição
	𝐂,𝒏-𝒑. = ,(𝒏+𝒑−𝟏)!-𝒑!,𝒏−𝟏.!..