Análise Combinatória, Notas de estudo de Matemática

Baixe Análise Combinatória e outras Notas de estudo em PDF para Matemática, somente na Docsity! JUBIRY VICENTE DA SILVA hm cá ANÁLISE COMBINATÓRIA * RESUMO TEÓRICO PROBLEMAS RESOLVIDOS E PROPOSTOS 4 RIO DE JANEIRO — 1979  no 12. JUBIRY VICENTE DA SILVA INSTITUTO DE MATEMATICA E ESTATÍSTICA UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO BACHARELADO EM CIÊNCIAS ESTATÍSTICAS ENCE -CONRE 029 ALINE COMBINATORIA RESUMO TEÓRICO PROBLEMAS RESOLVIDOS E PROPOSTOS SUMÁRIO pão. Arranjos Simples....eesiiececeenerirreeeeeeeertrerensertenes cer 1 Permitações Simples. ...iitceceserenereseeenensenecererereceseentos 2 Conbinações Simples... .u.ceeeceeo 3.1, Propriedades das Combinações Triângulo Aritmético de Tartaglia - Pascal. ...cceecesceeseeermertos 4.1, Teorema das Colunas. 4 Teorema das Linhas Teorema de Bezout....cccecsescertsreaaenmenrerencasenercenerceriraa .7 Permitações Circulares. ..... tieeeeeerenenenenananenennenaneenes Permutações com Repeti Arranjos com Repetiçã Combinações com Repetição... ..cccccecesecescecaneoaneneneneneraneno n Fómiila de Euler Fórmula do Lagrange. ..eeeercererereceenereceros eemeeenerasenesineeo 13 Binômio...ecececerecenenenenenececacanenenenenenemenerneneceneances 14 12.1. Fómla de Stévin...ccscssssassreris certame rena ar ce serasa s aà 1.2. Binômio de Newton. .ccecerecesserecerareranenennaraceneneneneno ” 2,2.1 Temo Geral do Desenvolvimento. ......cccceree rrrreeorertaaeca 14 12.2.2 lei de Formação dos Temos... .secesecesenecentenecesenenaceea 14 12.3. Temos Equidistantes.... easarasaia . ee cell 12.4. Soma dos coeficientes do binômio «15 15 12,5. Temo de Maior Coeficiente. ia de Polinômios... Potênc 13.1 Fórmula de Leibniz..... cce 13.2. Fórmula do Binômio para Expoenves Fracionários Positivos e Ne- gativoS eesesseneess Prot mas Resolvidos de Análise Combinató. Binômio de Newton Potências de Polinômios. ss... Problemas Propostos ...».. 3. Combinações Simples Chama-se combinações simples de n elementos de classe p, Bos gru- pamentos não ordenados contendo p desses elementos. Assim, as combinações simples são grupamentos que diferem entre si pela natureza dos elementos. Pela definição, para que 2 combinações difiram uma da outra E ne- cessário que pelos menos um dos elementos de uma não figure na outre, uma vez que à ordem dos elementos não diferencia combinações. Por esse motivo as combinações são também chamadas de produto distintos. Consideramos formado o quadro das combinações simples de classe p de n elementos. Permutemos os elementos de cada uma dessas combinações, de modo a formar O quadro. Neste quadro os grupamentos diferirão entre si: a) pela ordem dos elementos, quando originários da mesma combina- ção, ou b) pela natureza dos elementos, quando originários de duas combi- nações. Temos, assim formado o quadro dos arranjos de classe p dos n elementos, o que nos permite escrever: p Mm = UP — Pa. A [aa Pp Q 7 f o ): -1 p PA M ngn al dele = Pp: tp-Dp Exemplo 1: Quantos são os produtos ternários feitos com os & primeiros núme- ros primos: Solução: 2,3,5,7,M, 13.17.19 8.7.6 1.2.3 Exemplo 2: Com os elementos a,b,c,d tom ados 2 a 2 podemos formar es com- binações: > 43 G= =6, isto é: “ar ab ac ad be bd cd 3.1. Propriedades das Combinações: 1) da formula de fatorial tiramos: pi(n-p): (np)! Logo, temos as chamadas combinações complementares [rd = CP, aton- selhâvel quando p > Exemplo: 8. ção. Go = Goi 12 12 5 a > cão = Ciogi por ser 98» 100. 11) O número de combinações de n elementos de classe p que não con- têm um certo elemento Po. iii) Relação de Sbifel: Pe le mo nt Demons tração: Consideremos as igualdades: Gl. Amei) (ue2) o (nepé n- 1.2.3. +. (p-1) o. AM) (MD) de (rep n=1 1.2.3. ... (p-1)p Somando membro a membro e colocando em evidência, temos: [5a + Os fu ade lan (ya todo) 1.2.3... (p-1) Ee o feel tmêt os np en M 1.23. ..(p-1) Pp p! p cd +Gus A ou cel + Co - Ch cad. Fôrmula generelizada de Stifel: E p=] p-1 p-1 p-1 Po= + Cy + d+ ql dy 4.4 9.8.7 =c 9.8.7.6 , SB? 196 + 84 =210 0 909 1.2.3.9 1.2.3 4. Triângulo Aritmêtico de Tartaglia- Pascal Chama-se coeficiente binomial de classe p de n elementos, a relação: o (0) = Mini) (nego. (rep para n>p n Pp 1.2.3. ... Pp = Estes coeficientes são também chamados nimeros combinatórios: Paran <p— (go -0 e (o =, para n> O. Representando os subconjuntos aj,a,, ... , à, = A e »a =Btemse: A aj açB. NAM Trocando-se ajea, de posição, temos Aa, as B. O que não acarreta alteração no número de inversões nos subconjuntos À e B. Apenas, se a; a, cons tituia uma inversão (permanência) na primeira, passou a constituir permanência (inversão) na segunda, havendo então, diminuído (aumentado) de 1 0 número de inversões, que se era par (impar) passou a ser impar (par), mudando a classe da permutação. 29 Caso: Os dois elementos não são consecutivos: Suponha a; +... açõ Pp Efetuando p mudanças sucessivas de classe, chegar-se-ã a posição. Finalmente, fazendo mais uma troca, ou seja p+l, chegar-se a Tem-se, então, um total de p+1+p = 2p+1 (número impar) de mudanças de classe. Portanto, se o número de inversões era impar (par), somando a núme ro ímpar, passou a ser par (impar), havendo a permutação mudado de classe. Consequência: Feitas as n! permutações entre n elementos, há tantas de classe par (p) quantas de classe Tmpar (1), isto & P = 1 = 6. Permutações Circulares. P( - n Os elementos estão dispostos segundo uma circunferência e de acordo com um sentido determinado. Chama-se permutações circulares de n elementos às permutações obtí- das passando sucessivamente para o Último lugar o primeiro elemento da per- mutação. Para exemplificação, tomemos os elementos asbsc,di abcd bcda cdab dabc 8 E claro que ao agrupamento de n elementos, correspondem n permutações circulares desses agrupamentos . Designemos por P. o número das disposições possíveis, distintas, n de n elementos sobre uma circunferência, como cada uma dessas disposições dã origem a n permutações circulares, e como o número total das permuta - ções de n elementos é nº, tem-se: nP. = n! poi (o)! do anterior: 7. Permutações com Repetição, ou seja com elementos nem todos distintos. Consideremos a permutação: ajazega bybdy CCC, Total das permutações simples desses 10 elementos E 10! Fazendo ay = ap =2;=&, =a,0 no de permutações dos mesmos 10 elementos em que 4 deles são iguais serã evidentemente. 10: 4 Fazendo ema aaa by b, CC, C, Cy » = b, 0 nº de permutações será: a Finalmente, fazendo C, =C,=C,=C,=C o nº de permutações dos elementos aa aabbccccõserá evidentemente: ou seja: 10! 4.214 Generalizando — seja a permutação simples de n elementos (distintos) perna bybo... ce My Ego onde a+B+...+»=h. O número de permutação E n! Fazendo: a elementos iguais a a E elementos iguais a b à elementos iguais a 4 Considerando ay = a, =... =a =aeas restantes distintas de modo que o numero de permutações distintas ficará a ! vezes menor, ou seja igual a: n: a! Procedendo analogamente em relação às demais letras, teremos o número de permutações dos n elementos igual a em que se representa por: abra cs Pn Quantos Anagramas tem a palavra COPACABANA Solução: a = 4 elementos igual g = 2 elementos igual y = Telemento igual 85 e = Velemento igual a a a = | elemento igual a a o = Yelemento igual a Temos então: 42,15, to 4 = 10.9.8.7.6.5.8 ! Po . —miaia me a iii = 75600 sa. 4221 B. Arranjos com Repetição. Os arranjos com repetição dos n elementos p a p são os conjuntos ordenados de p elementos, distintos ou não, dentre os n elementos. 10 12. Binônimo de Newton A fórmula do binômino de Newton destina-se ao desenvolvimento das potências sucessivas de um binônimo. 12.1. - Fórmula de Stevin: (ttay) (xta5) 20 (mta) = las, x SME 45 12.2. - Binônimo de Newton: Fazendo, na fórmula de Stevin, ay = a, =... Chegaremos a fórmula de Newton: sysatat...tas(i)a -a24al4 E) a? 2 ssa praca lo leiam ou seja o Binônimo de Newton: (x+a)la ? [e ad qd 4=0 12.2.1. - Têrmo Geral do Desenvolvimento. Tomo o nt 12.2.2. - Lei de Formação dos Termos: Consideremos dois termos consecutivos: n-p (May MP Torn (pax e Toe” Gn 7 (pr1) (pa) pr ppl ao To *T pel a T (1) x prelo Cm "Tx pm Pp Pp 12.3. - Termos Equidistantes: Permutando a e x no binônimo de Newton, temos: n - tr =) 4 ar? po P n ol ralo (la af po P No desenvolvimento, o termo do grau p, ema, e do grau n-p, em x, serã Cop) x? «MP; como os binônimos são idênticos, os termos semelhantes devem ter coeficientes iguais, então: (np) = (Pp) 14 Dizemos, então, que são iguais os numeros de combinações complementares (termos equidistantes), isto &, de clas- ses cuja soma é igual ao número de objetos. 12.4, - Soma dos coeficientes do binômio. Se, na formula do binômio, fizemos em ambos os membros a =, teremos: le en" 12.4.1 - Fazendo x = a = -1, obtem-se a soma de todos os coeficientes binominais de classe par e classe impar: n-1 clesses par : (9H)... n DE) = E cuêg=o P: Classes impar : (Ue(G)e(g)+...= 12.5. - Termo de Maior Coeficiente. No desenvolvimento do binômio de Newton os coeficientes são: = Dem (De Para um deles ser maior que o precedente, & preciso que: n A, ou tl, n-pri>p-s po tl (6-1) p-1 aa ias + - Seja k, o maior inteiro inferior a LS] ; então: n+ n+1 Ketilexsc> Lilo p<keparap>k+2 Então: (<DD> Quo) > 15 O coeficiente máximo É, portanto o maior dos dois números (|) e (km), Se não forem iguais; se Forem ambos são máximo. Para comparar (k) € (111)» estudaremos a relação. mk (o K+1 i) Quando n for par n = 2k, o número de termos do desenvol - vimento serã impar 2k+1.0 termo de coeficiente máximo serã o do meio. n (1) Hi) se n for máximo, n = 2k+1,0 número de termos do desenvol vimento serã par, 2k+2, e consequentemente havera dois termos centrais: n n 77 - 7 13. - Potência de Polinômios. 13.1 Fórmula de Leibniz. Seja um polinômio de k termos, elevado a potência n: n k n (Mptaptetan= (ia) i=l Dedução pela fórmula do binômio de Newton: (aytat. ta) ele) = 2 (8) apo xls Ne n- n=, n Neg | Ea tagr o raUS (a, ya cc (8) ob ylac8 n-a-g- nemefio.. , rodo = (atas , a, 16 1 (og" = quere C|Dxt (DI + 13.2.1 Aplicação: va Per Sea gota ts 2) eagle dec FX DE. a Vire E (ui! L tê a (3 -Nd j= 3º aq ter E po 14d ja) ja 5! ce id mib od “a 39x 5) (1-5) "= ão e) x J º . 9 ==> A 19  14. PROBLEMAS RESOLVIDOS DE ANALISE COMBINATÓRIA Num campeonato de futebol tomam parte 10 clubes. Se cada clube tem que jogar du as vezes, uma no 19 turno (A com B) e outra no 29 (B com A), quantos jogos deve- rão ser realizados? 2. - Ao & 10.9 = 90 Numa sala hã 6 cadeiras e 10 pessoas. De quantas maneiras se podem sentar 6 pes- soas ficando as outras 4 em pe? 6 Ag: 10-5.8.7.6.5=151.200 Quantos são os nimeros de dois algarismos diferentes que existem no sistema de numeração usual ( de base 10 )? -n = 8 Ao Quantos números maiores que 200 e menores que 1000 podem ser formados com os al- garismos 1,2,3,4 e 5, sem repeti-los? 1) Numero total de arranjos dos 5 algarismos 3 a 3 & 3 Ag=5.4.3-60 ii) Começando por cada um dos algarismos; 60:5-12 iii) Começando por 2,3,4 e 5 serão: 12x4=48 De quantas manciras podem ser escritas as letras da palavra ALGARISMO, as vogais aguardando sempre a mesma ordem? 5 Ag=9.8.7.6.5=]5120 De quantas maneiras diferentes 8 consoantes e 4 vogais podem ser escritas em li- nha, tomando-se de cada vez 5 consoantes e duas vogais i) Numero de modos diferentes de tomar as consoantes: 53 Cg-Lg=56 11) Número de modos diferentes de tomar as vogais: 2, 456 iii) Número de modos diferentes de tomar 5 consoantes e duas vogais: 56x6=336 20 iv) Número de permutações de cada grupo de 5 consoantes e 2 vogais: Pj=72=5040 v) Numero total de modos de dispor 5 consoantes e 2 vogais: - 5 2 5040x336=1 693 440 ou Cj . CÍ. P; 7. Dispomos de 2 obras em 3 volumes e duas outras de 3 volumes cada um. De quantas maneiras podemos colocar esses 10 volumes sobre uma prateleira de tal modo que os volumes de uma mesma chra nunca estejam separados ? 41.31.34.21,214=3456 8. De quantos modos podem ser escritas as letras da palavra CEDULA de forma que não Fiquem juntas 2 vogais e 2 consoantes? à) PyP ii) Coma as consoantes podem passar para os lugares das vogais e vice-versa,te remos ao todo 36x2=72 cuseja 31312 obs. no caso de P consoantes e P vogais: 2(P!)? 9. De quantos modos podem ser escritas as letras da palavra ALICE de modo que não fiquem juntas duas vogais e duas consoantes? PyPp=3t2!=12 Obs. Em caso geral deste problema, havendo P+1 vogais e P consoantes seria ppa) Per Ppsloe Din 10. Nas permutações da palavra ÂNGULO quantas começam por vogal? Quantas começam e acabam por vogal? 1) Ps: 3=120:3=360 2 Mi) Par Ag=24-6=144 1) Nas permutações das letras da palavra CADERNO quantas começam por C? por CA 12) Quantos números maiores que 20 000 e menores de £0 000 podem ser formados com os algarismos 1,2,3,5 € 9. a 25. Quantas comissões de 7 pessoas podem ser constituídas com 6 rapazes e 4 moças, figurando, pelo menos, 2 moças 2 - 2m + 5r => CC =36 m + dr= G an + 3r mo Cj. 26. De quantas modos 10 pessoas podem sentar-se em 10 cadeiras enfileiradas: a) sem restrições ? b) ficando A e B sempre juntas ? c) sem que A e B Fiquem juntas ? alo b)9!2!s JO! -9!2º 27. Numa uma hã 10 bolas brancas, 5 pretas e 6 azuis. De quantos modos se pode retirar 3 bolas brancas ? 28. Com 5 jogadores, entre cs quais figuram o goleiro, quantos grupos diferentes de 2 jogadores podemos formar, sendo que em nenhum desses grupos deve cons - tar o goleiro. 29. Com 6 rapazes e 4 moças quantas comissões de 3 pessoas podem ser formadas, ha vendo em cada comissões a participação feminina ? 3 Ho - 7 = 120 - 20 = 100 30. De quantas diagonais possui um polígono de n lados ? E-do- atri) (no tlgd n 2 31. De quantas formas diversas podemos escolher um romance. uma revista e um jornal entre 7 romances, 5 revistas e 10 jornais ? «CG. e = 350 maneiras diferentes. 24 32, 33. 3. 35. Num congresso de professores hã 30 professores de Física e 30 de matemati ca. Quantas comissões de 8 professores podem ser formadas: a) sem restrições? b) havendo pelo mentos 3 professores de fisica e 3 de matematica? c) havendo pelo menos 1 professor de matemática? 8 x 2 19 3 Goo 5 xe 30 30º530' 4 4 30 +Cg xe 8. 3 4 a) Co: bg 30 * Go Numa urna hã 4 bolas brancas, 6 bolas pretas, 7 bolas vermelhas e 10 bo- * tas azuis, todas numeradas. Sacam-se, de uma vez, & bolas. . a) Quantas sacadas distintas são possíveis? b) Quantas são as sacadas em que aparecem 3 bolas brancas, 2 pretas, uma vermelha e as restantes azuis? c) Quantas são as sacadas em que não aparecem bolas brancas? b) [5 ç 1 2. e ) . 6 Cy Cor 18.900 ; Cog 8, 3 Cy: r Sacam-se, dé uma vez, cinco pedras de uma urna onde se encontram 90 pe- dras numeradas de 1 a 90. Quantas são as sacadas: a) possíveis? b) em que saiam, pelo menos, duas pedras de número impar? c) em que saiam 3 pedras de número par e 2 de número impar? 5 4 3.2 3 Co 5 b) Cogtas las Cas é) Cog'Cas Para a seleção brasileira de futebol foram convocados 22 jogadores, os quais jogam em todas as posições, exceto dois deles, que so jogam de go teiro. De quantos modos se pode selecionar os 11 jogadores titulares? na Cogtog 25