Uma interpretação para o princípio aditivo é: suponha que o evento pode ocorrer maneiras e o evento de maneiras distintas das outras . Então, o número de maneiras de ocorrer o evento “ \underline{ou} ” é . No caso geral, se são conjuntos dois-a-dois disjuntos então
Por exemplo, há quantas possibilidades de escolher um inteiro entre e que é múltiplo de ou de ? Devemos determinar a cardinalidade do conjunto de inteiros entre e que são múltiplos de ou múltiplos de , tais conjuntos são disjuntos pois . Os múltiplos de são cinco, os múltiplos de são dois, portanto, os múltiplos de ambos são . O evento múltiplo de ou múltiplo de ocorre de modos distintos.
Teorema 43 (Princípio de Inclusão–Exclusão) Se e são conjuntos finitos (não necessariamente disjuntos) então
Demonstração:
Sejam
e
conjuntos finitos. Podemos escrever
como a seguinte união de subconjuntos disjuntos (verifique)
portanto, pelo princípio aditivo
Também podemos escrever como uma união disjunta (verifique)
portanto donde deduzimos
Substituindo (42) em (41)
Por exemplo, o número de possíveis resultados que são múltiplo de 2 ou de 3 no lançamento de uma dado é dado por: os múltiplos de 2 definem o subconjunto , os múltiplos de 3 definem o subconjunto , portanto,
Exercício 37 Prove que se , e são conjuntos finitos então
Exemplo: Em uma academia de arte, há 43 estudantes que tomam aula de cerâmica, 57 estudantes que fazem pintura e 29 estudantes que tomam aula de escultura. Há 10 alunos em cerâmica e pintura, 5 em pintura e escultura, 5 em cerâmica e escultura e 2 tendo todos os três cursos. Quantos alunos alunos estão fazendo pelo menos um curso na academia de arte? Vamos indicar por , e os conjuntos de alunos que fazem cerâmica, pintura e escultura, respectivamente. Queremos calcular . Aplicamos inclusão–exclusão: .
Exercício 38 De quantas maneiras podemos escolher um número em que não é divisível por , ou ?
Uma interpretação para o princípio multiplicativo é: se um evento pode ser descrito em duas etapas de modo que há desfechos possíveis para a etapa e há desfechos possíveis para a etapa, então o número de possíveis desfechos para o evento é .
De um modo geral, se , … representam etapas de evento composto, então o números de modos distintos de realizar o evento é
que pode ser demonstrado usando princípio da indução.
Exercício 41 Uma placa de carro é uma sequência de 3 letras seguidas por 4 dígitos. Qual é a quantidade de placas distintas que podemos obter?
Esboço de solução: para .
para .
.
Exemplo: Cada posição da memória (célula de memória) de um computador tem um endereço que é uma sequência binária. As arquiteturas com processadores 32-bits tem capacidade para endereçamento de posições de memória, aproximadamente Gigabytes. As arquiteturas com processadores 64-bits tem capacidade para endereçamento de
posições de memória, aproximadamente Exabytes (16 milhões de Terabytes). Suponhamos que um dispositivo de Gigabyte ocupe um dispositivo de dimensões . Para guardar Exabytes precisaríamos de uma quarto de dimensões .
A seguir destacamos alguns casos particulares do princípio multiplicativo. Essencialmente são dois tipos de listas: arranjos e combinações. Nos arranjos a ordem dos elementos importa e nas combinações a ordem não importa.
9.1. Arranjos
Quantas palavras (sequências) de 3 letras distintas do alfabeto latino podem ser formadas? Como o alfabeto tem 26 letras, pelo princípio multiplicativo são palavras.
Definição 27 Um arranjo simples de elementos tomados de um conjunto de elementos é uma sequência de elementos não repetidos de . A quantidade de arranjos simples de elementos tomados de um conjunto de elementos () é o número dado por
Quando é permitido repetição dizemos arranjo com repetição que é um caso particular do Princípio Multiplicativo com todos os conjuntos iguais. A quantidade de arranjos com repetição de elementos tomados de um conjunto de elementos é o número .
Por arranjo nos referimos a arranjo simples. Alguns textos usam a notação para .
Exemplo: De quantas maneiras podemos escolher um inteiro entre e (inclusive e com 3 dígitos) com todos os dígitos distintos? O conjunto tem elementos e a quantidade deles sem dígitos repetidos é .
Paradoxo do aniversário: Com que probabilidade ocorre que num grupo com 25 pessoas 2 ou mais pessoas façam aniversário no mesmo dia? O aniversário de 25 pessoas pode ocorrer de modos diferentes. O aniversário de 25 pessoas sem que nenhum deles coincida pode ocorrer de modos diferentes. Portanto, há possibilidades diferentes para o aniversário de 25 pessoas com pelo menos duas aniversariando no mesmo dia; a probabilidade desse evento é
Com 55 pessoas a probabilidade é maior que .
Exercício 42 Sejam e conjuntos finitos com . Há quantas funções injetivas de em ? E quantas são as funções de em ?
Permutação
Exemplo: De quantas maneiras diferentes 8 alunos podem se sentar numa sala com 8 cadeiras? O primeiro aluno tem 8 opções, o segundo tem 7, o terceiro tem 6, o quarto tem 5, o quinto tem 4, o sexto tem 3, o sétimo tem 2 e para o oitavo resta 1 opção. Logo há maneiras dos 8 alunos sentarem nas 8 cadeiras.
O caso de arranjo simples com é uma permutação. Quantas palavras com letras distintas podem ser formadas com as letras , e ? Pelo princípio multiplicativo são palavras.
Definição 28 Uma permutação de elementos de um conjuntos é uma sequência de elementos de . O número de permutações dos elementos de um conjunto de elementos é
Exemplo: O número de permutações possíveis com as letras , , , e é . O número de permutações possíveis com as letras , , , , e é .
Exemplo: A quantidade de permutações que podem ser formadas com as letras da palavra é . A quantidade de permutações que podem ser formadas com as letras da palavra é . A quantidade de permutações que podem ser formadas com as letras da palavra é . A quantidade de permutações que podem ser formadas com as letras da palavra é . A quantidade de permutações que podem ser formadas com as letras da palavra é . A quantidade de permutações que podem ser formadas com as letras da palavra é . A quantidade de permutações que podem ser formadas com as letras da palavra é .
Perceba que o fatorial cresce bastante rápido com
:
é mais que a quantidade de segundos que passam em
ano.
é mais que a quantidade de segundos que passam em
anos.
é mais que a quantidade de segundos que passam em
anos.
Notemos que
Permutação com repetição
Exercício 43 Qual é o número de permutações distintas com as letras da palavra ?
Solução: [Solução] São
permutações de 3 símbolos, mas há permutações que dão origem a mesma sequência. As seis permutações de ana são:
ana, ana,
aan, aan, naa, naa
em cada duas permutações a palavra é a mesma, só muda a ordem da letra repetida, portanto são
permutações distintas.
Exercício 44 Qual é o número de permutações distintas com as letras da palavra ?
Solução: da mesma maneira, das permutações as permutações que troca a ordem da letra igual e deixam as outras letras na mesma posição da sequência geram a mesma palavra, portanto são
permutações distintas.
Exercício 45 Qual é o número de permutações distintas com as letras da palavra ?
Solução: São permutações de 6 símbolos. Mas agora há permutações que diferem apenas na ordem das letras ou das letras e dão origem a mesma sequência, por exemplo: são permutações diferentes que determinam a mesma sequência. As permutações das letras são indistinguíveis, assim como as da letras , portanto, há
permutações distintas.
Exercício 46 Um sinal é composto por nove bandeiras alinhadas. Quantos sinais diferentes é possível formar quando há disponíveis 4 bandeiras brancas, três bandeiras vermelhas e duas bandeiras azuis? Bandeiras da mesma cor são idênticas.
Esboço de solução: .
Definição 29 No caso de permutações com repetição de objetos, se são objetos no total, com tipos de objetos distintos e objetos do tipo (, ) então temos permutações donde descontamos as permutações de objetos do mesmo tipo resultando
Mão de bridge: Numa mão de Bridge as 52 cartas de um baralho embaralhado são divididas igualmente entre 4 jogadores. O número de modos distintos com que isso é feito pode ser calculado da seguinte forma: uma distribuição de cartas corresponde a uma sequência de 52 objetos, os 13 primeiros objetos da sequência são as cartas do primeiro jogador, os 13 seguintes do segundo jogador, os próximos 13 do terceiro e os 13 últimos objetos da sequência são as cartas do quarto jogador. Há sequências distintas de cartas. Entretanto, dessas temos que, para cada jogador, permutações correspondem a mesma sequência de cartas em sua mão, portanto, são
modos distintos de distribuir as cartas, ou mãos diferentes de início de jogo.
Exercício 47 Se numa mão de Bridge as 52 cartas de um baralho são divididas igualmente e aleatoriamente entre 4 jogadores. Com que probabilidade cada jogador recebe um ás?
Solução: Os 4 ases podem ser distribuídos de modos distintos entregando um para cada jogador. As 48 cartas restantes são distribuídas pelos jogadores de maneiras distintas. Pelo princípio multiplicativo são modos distintos de os jogadores receberem um ás cada. Portanto a probabilidade é
que vale aproximadamente .
Exercício 48 Quantos são as permutações das letras da palavra MATEMÁTICA?
Permutação circular
De quantos modos 5 crianças podem formar uma roda de ciranda? As rodas , e , por exemplo, são iguais pois importa apenas a posição relativa entre as crianças. Assim cada roda pode ser girada de cinco maneiras e a resposta correta é
Definição 30 O número de permutações circulares de objetos distintos, se consideramos equivalentes disposições que possam coincidir por rotação, é igual a
Aproximação de Stirling
Duas sequências de números e são assintoticamente iguais e escrevemos , se
Frequentemente, é muito útil quanto trabalhamos com fatoriais a seguinte igualdade assintótica conhecida como fórmula de Stirling
| stirling | ||
9.6. Combinações
Tomemos um arranjo de elementos escolhidos de um conjunto com elementos. A quantidade de arranjos que têm os mesmos elementos é pois a única diferença entre eles é a ordem com que se apresentam os elementos. Por exemplo, se selecionamos sequencialmente e sem reposição cartas de um baralho então temos arranjos distintos, um dos quais é . Agora, se selecionamos três cartas de uma só vez as permutações de correspondem a mesma seleção. A quantidade de seleções distintas é
Exercício 49 Seja um conjunto com elementos. Dado , , quantos subconjuntos de cardinalidade estão contidos em ?
Solução: Denote por a quantidade de subconjuntos de cardinalidade estão contidos em .
Um único subconjunto de tamanho determina arranjos de elementos de . Subconjuntos distintos determinam arranjos distintos, portanto, , ou seja
Usando (48)
Definição 31 Uma combinação de elementos escolhidos de um conjunto com elementos é simplesmente um subconjunto com elementos de . A quantidade de subconjuntos de com elementos, para , é o coeficiente binomial
Convencionamos que se .
Exemplo (Mega-Sena): O jogo de apostas consiste em acertar 6 dezenas escolhidas dentre 60. O número de possíveis resultados distinto para a Mega-Sena é . Se uma aposta em seis números demorar 1 segundo para ser registrada, então registrar demoraria um ano e meio, aproximadamente. A probabilidade de acertar os seis números é
A chance de morrer por raio no Brasil em 2010 era (40 vezes maior. Esse número é uma média no sentido de que considera que todos têm a mesma chance de ser atingido, o que não é real).
Exemplo: Numa população com elementos, são azuis e são verdes. De quantas maneiras podemos escolher elementos com deles azuis? O número de maneiras de escolher verdes é . O número de maneiras de escolher azuis é . Pelo Princípio Multiplicativo, o número de maneiras de escolher azuis e verdes é .
Exercício 50 Prove que a seguinte identidade
Exercício 51 Três bolas são retiradas aleatoriamente de uma caixa com 6 bolas brancas e 5 bolas pretas. Com que probabilidade a escolha resulta em 1 branca e 2 pretas?
Solução: No total são 13 bolas das quais escolhemos 3. O número de possíveis resultados é . “6 bolas brancas e 5 bolas pretas” ocorre de modos diferentes, pelo exercício anterior. Portanto a probabilidade é
Combinação com repetição
Se escolhemos uma peça de dómino ao acaso, com que probabilidade obtemos
As peças de dominós são formadas por dois números tomados dos números de 0 a 6 podendo haver repetição. Os dominós com pares de números diferentes são , mais os pares repetidos resultam em peças de dominós, portanto, são combinações de 2 objetos tomados dentre 7 com repetição. Essa estratégia de contagem não é facilmente generalizável, o leitor pode tentar contar o número de peças de dominós de 5 pontas com 16 possíveis números diferentes, o resultado deverá ser .
A resposta para o caso geral: dentre objetos, queremos selecionar podendo haver repetição e sem considerar ordem. Isso pode ser feito de
maneiras diferentes. No caso dos dominós, por exemplo, são números dos quais selecionamos , podendo repetir número
Uma maneira de modelar combinação com repetição para deduzir equação (52) é escrever uma equação com uma indeterminada para cada um dos objetos, . A variável indica quantas vezes o -ésimo objeto será selecionado, portanto . Assim, o número combinações com repetição é a quantidade de soluções inteiras de
Soluções inteiras de equações lineares
Vamos começar com um caso simples, estudaremos o número de soluções de
Escrevemos
e uma solução da equação (54) corresponde a escolha de operadores dentre os escritos na equação acima; por exemplo, se usamos para representar as escolhas
corresponde a , e , e
corresponde a , e . Portanto essa equação tem soluções em .
Agora, estudaremos o número de soluções de
Notemos que uma solução inteira e positiva da equação determina uma única solução inteira e não-negativa da equação e vice-versa, ou seja, as equações
têm o mesmo número de soluções.
De volta ao problema que gerou essa discussão: o número de maneiras de selecionar objetos, podendo haver repetição, dentre objetos é igual ao número de soluções inteiras da equação (53), que é o mesmo número de soluções inteiras de
consideramos e dos operadores escolhemos , ou seja, são soluções inteiras. Finalmente, a equação (52) segue do seguinte exercício
Exercício 52 Verifique que vale
para todo e todo para os quais os coeficientes binomiais estão definidos.
A quantidade de maneiras diferentes de selecionarmos elementos de um conjunto de elementos é,
9.9. Binômio de Newton
Se é um conjunto com elementos então a quantidade de subconjuntos de de cardinalidade é o número de maneiras distintas que podemos selecionar elementos dentre os do conjunto, isto é, são subconjuntos, como há subconjuntos de concluímos que
Esse fato é consequência, também, de um resultado mais geral conhecido como Teorema Binomial.
Teorema 46 (Teorema Binomial) Para todo , vale
Fazendo temos a equação (61).
Vejamos como o produto de desenvolve para valores pequenos de
Assim,
com ocorrências de . Desenvolvendo o produto temos uma soma em que cada termo é da forma , para . Para cada o coeficiente de é o número de maneiras de escolher o de fatores da equação (62) (para o , dos fatores restantes). O número de maneiras de escolher fatores dentre é , portanto
Exercício: Se , e são três subconjuntos de , prove que há ternas com .
[Solução]
Coeficiente multinomial
De volta ao exemplo mão de bridge, se dividimos a tarefa de distribuir as cartas em 4 etapas, cada etapa seleciona 13 cartas para um jogador, então pelo princípio multiplicativo o número de maneiras distintas de distribuir as cartas no jogo de bridge é
Com raciocínio análogo ao feito para o Teorema Binomial,
e, de modo geral,
Teorema 47 (Teorema Multinomial) Para todo , vale
de modo que é conhecido como coeficiente multinomial.