Introdução_ao_cálculo_combinatório,_lei_Meldo_Leonardo_Maúnze[1]

Prévia do material em texto

Universidade Lúrio
Faculdade de Engenharia
Licenciatura em Engenharia Informática
Disciplina: Matemática Discreta
Introdução ao Cálculo Combinatório: Arranjos e Permutações.
Docente: Sufia Sumaila, 
Discente: Meldo Leonardo Maúnze
Pemba, abril 2020
1
Índice 
Introdução	1
Introdução ao cálculo combinatório	2
Princípios de enumeração combinatória	2
Arranjos	5
Permutações	6
Conclusão	10
Referencias Bibliográficas	11
Introdução
A análise combinatória é a parte da Matemática que se dedica a contagem de elementos, da sequência de elementos, bem como a contagem de subconjuntos de um conjunto, trata se de uma área que permite resolver problemas simples que porém que fazem parte do dia a dia da humanidade, nesta perspetiva, o presente trabalho tem como objetivo trazer uma análise no concernente a introdução ao cálculo combinatório, assim poderá se desenvolver temas como arranjos, permutações, entre outros que poderão fornecer bases solidas para a compreensão do calculo combinatório.
De referir que o trabalho destina se a disciplina de matemática discreta, da universidade Lúrio para o curso de Engenharia informática e foi possível sua realização através de consultas em manuais didáticos.
Introdução ao cálculo combinatório
O conhecimento de alguns elementos da teoria de conjuntos segundo [ (Vuma, 2010)] permite ter uma perspetiva mais natural do cálculo combinatório fornecendo uma ferramenta necessária a resolução de problemas, assim importa recordar algumas conceitos básicos da teoria de conjuntos como é o caso de:
1. Cardinal de um conjunto: o cardinal de um conjunto finito A é o número de elementos deste conjunto, e pode se representar pela notação: .
2. Complementar de um conjunto: o complementar de um conjunto A em relação a um universo U, é o conjunto de todos elementos de U que não pertencem a A. Pode ser representado da seguinte maneira: Ā o complementar de um conjunto A em relação a um Conjunto B, é o conjunto dos elementos de B que completam o B.
3. Reunião e intercessão de conjuntos, 
4. Produto cartesiano, é o conjunto de todos pares ordenados que se podem formar indicando primeiro um elemento de A e depois um elemento de B e representa se por .
, assim é fácil constatar que .
O conhecimento desses conceitos básicos é crucial na rápida assimilação dos conteúdos relacionados ao cálculo combinatória, neste caso os princípios de enumeração combinatória que servirão de “força eletromotriz” para a perceção do tema do trabalho, 
Princípios de enumeração combinatória
[ (Cardoso, Szymanski, & Rostami, 2011)] apresentam os seguintes princípios:
1. Princípio da bijeção;
2. Princípio da multiplicação;
3. Princípio da inclusão e adição 
Esses princípios, segundo [ (Figueredo, sila, & Cunha, 2010)] permitem melhor analise e resolução dos problemas relacionados com o calculo combinatório, desta forma, segue se o desenvolvimento de cada princípio, a saber:
1. Princípio da bijeção 
O princípio da bijeção consiste na identificação dos objetos de um conjunto com os elementos de outro conjunto com o qual é mais fácil trabalhar. Assim, de acordo com este princípio, dados os conjuntos A e B, se existe uma bijeção = B, conhecida a cardinalidade do conjunto A, ficamos a conhecer a cardinalidade do conjunto B.[ (SANTOS, 2007)]
2. Princípio da adição
Dados dois conjuntos, A e B, se A e B são dois conjuntos disjuntos, sendo p e q elementos, respectivamente, então possui elementos.
Exemplo: [Exame Matemática 12ª cLasse (adaptado)] Josemar ofereceu a Issufo 3 livros de Álgebra, 7 livros de combinatória e 5 livros de Geometria e pediu-lhe para escolher um único livro. De quantas maneiras Issufo pode realizar essa escolha?
RESOLUÇÃO: se uma decisão A pode ser tomada de x maneiras, uma decisão pode ser tomada de y maneiras e as decisões são independentes, então o número de maneiras de se tomarem as decisões . Considerando os três conjuntos de livros:
· }, conjunto dos livros de Álgebra.
· , conjunto dos livros de combinatória.
· conjunto dos livros de Geometria.
Issufo deverá escolher apenas um livro dentre os três conjuntos, como temos 3 opções em A, 7 opções em C e 5 opções em G, portanto ao todo obtemos 15 opções de escolha. No geral, o princípio aditivo pode ser reescrito da seguinte maneira:
Se são conjuntos disjuntos dois a dois . 
3. Princípio de inclusão-exclusão 
Segundo (SANTOS, 2007)] o Princípio da inclusão e exclusão é uma fórmula para contar o número de elementos que pertencem à união de vários conjuntos não necessariamente disjuntos. Para entendermos melhor do que se trata.
Primeiro: sejam A1 e A2 dois conjuntos finitos quaisquer. 
Temos: |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|.
Temos que A1 ∪ A2 = (A1 − A2) ∪ A2, onde no segundo membro da igualdade temos uma união de dois conjuntos disjuntos. Pelo princípio aditivo, temos que
|A1 ∪ A2| = |A1 − A2| + |A2|. Aplicando novamente este princípio, temos que
|A1| = |A1 − A2| + |A1 ∩ A2| = |A1 − A2| = |A1| − |A1 ∩ A2|. Substituindo a segunda expressão na primeira expressão temos |A1 ∪ A2| = |A1| − |A1 ∩ A2| + |A2|,
Segundo: sejam A1, A2 e A3 três conjuntos finitos quaisquer. Então, |𝐴1 ∪ 𝐴2 ∪ 𝐴3| = |𝐴1| + |𝐴2| + |𝐴3| + |𝐴1 ∩ 𝐴2 ∩ 𝐴3|−(|𝐴1 ∩ 𝐴2| + |𝐴1 ∩ 𝐴3| + |𝐴2 ∩ 𝐴3|).
Pelo primeiro teorema temos que,. Lembrando que pelo primeiro teorema, podemos afirmar que e ainda |. Substituindo, temos +|A1 ∩ A3| − |(A1 ∩ A2) ∩ (A1 ∩ A3)|). Já que (concluímos que 
Terceiro: usando a notação de somatório podemos reescrever o principio a cima da seguinte maneira , essa expressão nos leva a: assim: o princípio da inclusão resume se da seguinte maneira:
 +…+() (Pinto, 2005)
4. O princípio da multiplicação
O princípio da multiplicação ou princípio fundamental da enumeração combinatória, também chamado de princípio multiplicativo, postula que quando um evento é composto por n etapas sucessivas e independentes, de tal modo que as possibilidades da primeira etapa é x e as possibilidades da segunda etapa é y, resulta no número total de possibilidades de o evento ocorrer, dado pelo produto [ (Gomide & Stolfi, 2011). Matematicamente, são conjuntos não vazios finitos, então o conjunto dos n-uplos (a1, a2, ..., an), onde o qual vamos denotar por [ (Cardoso, Szymanski, & Rostami, 2011)]
Em resumo, no princípio fundamental da enumeração combinatória, multiplica-se o número de opções entre as escolhas que lhe são apresentadas.
Os princípios da enumeração podem ser usados em grande parte dos problemas relacionados com enumeração combinatória. Entretanto, em algumas situações seu uso torna a resolução muito trabalhosa, desta forma, pode se recorrer algumas técnicas para resolver problemas com determinadas características. Basicamente há três tipos de agrupamentos: arranjos, combinações e permutações. Neste estudo, como fora mencionado na introdução, poderão ser desenvolvidos, os conteúdos relacionados com arranjos e permutações respetivamente.
Arranjos 
“Dados n elementos quaisquer, chama se arranjo dos n elementos p a p todos os conjuntos ordenados que é possível obter com p elementos arbitrariamente entre os n dados” .[ (Gomide & Stolfi, 2011)
Arranjos com repetição 
Dados n tipos de objetos, podemos formar diferentes configurações de p objetos, em certos casos assumindo que essas configurações podem conter mais do que um objeto do mesmo tipo. Duas configurações dizem-se distintas se contêm diferente número de objetos de determinado tipo ou se são determinadas por diferentes ordenações dos objetos que as constituem. Dados n tipos diferentes de objetos, as configurações de p objetos que dependem da ordem e podem conter mais do que um objeto do mesmo tipo designam-se por arranjos com repetição de n elementos p a p. [ (Cardoso, Szymanski, & Rostami, 2011)].
Nestes casos, duas configurações dizem-se distintas se existe pelo menos um tipo de objetos que ocorre mais vezes numa configuração do que na outra ou se a ordem de ocorrência dos diferentes objetos não é igual nas duas configurações
O número de arranjos com repetição de um conjunto de n elementosp a p denota-se por An(p)
pelo princípio da multiplicação, 
Exemplo: [Matemática 12ª classe (adaptado)] Numa loja, os códigos de produtos são formados por quatro letras das 20 primeiras letras do alfabeto. Quantos formações de códigos de produtos são possíveis?
É possível notar que , nesses códigos, não importa se as letras se repetem. Portanto, para cada letra integrante temos 20 possibilidades. Pelo príncipio da multiplicação basta que se multipliquem as possibilidades, 20× 20× 20 ×20 = 20⁴ Usando a fórmula, com n=20 e p=4, encontra se 20⁴ o mesmo resultado de antes, neste caso: 160.000
Fatorial de um número
Dado um número natural n, chama se fatorial de n, ao produto dos n primeiros números se n≠1, o fatorial de n representa se por n!
. [ (Figueredo, sila, & Cunha, 2010)]
Arranjos sem repetição 
Se na definição de arranjo não se considerar a hipótese de repetição de qualquer elemento trata se de arranjo simples (ou arranjo sem repetição ou simplesmente arranjo)[ (Cardoso, Szymanski, & Rostami, 2011)]. Aplicando o princípio da multiplicação generalizada, pode se concluir que que o número de arranjos simples de n elementos p a p, denotado por An,p, é igual An,p = (n)p = n(n − 1). . .(n − p + 1). Usando o princípio multiplicativo tem se 
A(n,p)n(n-1)(n-2)…(n-p+1), Assim [ (Gomide & Stolfi, 2011)]
Exemplo: [Exame iscam (adaptado)] A turma da faculdade de Engenharia da unilurio deseja realizar uma votação para escolher um representante e um vice representante de uma turma, com 20 alunos. Sendo que o mais votado será o representante e o segundo mais votado o vice-representante. De quantas maneiras distintas a escolha poderá ser feita? 
Resolução: É importante observar que nesse caso, a ordem é importante, visto que altera o resultado final, certamente trata se de um arranjo sem repetição daí que pela fórmula do arranjo sem repetição teremos: dos 20 somente 2 serão escolhidos, assim: , , logo, o arranjo pode ser feito de 380 maneiras diferentes. Em particular, os arranjos simples com designam-se por permutações (permutações simples). 
Permutações
Permutação Simples
Uma permutação de n objetos distintos é qualquer coleção ordenada desses n objetos. Seja X um conjunto finito de n elementos. Informalmente de acordo com [ (Pinto, 2005)] uma permutação de X, é uma lista de elementos de X em determinada ordem, sem repetição e nem omissões. Uma vez escolhido o primeiro dessa Ordem, para a escolha do segundo, temos n – 1 possibilidades. Existem quantas permutações num conjunto de n objetos? Usando o princípio da multiplicação, dividiremos nosso problema em n etapas. Como uma permutação é coleção ordenada desses n objetos, para a primeira posição da ordem desses elementos temos n possibilidades. Uma vez Escolhido o segundo elemento da ordem, para a escolha do terceiro, temos n-2 possibilidades, e, assim por diante. Como consequência, o número de permutações de n elementos vem dado por:
Exemplo: [Exame de admissão up (adaptado)] no aeroporto de pemba, há apenas um banco de 6 lugares, de quantas maneiras diferentes 6 pessoas podem se sentar em um banco com 6 lugares.
Resolução: A ordem em que irão se sentar é importante e o número de lugares é igual ao número de pessoas, raciocinando a pessoa 1 pode ocupar o lugar 1, ou 2 ou 3 ou 4 ou ainda 5, a pessoa 2, pode ocupar o lugar 1 ou 2 ou 3, assim sucessivamente, é possível que neste caso, trata se de um problema que é recomendável usar a permutação, assim, , logo, existem 720 maneiras diferentes para as 6 pessoas sentarem neste banco.
Por convenção existe uma única permutação com 0 elementos e, consequentemente, que 0! = 1
Permutações com elementos repetidos	
Dados N objetos, de modo que N1 são de um certo tipo, N2 são de tipo diferente dos anteriores, são de um tipo diferente dos anteriores e , então, o número de permutações destes n objetos é dado pela fórmula (Figueredo, sila, & Cunha, 2010)
Para provar a fórmula acima vamos fazer o raciocínio seguinte, se fossem N objetos distintos, teríamos N! Permutações, sendo x o número de permutações dos objetos, então para cada objeto existem:
· N1! Maneiras de colocar objetos do primeiro tipo;
· N2! Maneiras de colocar objetos do segundo tipo; 
· ...
· Nr maneiras de colocar objetos da do r-esimo tipo, pelo princípio da multiplicação temosN.
 Exemplo: [Exame matemática Discreta Unizambeze (adaptado)]: quantos são os anagramas da palavra BANANA? Engano seria achar que basta tomarmos a permutação simples de 6 elementos, dessa forma só estaria correto se todas as letras que compõem BANANA fossem distintas, o que não é o caso. Imagine que as três letras A, bem como as duas letras N, sejam distinguíveis entre Si, chamando-as de A, A2, A3, N1 e N2. Considerando por exemplo o Anagrama BANANA, permutando primeiramente as letras A, teremos as . Que representam o mesmo anagrama. Vale a pena lembrar que já sabíamos que haveriam 3! = 6 maneiras de se permutar 3 elementos supostamente distintos, como visto em permutações simples. Agora tomando por exemplo , e permutando as letras N,
Teremos as formas: . Também já era do conhecimento que haveria 2! = 2 maneiras de se permutar 2 elementos supostamente distintos. É evidente que para as outras cinco composições, também poderia gerar se duas novas formatações, totalizando 12 novos anagramas, que na realidade são todos iguais ao anagrama BANANA. Imaginando que as 6 letras de BANANA fossem distintas, seria possível obter 6! anagramas, entretanto mostrou se que a cada 12 desses anagramas imaginados corresponde um só na realidade. Portanto o número de anagramas pedido é: .
Permutações Circulares
Uma permutação circular de n objetos distintos é qualquer modo de colocar esses n objetos em círculo. Existem quantas permutações circulares num conjunto de n objetos distintos? 
Considerando que se uma permutação em círculo pode ser obtida a partir de outra por rotação dos elementos, então estas duas permutações são consideradas iguais. Portanto, cada uma das n! permutações simples distintas dos n elementos, analisando como se elas estivessem em linha, é contada n vezes, pois existe exatamente n possibilidades de se rotacionar N elementos em torno de um círculo até voltar a situação inicial, ou seja a cada grupo de n permutações em linha corresponde a uma única permutação circular. Entretanto,conclui se que o número de permutações circulares de n objetos distintos, representa-se por
P(c,n) é dado por: 
Permutações dos elementos do conjunto } 
Sem perda de generalidade o estudo estará centralizado nas permutações dos elementos do conjunto }, o qual se denota por Sn. E claro que cada permutação π dos elementos do conjunto [n] pode ser interpretada como uma bijeção Esta permutação pode escrever-se na forma mais compacta ou, quando no contexto não há lugar a qualquer duvida em relação a permutação em causa, simplesmente [ (Cardoso, Szymanski, & Rostami, 2011)].
1. Permutação identidade
 Para cada inteiro a permutaçãodesigna-se por permutação identidade e denota-se por πid. Tendo em conta as observações anteriores, podemos ainda representar a permutação identidade por πid ou Uma vez que as permutações são bijeções, a composição de permutações define-se em coerência com a composição de bijeções. Como consequência, se .
2. Transposição
Uma permutação τ ∈ Sn diz-se uma transposição se é um ciclo de comprimento dois. Em particular, os ciclos com dois elementos sucessivos, ou seja, tais que para , são transposições que se designam por transposições simples. Observe-se que cada transposição τ é igual à sua inversa, isto é, τ−1 = τ ou de modo equivalente τ ◦ τ = πid. Mais geralmente, cada permutação π tal que diz-se uma involução, logo, cada transposição é uma involução. Por outro lado, sendo π = (π1 . . . πn) ∈ Sn uma permutação, se
3. Inversão
Dada a permutação designa-se por inversão de π se xi > xj . O número de todas as inversões da permutação π denota-se por 
4. Sinal de uma permutação 
Dada uma permutação , o número designa-se por sinal da permutação π e denota-se por sgn(π). Umavez que I(πid) = 0, deve observar-se que e, para cada transposição.
5. Paridade de uma permutação
A permutação π ∈ Sn diz-se par se sgn(π) = 1 e diz-se ímpar no caso contrario. Denotando o conjunto das permutações pares do conjunto [n] por Pn, ou seja, Pn = {π ∈ Sn : sgn(π) = 1}, pode concluir-se que se π, ρ ∈ Pn então 
.
Conclusão
Como foi possível constatar, a análise combinatória é um campo vasto e de bastante interesse para a contagem e organização de elementos, foi possível observar que as permutações ocorrem quando se formam agrupamentos com distintos elementos, de forma que os tais elementos sejam distintos entre si pela ordem por outro lado, os arranjos são agrupamentos nos quais a ordem dos seus elementos faz a diferença, os arranjos são distintos entre si pela ordem ou pela espécie.
Assim, pode se afirmar que os objetivos do trabalho foram respondidos com sucesso a medida que foi possível definir e desenvolver todos os conteúdos do mesmo, todavia, admite se a carência de informações diversas devido a carência de material porém, deixou se ficar o essencial.
Referencias Bibliográficas 
Cardoso, D. M., Szymanski, J., & Rostami, M. (2011). matematica discreta, combinatoria, teoria de grafos e algoritmos. lisboa: ed.
Figueredo, L. M., sila, M. O., & Cunha, M. O. (2010). teoria de conjuntos e tecnicas de contagem (3rd ed., Vol. 1). rio de janeiro: Tereza Queiroz.
Gomide, A., & Stolfi, J. (2011). elementos de matematica discreta para computacao. sao paulo: N/A.
Pinto, J. S. (2005). topicos de matematica discreta. aveiro: departamento de matematica da universidade aveiro.
SANTOS, J. e. (2007). Introdução à Análise Combinatória. Moderna. Rio de Janeiro.
Vuma, J. P. (2010). pre-universitario matematica 12 (1 ed.). maputo: longman mocambique.
11