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é.