Matemática Discreta - Teoria da Contagem
Na vida diária, muitas vezes é necessário descobrir o número de todos os resultados possíveis para uma série de eventos. Por exemplo, de quantas maneiras um painel de juízes composto por 6 homens e 4 mulheres pode ser escolhido entre 50 homens e 38 mulheres? Quantos números PAN com 10 letras diferentes podem ser gerados, de modo que as primeiras cinco letras sejam letras maiúsculas, as próximas quatro sejam dígitos e a última seja novamente uma letra maiúscula. Para resolver esses problemas, a teoria matemática da contagem é usada.Counting abrange principalmente a regra de contagem fundamental, a regra de permutação e a regra de combinação.
As regras de soma e produto
o Rule of Sum e Rule of Product são usados para decompor problemas de contagem difíceis em problemas simples.
The Rule of Sum- Se uma sequência de tarefas $ T_1, T_2, \ dots, T_m $ pode ser feita em $ w_1, w_2, \ dots w_m $ maneiras respectivamente (a condição é que nenhuma tarefa pode ser executada simultaneamente), então o número de maneiras de fazer uma dessas tarefas é $ w_1 + w_2 + \ dots + w_m $. Se considerarmos duas tarefas A e B que são disjuntas (ou seja, $ A \ cap B = \ emptyset $), então matematicamente $ | A \ cup B | = | A | + | B | $
The Rule of Product- Se uma sequência de tarefas $ T_1, T_2, \ dots, T_m $ pode ser feita em $ w_1, w_2, \ dots w_m $ maneiras respectivamente e cada tarefa chega após a ocorrência da tarefa anterior, então há $ w_1 \ times w_2 \ times \ dots \ times w_m $ formas de executar as tarefas. Matematicamente, se uma tarefa B chegar depois de uma tarefa A, então $ | A \ vezes B | = | A | \ vezes | B | $
Exemplo
Question- Um menino mora em X e quer ir para a escola em Z. De sua casa X, ele deve primeiro chegar a Y e depois de Y a Z. Ele pode ir de X a Y por 3 linhas de ônibus ou 2 linhas de trem. A partir daí, ele pode escolher 4 rotas de ônibus ou 5 rotas de trem para chegar a Z. Quantas maneiras existem para ir de X a Z?
Solution- De X para Y, ele pode ir em $ 3 + 2 = 5 $ maneiras (Regra da Soma). Depois disso, ele pode ir de Y a Z em $ 4 + 5 = 9 $ maneiras (Regra da Soma). Portanto, de X a Z ele pode ir em $ 5 \ vezes 9 = 45 $ maneiras (Regra do Produto).
Permutações
UMA permutationé um arranjo de alguns elementos em que a ordem é importante. Em outras palavras, uma Permutação é uma combinação ordenada de elementos.
Exemplos
De um conjunto S = {x, y, z} tomando dois de cada vez, todas as permutações são -
$ xy, yx, xz, zx, yz, zy $.
Temos que formar uma permutação de números de três dígitos a partir de um conjunto de números $ S = \ lbrace 1, 2, 3 \ rbrace $. Diferentes números de três dígitos serão formados quando organizarmos os dígitos. A permutação será = 123, 132, 213, 231, 312, 321
Número de Permutações
O número de permutações de 'n' coisas diferentes tomadas 'r' de cada vez é denotado por $ n_ {P_ {r}} $
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
onde $ n! = 1.2.3. \ pontos (n - 1) .n $
Proof - Que haja 'n' elementos diferentes.
Existem várias maneiras de preencher o primeiro lugar. Depois de preencher o primeiro lugar (n-1), resta o número de elementos. Portanto, existem (n-1) maneiras de preencher a segunda posição. Depois de preencher a primeira e a segunda posições, resta (n-2) o número de elementos. Portanto, existem (n-2) maneiras de preencher a terceira posição. Agora podemos generalizar o número de maneiras de preencher a r-ésima casa como [n - (r – 1)] = n – r + 1
Portanto, o total não. de maneiras de preencher do primeiro ao résimo lugar -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ pontos 3.2.1] / [(nr) (nr-1) \ pontos 3.2.1] $
Conseqüentemente,
$ n_ {P_ {r}} = n! / (nr)! $
Algumas fórmulas importantes de permutação
Se houver n elementos dos quais $ a_1 $ são semelhantes de algum tipo, $ a_2 $ são semelhantes de outro tipo; $ a_3 $ são semelhantes de terceiro tipo e assim por diante e $ a_r $ são de $ r ^ {th} $ tipo, onde $ (a_1 + a_2 + ... a_r) = n $.
Então, o número de permutações desses n objetos é = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.
Número de permutações de n elementos distintos levando n elementos de cada vez = $ n_ {P_n} = n! $
O número de permutações de n elementos diferentes tomando r elementos de cada vez, quando x coisas particulares sempre ocupam lugares definidos = $ n-x_ {p_ {rx}} $
O número de permutações de n elementos diferentes quando r coisas especificadas sempre vêm juntas é - $ r! (n − r + 1)! $
O número de permutações de n elementos diferentes quando r coisas especificadas nunca se encontram é - $ n! - [r! (n − r + 1)!] $
O número de permutações circulares de n elementos diferentes tomados x elementos no tempo = $ ^ np_ {x} / x $
O número de permutações circulares de n coisas diferentes = $ ^ np_ {n} / n $
Alguns problemas
Problem 1 - De um monte de 6 cartas diferentes, de quantas maneiras podemos permutá-lo?
Solution- Como estamos pegando 6 cartas por vez de um baralho de 6 cartas, a permutação será $ ^ 6P_ {6} = 6! = 720 $
Problem 2 - De quantas maneiras as letras da palavra 'READER' podem ser arranjadas?
Solution - Existem 6 letras de palavras (2 E, 1 A, 1D e 2R.) Na palavra 'READER'.
A permutação será $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - De que forma as letras da palavra 'LARANJA' podem ser arranjadas de forma que as consoantes ocupem apenas as posições pares?
Solution- Existem 3 vogais e 3 consoantes na palavra 'LARANJA'. Número de maneiras de arranjar as consoantes entre si $ = ^ 3P_ {3} = 3! = 6 $. As 3 vagas restantes serão preenchidas por 3 vogais em $ ^ 3P_ {3} = 3! = 6 $ maneiras. Portanto, o número total de permutação é $ 6 \ vezes 6 = 36 $
Combinações
UMA combination é a seleção de alguns elementos dados em que a ordem não importa.
O número de todas as combinações de n coisas, tomadas r de cada vez é -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
Encontre o número de subconjuntos do conjunto $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ com 3 elementos.
Solution
A cardinalidade do conjunto é 6 e temos que escolher 3 elementos do conjunto. Aqui, a ordem não importa. Portanto, o número de subconjuntos será $ ^ 6C_ {3} = 20 $.
Problem 2
Há 6 homens e 5 mulheres em um quarto. De quantas maneiras podemos escolher 3 homens e 2 mulheres na sala?
Solution
O número de maneiras de escolher 3 homens entre 6 homens é $ ^ 6C_ {3} $ e o número de maneiras de escolher 2 mulheres entre 5 mulheres é $ ^ 5C_ {2} $
Portanto, o número total de maneiras é - $ ^ 6C_ {3} \ vezes ^ 5C_ {2} = 20 \ vezes 10 = 200 $
Problem 3
De quantas maneiras você pode escolher 3 grupos distintos de 3 alunos de um total de 9 alunos?
Solution
Vamos numerar os grupos como 1, 2 e 3
Para escolher 3 alunos para o 1º grupo, o número de maneiras - $ ^ 9C_ {3} $
O número de maneiras de escolher 3 alunos para o 2º grupo após a escolha do 1º grupo - $ ^ 6C_ {3} $
O número de maneiras de escolher 3 alunos para o 3º grupo depois de escolher o 1º e o 2º grupos - $ ^ 3C_ {3} $
Portanto, o número total de maneiras $ = ^ 9C_ {3} \ vezes ^ 6C_ {3} \ vezes ^ 3C_ {3} = 84 \ vezes 20 \ vezes 1 = 1680 $
Identidade de Pascal
Identidade de Pascal, primeira derivada por Blaise Pascal em 17 th século, estados que o número de maneiras de escolher k elementos de n elementos é igual à soma do número de maneiras de escolher elementos (k-1) a partir de (n-1) elementos e o número de maneiras de escolher elementos de n-1 elementos.
Matematicamente, para quaisquer inteiros positivos k e n: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $
Proof -
$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$
$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $
$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $
$ = (n-1)! \ frac {n} {k! (nk)! } $
$ = \ frac {n! } {k! (nk)! } $
$ = n_ {C_ {k}} $
Princípio Pigeonhole
Em 1834, o matemático alemão Peter Gustav Lejeune Dirichlet estabeleceu um princípio que chamou de princípio da gaveta. Agora, é conhecido como o princípio do escaninho.
Pigeonhole Principleafirma que, se houver menos pombos do que o número total de pombos e cada pombo for colocado em uma pomba, então deve haver pelo menos um pombo com mais de um pombo. Se n pombos forem colocados em m escaninhos onde n> m, haverá um buraco com mais de um pombo.
Exemplos
Dez homens estão em uma sala e participam de apertos de mão. Se cada pessoa aperta a mão pelo menos uma vez e nenhum homem aperta a mão do mesmo homem mais de uma vez, então dois homens participam do mesmo número de apertos de mão.
Deve haver pelo menos duas pessoas em uma classe de 30 alunos cujos nomes comecem com o mesmo alfabeto.
O princípio de inclusão-exclusão
o Inclusion-exclusion principlecalcula o número cardinal da união de vários conjuntos não disjuntos. Para dois conjuntos A e B, o princípio afirma -
$ | A \ xícara B | = | A | + | B | - | A \ cap B | $
Para três conjuntos A, B e C, o princípio afirma -
$ | A \ xícara B \ xícara C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $
A fórmula generalizada -
$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ soma \ limites_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ soma \ limites_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $
Problem 1
Quantos inteiros de 1 a 50 são múltiplos de 2 ou 3, mas não ambos?
Solution
De 1 a 100, existem $ 50/2 = 25 $ números que são múltiplos de 2.
Existem $ 50/3 = 16 $ números que são múltiplos de 3.
Existem $ 50/6 = 8 $ números que são múltiplos de 2 e 3.
Portanto, $ | A | = 25 $, $ | B | = 16 $ e $ | A \ cap B | = 8 $.
$ | A \ xícara B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $
Problem 2
Em um grupo de 50 alunos, 24 gostam de bebidas geladas e 36 gostam de bebidas quentes e cada aluno gosta de pelo menos uma das duas bebidas. Quantos gostam de café e chá?
Solution
Seja X o conjunto de alunos que gostam de bebidas frias e Y o conjunto de pessoas que gostam de bebidas quentes.
Então, $ | X \ xícara Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $
$ | X \ cap Y | = | X | + | Y | - | X \ xícara Y | = 24 + 36 - 50 = 60 - 50 = 10 $
Portanto, há 10 alunos que gostam tanto de chá quanto de café.