ANÁLISE COMBINATÓRIA 1 (1)

Prévia do material em texto

ANÁLISE COMBINATÓRIA
OBJETIVO
oIntroduziremos de forma natural e intuitiva as construções clássicas da análise combinatória (permutações, arranjos, combinações).
o O	objetivo	é	mostrar	que	as	fórmulas	para	permutações,
combinações,	que	obteremos	com	a	aplicação	dos	princípios
arranjos	 e aditivo	e
multiplicativo, são ferramentas importantes para simplificar a solução de vários problemas.
Exemplo 1: Suponha que tenham entrado em cartaz 3 filmes e 2 peças de teatro e que Carlos tenha dinheiro para assistir a apenas 1 evento. Quantos são os programas que Carlos pode fazer no sábado?
Exemplo 2: Suponha que tenham entrado em cartaz 3 filmes e 2 peças de teatro e que Carlos tenha dinheiro para assistir a um filme e a uma peça de teatro. Quantos são os programas que Carlos pode fazer no sábado?
Exemplo 3: Numa confeitaria, há 5 sabores de picolés e 3 sabores de salgados. Suponha que Maria só tenha permissão para tomar um picolé ou comer um salgado. Quantos são os possíveis pedidos que Maria pode fazer?
Exemplo 4: Suponha que Lúcia vá à confeitaria com Maria e possa tomar um picolé e comer um salgado. Quantos pedidos diferentes Lúcia pode fazer?
Os Exemplos 1 e 3 obedecem a um mesmo princípio básico que chamamos de princípio aditivo.
PRINCÍPIO ADITIVO
Se 𝐴 e 𝐵 são dois conjuntos disjuntos	𝐴 ∩ 𝐵 = ∅	com, respectivamente, 𝑝 e 𝑞
elementos, então 𝐴 𝖴 𝐵 = 𝑝 + 𝑞 elementos.
Os Exemplos 2 e 4 obedecem a um mesmo princípio básico de contagem que chamamos de princípio multiplicativo.
PRINCÍPIO MULTIPLICATIVO:
Se um evento 𝐴 pode ocorrer de 𝑚 maneiras diferentes e, se, para cada uma
dessas 𝑚 maneiras possíveis de 𝐴 ocorrer, um outro evento 𝐵 pode ocorrer de
𝑛	maneiras diferentes, então o número de	maneiras de	ocorrer	o evento A seguido do evento 𝐵 é 𝑚 ∙ 𝑛.
Em linguagem de conjuntos:
Se 𝐴 é um conjunto com 𝑚 elementos e 𝐵 é um conjunto com 𝑛 elementos, então o conjunto 𝐴 × 𝐵 (lê-se 𝐴 cartesiano 𝐵) dos pares ordenados (𝑎, 𝑏), tais que 𝑎 pertence a 𝐴 e 𝑏 pertence a 𝐵, tem cardinalidade 𝑚 ∙ 𝑛.
EXTENSÃO DO PRINCÍPIO ADITIVO
Se 𝐴1, 𝐴2, … , 𝐴𝑛 são conjuntos, disjuntos 2 a 2, e se 𝐴𝑖	possui 𝑎𝑖	elementos, então a união ڂ𝑛	𝐴𝑖, possui σ𝑛	𝐴𝑖 elementos.
𝑖=1	𝑖=1
EXTENSÃO DO PRINCÍPIO MULTIPLICATIVO
Se um evento 𝐴𝑖 pode ocorrer de 𝑚𝑖 maneiras diferentes, para 𝑖 = 1,2, … , 𝑛,
𝑖=1
então esses 𝑛 eventos podem ocorrer, em sucessão, de ς𝑛	𝑚𝑖 maneiras.
Em linguagem de conjuntos, se o conjunto 𝐴𝑖 tem cardinalidade 𝑚𝑖, para 𝑖 =
𝑖=1
ς𝑛
𝑚𝑖
1,2, … , 𝑛 ,	então	o	produto	cartesiano	𝐴1 × 𝐴2 × ⋯ × 𝐴𝑛	tem elementos.
Exemplo 5: De quantas maneiras podemos dar 2 prêmios a uma classe com 10 rapazes, de modo que os prêmios não sejam dados a um mesmo rapaz?
Exemplo 6: De quantas maneiras podemos dar 2 prêmios a uma classe com 10 rapazes, se é permitido que ambos sejam dados a um mesmo rapaz?
Exemplo 7: Um amigo mostrou-me 5 livros diferentes de matemática, 7 livros diferentes de física e 10 livros diferentes de química e pediu-me para escolher 2 livros com a condição de que eles não fossem da mesma matéria. De quantas maneiras eu posso escolhê-los?
Exemplo 8: Quantos são os anagramas de 2 letras diferentes que podemos formar com um alfabeto de 23 letras?
Exemplo 9: Há 12 moças e 10 rapazes, onde 5 deles (3 moças e 2 rapazes) são filhos da mesma mãe e os restantes não possuem parentesco. Quantos são os casamentos possíveis?
Exemplo	10:	Quantos	são	os	números	que	podemos	formar	com	todos	os dígitos 1, 1, 1, 1, 1, 1, 1, 2 e 3?
Exemplo 11: Quantos números de 3 algarismos distintos podemos formar com os dígitos 5, 6 e 7?
O	Exemplo	11	trata	de	um	princípio	de	contagem	que	chamamos	de permutação simples.
PERMUTAÇÃO SIMPLES:
Uma permutação de 𝑛 objetos distintos é qualquer agrupamento ordenado desses objetos, de modo que, se denominarmos 𝑃𝑛 o números das permutações simples dos 𝑛 objetos, então 𝑃𝑛 = 𝑛(𝑛 − 𝑙)(𝑛 − 2) ∙ ⋯ ∙ 1 = 𝑛!.
Exemplo 12: Considerando os dígitos 1, 2, 3, 4 e 5, quantos números de 2 algarismos distintos podem ser formados ?
Exemplo	13:	Quantos	subconjuntos	de	2	elementos	possui	o	conjunto	𝐴 =
{1,2,3,4,5}?
Exemplo 14: Considerando os dígitos 1, 2, 3, 4 e 5, quantos números de 3 algarismos distintos podem ser formados ?
Exemplo	15:	Quantos	subconjuntos	de	3	elementos	possui	o	conjunto	𝐴 =
{1,2,3,4,5}?
De modo geral, podemos dizer que o princípio multiplicativo leva em conta a ordem dos elementos do grupo formado. Se essa ordem não importar, devemos excluir as repetições dividindo o resultado, obtido com o princípio multiplicativo, pelo número de permutações dos componentes do grupo.
Exemplo 16: De quantas maneiras diferentes as letras a, a, a, a, b, b, b, c, c, d, podem ser distribuídas entre 2 pessoas?
Exemplo 17: Quantos são os divisores do número 126.000?
Exemplo	18:	Dado	𝑁 = 𝑝1𝖺𝑛 ∙ 𝑝2𝖺2 ∙ ⋯ ∙ 𝑝𝑛𝖺𝑛
distintos, calcular o número de divisores de 𝑁.
onde	os	𝑝𝑖
são	primos	e
Exemplo 19: Quantos subconjuntos possui o conjunto 𝐴 = {𝑎, 𝑏, 𝑐}?
Exemplo 20: Quantos subconjuntos possui o conjunto 𝐴 com 𝑛 elementos?
Exemplo 21: Quantas são as maneiras de 6 carros serem estacionados em 6 vagas?
Exemplo 21: De quantas maneiras 12 moças e 12 rapazes podem formar pares para uma dança?
Exemplo 22: Numa sorveteria, há 20 sabores diferentes de sorvete. Considerando que não se possa misturar sabores, de quantas maneiras 7 amigos podem fazer seus pedidos?
Exemplo	23:	De	quantas	maneiras	podemos	distribuir	6	objetos	diferentes entre 2 pessoas, de modo que cada uma receba pelo menos 1 objeto?
Exemplo 24: De quantas maneiras podemos separar 6 objetos diferentes em 2 conjuntos não-vazios?
Exemplo 25: De quantas maneiras podemos distribuir n objetos diferentes em duas caixas diferentes, de modo que nenhuma caixa fique vazia?
Exemplo 26: De quantas maneiras podemos distribuir n objetos diferentes em 2 caixas iguais, de modo que nenhuma fique vazia?
Exemplo 27: De quantas maneiras podemos distribuir 6 laranjas (iguais) entre 2 pessoas?
Exemplo 28: De quantas maneiras podemos distribuir n objetos iguais em 2 caixas diferentes?
Exemplo 29: De quantas maneiras podemos distribuir 6 laranjas (iguais) entre 2 pessoas, de modo que cada uma receba pelo menos 1 laranja?
Exemplo 30: De quantas maneiras podemos distribuir n objetos iguais em 2 caixas diferentes de modo que nenhuma fique vazia?
Exemplo 31: De quantas maneiras podemos distribuir 6 laranjas (iguais) em 2 caixas iguais?
Exemplo 32: De quantas maneiras podemos colocar 5 laranjas (iguais) em 2 caixas iguais?
Exemplo 33: Seja 𝑛 um número par de objetos idênticos. De quantas maneiras podemos colocá-los em 2 caixas iguais?
Exemplo	34:	Seja	𝑛	um	número	impar	de	objetos	idênticos.	De	quantas maneiras podemos colocá-los em 2 caixas iguais?
Exemplo 35: De quantas maneiras podemos colocar 6 laranjas (iguais) em 2 caixas iguais, de modo que nenhuma caixa fique vazia?
Exemplo 36: De quantas maneiras podemos colocar 5 laranjas (iguais) em 2 caixas iguais, de modo que nenhuma fique vazia?
Exemplo 37: Sejam um número par de objetos idênticos. De quantas maneiras podemos colocá-los em 2 caixas idênticas, de modo que nenhuma caixa fique vazia?
Exemplo 38: Seja n um número impar de objetos idênticos. De quantas maneiras podemos colocá-los em 2 caixas idênticas de modo que nenhuma fique vazia?
𝑛
Vamos tentar encontrar uma expressão matemática que caracterize 𝐴𝑝, usando
o princípio multiplicativo.
ARRANJO SIMPLES:
Arranjos simples de 𝑛 elementos tomados 𝑝 a 𝑝, onde 𝑛 > 1 e 𝑝 é um número natural tal que 𝑝 < 𝑛, são todos os grupos de 𝑝 elementos distintos, que diferem entre si pela ordem e pela natureza dos 𝑝 elementos que compõem
𝑛
cada grupo. Notação 𝐴𝑝 = 𝐴𝑛,𝑝.
Temos	𝑛	elementos	dos	quais	queremos	tomar	𝑝.	Este	é	um	problema equivalente a termos 𝑛 objetos com os quais queremos preencher p lugares.
FÓRMULA PARAARRANJO:
𝑛
𝑛,𝑝
𝐴𝑝 = 𝐴	=
𝑛!
𝑛−𝑝 !
.
Exemplo 39: Quantos anagramas de 2 letras diferentes podemos for mar com um alfabeto de 23 letras? (veja Exemplo 8)
Exemplo 40: Considere os algarismos 1, 2, 3, 4 e 5. Quantos números distintos, superiores a 100 e inferiores a 1.000, podemos for mar se: (a) o número é par?
(b) o número é ímpar? (c) o número é par ou ímpar?
Exemplo 41: Quantos inteiros entre 1.000 e 9.999 têm dígitos distintos e (a) são números pares? (b) consistem inteiramente de dígitos ímpares?
Exemplo 42: Quantos números de 4 ou 5 algarismos distintos, e maiores do que 2.000, podem ser formados com os algarismos 0, 1, 3, 5 e 7?
𝑛
Vamos tentar encontrar uma expressão matemática que caracterize 𝐶𝑝, usando
o princípio multiplicativo.
COMBINAÇÕES SIMPLES:
Combinações simples de 𝑛 elementos tomados 𝑝 a 𝑝, onde 𝑛 > 1 e 𝑝 é um número natural tal que 𝑝 < 𝑛, são todas as escolhas não ordenadas de 𝑝 desses
𝑛
𝑛 elementos. Notação: 𝐶𝑝 = 𝐶𝑛,𝑝. Se 𝑝 > 𝑛, 𝑝 e 𝑛 inteiros, define-se 𝐶𝑛,𝑝 = 0.
Quando consideramos combinações simples de 𝑛 elementos tomados 𝑝 a 𝑝, temos agrupamentos de 𝑝 elementos, tomados dentre os 𝑛 elementos disponíveis, que diferem entre si apenas pela natureza dos elementos, isto é, importa somente quem participa do grupo.
Para ilustrar, vamos voltar ao Exemplo 2.20, no qual, sendo dado o conjunto
𝐴 = {1,2,3,4,5}, pede-se o número de subconjuntos de 3 elementos que podem ser formados.
FÓRMULA PARA COMBINAÇÕES SIMPLES:
𝐶𝑝 = 𝐶	=
𝑛	𝑛,𝑝
𝑛!
𝑝! 𝑛−𝑝 !
.
Exemplo 43: Quantos são os anagramas formados por 2 vogais e 3 consoantes escolhidas dentre 18 consoantes e 5 vogais?
Exemplo	44:	Quantos	anagramas	da	palavra	UNIFORMES	come	çam	por consoante e terminam cm vogal?
Exemplo 45: Quantos triângulos diferentes podem ser traçados utilizando-se 14 pontos de um plano, não havendo 3 pontos alinhados?
Consideremos 𝑛 objetos distintos. O número de maneiras de escolhermos 𝑝
objetos é idêntico ao número de maneiras de escolhermos (𝑛 − 𝑝) objetos.
COMBINAÇÕES COMPLEMENTARES:
𝐶𝑝 = 𝐶𝑛−𝑝. Onde 𝐶𝑛−𝑝 é chamada combinação complementar de 𝐶𝑝.
𝑛	𝑛	𝑛	𝑛
Exemplo 46: De quantas maneiras podemos arrumar em fila 5 sinais (—) e 7 sinais (/)?
Exemplo 47: Quantas diagonais possui um polígono regular de 𝑛 lados?
Exemplo 47: De quantas maneiras pode-se escolher 3 números distintos do conjunto 𝐴 = {1,2,3, … , 50} de modo que sua soma seja um múltiplo de 3?
Exemplo	48:	De	quantas	maneiras	pode-se	escolher	3	números	naturais distintos de 1 a 30, de modo que a soma dos números escolhidos seja par?
Exemplo	49:	Dado	𝐴 = {1,2,3,4,5},	de	quantos	modos	é	possível	formar subconjuntos de 2 elementos nos quais não haja números consecutivos?
Exemplo	49:	Dado	𝐴 = {1,2,3, … , 𝑛},	de	quantos	modos	é	possível	formar subconjuntos de 𝑝 elementos nos quais não haja números consecutivos?
Exemplo 50: De quantas maneiras podemos arrumar em fila 5 sinais (—) e 7 sinais (/), de modo que não haja dois sinais (—) juntos?
Exemplo 51: Uma fila tem 20 cadeiras, nas quais devem sentar-se 8 meninas e 12 meninos. De quantos modos isso pode ser feito se 2 meninas não devem ficar em cadeiras contínuas?
Exemplo 52: Um baralho tem 52 cartas. De quantos modos diferentes podemos distribui-las entre 4 jogadores de modo que cada um receba 13 cartas?
Exemplo 53: Temos 52 mudas diferentes plantadas em pequenos vasos. De quantos modos diferentes poderemos colocá-los em 4 caixas iguais, de modo que cada caixa contenha exatamente 13 vasos?
Exemplo 54: De quantos modos podemos repartir 8 brinquedos diferentes entre três garotos, sendo que os dois mais velhos recebam 3 brinquedos cada e o mais novo receba 2 brinquedos?
Exemplo 55: De quantos modos diferentes podemos distribuir 8 bolas distintas em três caixas iguais, de modo que duas delas tenham exatamente 3 bolas cada?
Exemplo 56: De quantos modos podemos separar 20 objetos distintos em seis grupos, sendo dois grupos com 3 objetos, três grupos com 4 objetos e um grupo com 2 objetos?
REFERÊNCIAS BIBLIOGRÁFICAS
SANTOS,	J.	P.	O.;	MELLO,	M.	P.	;	MURARI,	I.	T.	C..	Introdução	à	Análise
Combinatória. 4 ed. Rio de Janeiro: Editora Ciência Moderna, 2008. v. 1, p. 400
image1.png
image2.png
image3.png
image4.png
image5.png
image6.png
image7.png
image8.png
image9.png
image10.png