====Exemplo 4.1.2====
''Um certo tipo de botao de uma fechadura de porta exige que voce insira um codigo antes que a fechadura abra.O bloqueio tem 5 botoes, numerados de 1 a 5.''
''(a) Se voce escolher um código de entrada que consiste de uma sequencia de 4 digitos, com números repetidos permitidos, quantos códigos de entrada são possíveis?''
''(b) Se voce escolher um código de entrada que consiste de uma sequencia de 4 digitos, sem repetir os números, quantos códigos de entrada são possíveis?''
[[Exemplo 4.1.2 - Solução]]
====Exemplo 4.1.3====
''Conte os numeros de instruções de impressão nesse algoritmo:
<nowiki>
de i=1 até n
de k=1 ate n
print hello
fim </nowiki>''
[[Exemplo 4.1.3 - Solução]]
====Exemplo 4.1.4====
''Conte os numeros de instruções de impressão nesse algoritmo:
<nowiki>
de i=1 até n
de k=i+1 ate n
print hello
fim </nowiki>''
[[Exemplo 4.1.4 - Solução]]
====Exemplo 4.1.5====
''Encontre o numero de palavras com 10 letras sem repeti-las:''
''(a) que não tenha vogais.''
''(b) que começam com uma vogal.''
''(c) que tenha C e V nas extremidades (em qualquer ordem).
''(d) que tenha vogais nas duas primeiras posições.
[[Exemplo 4.1.5 - Solução]]
====Exemplo 4.1.6====
''10 homens e 10 mulheres estão em uma fila:
''(a) encontre Encontre quantas possibilidades pode ser formada a fila.
''(b) encontre Encontre quantas possibilidades pode ser formada a fila se duas pessoas do mesmo sexo não podem ficar lado a lado;
''(c) encontre Encontre quantas possibilidades pode ser formada a fila se Beryl, Carol, e Darryl querem ficar juntas nesta sequencia (Carol, Beryl, and Darryl; ou Darryl, Beryl, e Carol).
[[Exemplo 4.1.6 - Solução]]
====Exemplo 4.1.7====
''Encontre o número de palavras 10 letras :
''(a) não Não contenha vogais.
''(b) começar Começar com uma vogal.
''(c) ter Ter vogais nas duas primeiras posições.
''(d) começar Começar com C e terminam com V.
''(e) começar Começar com C ou terminar com V.
''Para resolver o problema é ter em mente uma fila de dez espaços em branco :
[[Exemplo 4.1.7 - Solução]]
'''Solução:'''===Exemplos da Seção 4.2===
a) Cada um dos 10 espaços em branco da cadeia deve conter 1 das 21 consoantes,como podemos repeti-las===== Exemplo 4.Pela regra do produto: 21 X 21 X 21 X 21 X 2... X 21 1 ===== 21^10 ;
b)Há cinco opções para uma vogal ser colocada na primeira posição''Provar que em qualquer grupo de três números inteiros positivos, e não há restrições sobre os outros nove letrasexistem pelo menos dois,por isso : 5 x 26^9 cuja a soma é par. (Pág. 314)''
c)Se essas vogais devem estar nas duas primeiras posições e as letras podem ser repetidas, obtém[[Exemplo 4.2.1 -se o produto: 5² x 26^8 Solução]]
d)Se a palavra tem a forma : C===== Exemplo 4.2...V existem 26 maneiras para preencher cada uma dos oito espaços. Portanto, há 26^8 palavras desta forma.2 =====
e)Precisa-se usar ''Se forem escolhidos inteiros positivos aleatoriamente, qual é o princípio da inclusão-exclusão para evitar a dupla contagem.Sendo A¹ o conjunto de todas as palavras com 10 letras número mínimo que começam com C e A² o conjunto de todas as palavras com 10 letras podemos garantir que terminam com V: A¹ U A² = |A¹|+|A²| - |A¹ n A²| = 26^9 + 26^9 - dois dos números escolhidos sejam congruentes módulo 6. (26^8pág 314);''
===Exemplos da Seção [[Exemplo 4.2===.2 - Solução]]
===== Exemplo 4.2.1 3 =====
'''Provar Prove que em qualquer grupo conjunto de três números inteiros positivos700 palavras em inglês, existem deve haver pelo menos doisduas que começam com o mesmo par de letras (na mesma ordem), por exemplo, cuja a soma é parST OP e STAndard. (pág 314)'''
[[Contagem: Exemplo 1 4.2.3 - Solução]]
===== Contagem: Exemplo 4.2 .4 ====='''Se forem escolhidos inteiros positivos aleatoriamente, qual é o número mínimo que podemos garantir que dois dos números escolhidos sejam congruentes módulo 6. (pág 314)'''
[[Contagem: Exemplo 2 ''Cada tipo de peça de uma máquina feita em uma fábrica é carimbada com um código do formulário de letter- Solução]]digit-digit, onde os dígitos podem ser repetidos. Prove que, se 8000 peças são feitas, então, pelo menos, quatro delas devem ter o mesmo código carimbadas.(pág. 315)''
===== Contagem: [[Exemplo 3 =====4.2.4 - Solução]]
Prove ===== Exemplo 4.2.5 =====''Cada aluno é classificado como um membro de uma das seguintes classes: Freshman, Sophomore, Junior, Senior. Encontrar o número mínimo de estudantes que em qualquer conjunto devem ser escolhidos de 700 palavras em inglêsmodo a garantir que, deve haver pelo menos duas que começam com o mesmo par de letras (na , oito pertencem à mesma ordem), por exemplo, ST OP e STAndardclasse.(pág 314. 315)''
[[Contagem: Exemplo 3 4.2.5 - Solução]]
===Exemplos adicionais relativos a Seção 4.3===
'''EXEMPLO (E4, página 315)Exemplo 4.3.1'''Cada tipo de peça de uma máquina feita em uma fábrica é carimbada com um código do formulário de letter-digit-digit, onde os dígitos podem ser repetidos. Prove que, se 8000 peças são feitas, então, pelo menos, quatro delas devem ter o mesmo código carimbadas.
'''SoluçãoUma classe tem 30 alunos matriculados. De quantas maneiras pode-se:'''O numero de codigos possiveis 26 x 10 x 10 = 2600. Desde que,8000 > 3 x 2600,pelo menos 4 tenham o mesmo codigo.(pág 321)
''(a) Colocar 4 alunos em uma fila para uma foto?
'''EXEMPLO (E5, página 315b)'''Cada aluno é classificado como um membro de Colocar todos os 30 alunos em uma das seguintes classes: Freshman, Sophomore, Junior, Senior. Encontrar o número mínimo de estudantes que devem ser escolhidos de modo a garantir que, pelo menos, oito pertencem à mesma classe.fila para uma foto?
'''Solução:'(c) Colocar todos os 30 alunos em duas filas de 15 cada para uma foto?''De um grupo de 28 estudantes podem ser 7 pertencentes a cada classe.Mas se há 29 estudantes, pelo menos 8 devem ser membros da mesma classe.Portanto, o número mínimo de estudantes que deve ser escolhido é de 29.
Em outras palavras, nós estamos olhando para o número mínimo N tal que <math>|\frac{N}{[[Exemplo 4} | = 8</math>. O numero minimo é 293.1 - Solução]]
===Exemplos adicionais relativas a Seção '''Exemplo 4.3==='''EXEMPLO (E1, pág 321).2 '''Uma classe tem 30 alunos matriculados. De quantas maneiras pode-se:
(''Um certo tipo de botão de uma fechadura de porta exige que você insira um código antes que a fechadura abra.O bloqueio tem 5 botoes, numerados de 1 a) Colocar 5.O bloqueio é programado para reconhecer seis códigos de 4 alunos em uma fila para uma fotodígitos diferentes, podendo repetir os algarismos de cada código. Quantos conjuntos diferentes de códigos reconhecíveis existem?(pág 324)''
(b) Colocar todos os 30 alunos em uma fila para uma foto?[[Exemplo 4.3.2 - Solução]]
(c) Colocar todos os 30 alunos em duas filas de 15 cada para uma foto?
'''Solução:Exemplo 4.3.3 (pág 324)'''(a) Precisamos preencher a seguinte linha de quatro espaços em branco: 30 x 29 x 28 x 27. Este é o número de permutações de 4 a partir de um conjunto de 30, que é P( 30 ,4 );
(b)A resposta pode ser visualizado como o número de maneiras para preencher uma fila com 30 lacunas com os 30 estudantes, que é 30! , ou P( 30, 30 );...
(c) Podemos ver que o número de maneiras para preencher em duas filas,é cada uma com 15 espaços em branco, com os alunos 30:[[Exemplo 4.3.3 - Solução]]
Podemos então, começar por preencher a linha '''Exemplo 4.3.4'''''Quantas maneiras existem de escolher uma comissão de inferior, o que pode ser feito cinco pessoas consistindo de 30 x 29 x 28 x … x 17 x 16 maneiras. Em seguida, preencher linha superior, que pode ser feito três mulheres e dois homens de um grupo de 15! = 15 x 14 x 13… x 2 x 1 maneiras. Portanto a resposta é (30 x 29 x 28 x … x 17 x 16) x dez mulheres e sete homens?(15 x 14 x 13 x … x 2 x 1pág 324) = 30!''
'''EXEMPLO (E2, página 324)'''Um certo tipo de botão de uma fechadura de porta exige que você insira um código antes que a fechadura abra[[Exemplo 4.O bloqueio tem 5 botoes, numerados de 1 a 53.O bloqueio é programado para reconhecer seis códigos de 4 dígitos diferentes, podendo repetir os algarismos de cada código. Quantos conjuntos diferentes de códigos reconhecíveis existem?- Solução]]
'''Solução:Exemplo 4.3.5 '''Há 5⁴=625 possíveis códigos com quatro dígitos. Portanto, há C(625,6) conjuntos diferentes de códigos reconhecíveis.EXEMPLO (E3, página 324)…..
'''EXAMPLE Sendo o conjunto S = {1,2,3,...,19}. Encontre o número de subconjuntos de S com numeros iguais de inteiros pares e impares.(E4, page pág 324)'''Quantas maneiras existem de escolher uma comissão de cinco pessoas consistindo de três mulheres e dois homens de um grupo de dez mulheres e sete homens?
'''Solução:''' O número de maneiras de escolher três mulheres é C( 10,3 ) e o numero de maneiras de escolher 10 homens é C(7,2)[[Exemplo 4.Usando a regra do produto para escolher três mulheres e dois homens é C( 10,3 ) x C(7,2) = 2,520.5 - Solução]]
'''Exemplo 4.3.6 '''
'''EXEMPLO Encontre maneiras de dividir um baralho de 52 cartas, em:(E5, page pág 324)'''Sendo o conjunto S = {1,2,3,...,19}. Encontre o número de subconjuntos de S com numeros iguais de inteiros pares e impares.
'''Solução:'''Note que, existem 10 inteiros ímpares e 9 inteiros pares em S. Os subconjuntos a serem contados deve consistir de k inteiros ímpares e k inteiros pares, onde k=1,2,3,...,9. Portanto, pela regra do produto, o número de cada tipo é C(10, k) x C(9Em 4 pilhas iguais,k). Portanto, pela regra da soma, a resposta é C(10, k) x C(9classificado em A,k) + C(10B, k) x C(9,k)D;
''b)Em 4 pilhas iguais, sem classificação;''
[[Exemplo 4.3.6 - Solução]]
'''Exemplo 4.3.7 '''
'''EXEMPLO (E6Suponha que S = {1,2, . . ., page 324)'''25} . Encontre maneiras o numero de dividir um baralho subconjuntos de 52 cartastamanho 5, emtal que T:(pág 324)''
''a)Em 4 pilhas iguais, classificado em A,B,C,D;consista de 2 numeros impares e 3 numeros pares.
''b)Em 4 pilhas iguais, sem classificação;consiste de exatamente três números primos.
'''Solução:'''a) Cada pilha deve conter 52/4 = 13 cartas. Na sequencia, empilharemos A,em seguida B, depois C, e finalmente D. Então teremos C(52,13c) maneiras de obter tenha a pilha de Asoma dos seus elementos, C(39,13) maneiras de obter a pilha de B, C(26,13) maneiras de obter a pilha de C, e C(13,13)=1 maneiras de obter a pilha de D.Portanto pela regra do produto,teremos :C(52,13) x C(39,13) x C(26,13) x C(13,13) = <math>\frac{52!}{13!menor que 20.29!} .\frac{39!}{13!.26!} .\frac{26!}{13!.13!} .\frac{13!}{13!.0!} = \frac{52!}{(13!)^4} </math>
b''d) Se nas 4 pilhas não houver classificaçãotem,então podemos permutar as quatro pilhas em 4! Maneiras. Daí a resposta é a pelo menos, um número par na mesma do iten anterior dividido por 4!:<math>\frac{C(52,13).C(39,13).C(26,13).C(13,13)}{4!} = \frac{52!}{(13!)^4.4!}</math>''
[[Exemplo 4.3.7 - Solução]]
===Exemplos adicionais relativas a Seção 4.4==='''EXEMPLO (E7, page 324)Exemplo 4.4.1 '''
Supunha que S = {1,2, . . ., 25} ''Escreva a expansão de (x+2y)³. Encontre o numero de subconjuntos de tamanho 5,tal que T:(pág 328)''
a) consista de 2 numeros impares e 3 numeros pares[[Exemplo 4.4.1 - Solução]]
b) consiste de exatamente três números primos'''Exemplo 4.4.2 '''
c''Encontre o coeficiente <math>a^{17}b^{23}</math> na expansão de <math>(3a-7b) tenha a soma dos seus elementos, menor que 20^{40}</math>.(pág 328)''
d) tem, pelo menos, um número par na mesma[[Exemplo 4.4.2 - Solução]]
'''Exemplo 4.4.3 '''
'''Solução:'''Escreva a) Há 13 numeros impares; podemos escolher dois em Cexpansão de <math>(13,x^2-\frac{1}{x} ) maneiras^8</math>.Há 12 numeros pares; podemos escolher 3 em C(12,3pág 328) maneiras. Usando a regra do produto para encontrar o número de subconjuntos T, temos subconjuntos.''
b) Os numeros primos em S são 2,3,5,7,11,13,17,19, and 23, então temos C(9,3) maneiras de selecionar 3 desses numeros[[Exemplo 4.Mas também precisa selecionar 2 dos 16 números compostos para fazer T ter tamanho cinco;então C(16,2) maneiras para isso4.Portanto pela regra do produto temos C(9,3) x C(16,2)=10.080 subconjuntos possiveis T.- Solução]]
c) Há poucos subconjuntos com esta propriedade. Então é melhor neste caso, contar diretamente o conjunto de cinco números cuja soma é inferior ===Exemplos adicionais relativas a 20:1,2,3,Seção 4,.5, 1,2,3,4,6, 1,2,3,4,7,===1,2,3,'''Exemplo 4,8, 1,2,3,4,9, 1,3,4,.5,6.Assim, existem seis desses subconjuntos possiveis.1 '''
d) É mais fácil para contar o número total ''Uma padaria vende quatro tipos de biscoitos: chocolate, geleia, açúcar, manteiga de amendoim. Você pode comprar um saco com 30 biscoitos. Assumindo que a padaria tem pelo menos 30 de subconjuntos cada tipo de tamanho 5biscoito, e depois subtrair o número de subconjuntos sem números pares nelesquantos sacos contendo 30 biscoitos você poderia comprar se você deve escolher:<math>C(25, 5)-C(13,5pág 338) = 51,843</math>''
===Exemplos adicionais relativas a Seção 4.4==='''EXEMPLO (E1, página 328a)'''Escreva a expansão Ao menos 3 biscoitos de chocolate e pelo menos 6 biscoitos de manteiga de (x+2y)³.amendoim
'''Solução:'''pelo teorema binomial:<math>(x+2yb)^Exatamente 3 = \binom{3}{0} x^3(2y)^0+\binom{3}{1} x^2(2y)^1+\binom{3}{2} x^1(2y)^2+\binom{3}{3} x^0(2y)^3 = x^3+6x^2y+12xy^2+8y^3</math>biscoitos de chocolate e exatamente 6 biscoitos de manteiga de amendoim
'''EXEMPLO (E2, page 328c)'''Encontre o coeficiente <math>a^{17}b^{23}</math> na expansão No máximo 5 biscoitos de <math>(3a-7b)^{40}</math>.açúcar
'''Solução:'d) Pelo menos um dos quatro tipos de biscoitos.''Expandindo <math>(3a-7b)^{40}</math> usando o teorema binomial, localizamos o termo com o produto <math>a^{17}b^{23}</math>, e então encontramos o coeficiente:
<math>(3a[[Exemplo 4.5.1 -7b)^{40} = (3a+(-7b))^{40}</math>Solução]]
= <math>\cdots + \binom{40}{17} (3a)^{17}(-7b)^{23} + \cdots</math>
= <math>\cdots + \binom{40}{17} 3^{17}(-7)^23a^{17}b^{23} + \cdots</math>
Assim, o coeficiente de <math>a^{17}b^{23}</math> é <math>\binom{40}{17} 3^{17}(-7)^{23}</math>, que também pode ser escrito como <math>\binom{40}{23} 3^{17}(-7)^{23}</math>'''Exemplo 4.5.2 '''
'''EXEMPLO Quantos anagramas podem ser formados pela palavra DECEIVED? (E3, page 328pág 339)'''Escreva a expansão de <math>(x^2-\frac{1}{x} )^8</math>
'''Solução:'''Usa-se o teorema binomial[[Exemplo 4. Em seguida, várias regras exponenciais para simplificar os termos5.2 - Solução]]
<math>(x^2-\frac{1}{x} )^8 = \sum_{i=0}^{8} \binom{8}{i} (x^2)^i(\frac{-1}{x} )^{8-i}</math>
<math>= \sum_{i=0}^{8} \binom{8}{i} \frac{x^{2i}(-1)^{8-i}}{x^{8-i}}</math>
<math>= \sum_{i=0}^{8} \binom{8}{i} x^{3i-8}(-1)^{8-i}</math>
<math>= x^{-8}-8x^{-5}+28x^{-2}-56x^{1}+70x^{4}-56x^{7}+28x^{10}-8x^{13}+x^{16}</math>
<math>= \frac{1}{x^8} -\frac{8}{x^5} +\frac{28}{x^2} -56x^{1}+70x^{4}-56x^{7}+28x^{10}-8x^{13}+x^{16}</math>
===Exemplos adicionais relativas a Seção '''Exemplo 4.5===.3'''EXEMPLO (E1, page 338)'''Uma padaria vende quatro tipos de biscoitos: chocolate, geleia, açúcar, manteiga de amendoim. Você pode comprar um saco com 30 biscoitos. Assumindo que a padaria tem pelo menos 30 de cada tipo de biscoito, quantos sacos contendo 30 biscoitos você poderia comprar se você deve escolher:
a) Ao menos 3 biscoitos ''Um frasco contém 30 moedas de 1 centavo, 20 moedas de 5 centavos, 20 moedas de chocolate 10 centavos, e pelo menos 6 biscoitos 15 moedas de manteiga 25 centavos. (As moedas de amendoimcada denominação são consideradas idênticas.) (pág 339)''
b''(a) Exatamente 3 biscoitos Encontre o número de chocolate e exatamente 6 biscoitos maneiras de manteiga de amendoimcolocar todas as 85 moedas em uma fileira.
c''(b) No máximo 5 biscoitos Encontre o número de açúcarpossíveis ‘punhados’ de 12 moedas.''
d) Pelo menos um dos quatro tipos de biscoitos[[Exemplo 4.5.3 - Solução]]
Solução:
'''EXEMPLO (E2, page 339)Exemplo 4.5.4'''Quantos anagramas podem ser formados pela palavra DECEIVED?
'''Solução: 'De quantas maneiras é possivel colocar 7 das 8 letras de “CHEMISTS” em uma fila? (pág 339)''Na palavra há dois ‘D’, três ‘E’, um ‘C’, um ‘I’ e um ‘V’. Portanto, o número de permutações de DECEIVED é: <math>\frac{8!}{2!.3!.1!.1!.1!} = \frac{8!}{2!.3!}</math>
'''EXEMPLO (E3, page 339)'''Um frasco contém 30 moedas de 1 centavo, 20 moedas de [[Exemplo 4.5 centavos, 20 moedas de 10 centavos, e 15 moedas de 25 centavos. (As moedas de cada denominação são consideradas idênticas.)4 - Solução]]
(===Exemplos adicionais relativas a) Encontre o número de maneiras de colocar todas as 85 moedas em uma fileiraSeção 4.6==='''Exemplo 4.6.1'''
''Coloque as seguintes permutações de 1, 2, 3, 4, 5, 6, na ordem lexicográfica : (bpág 345) Encontre o número de possíveis ‘punhados’ de 12 moedas.''
'''Solução:'''(a) A resposta não é 85! uma vez que as moedas não são todos distintos. Pense no problema como um de fazer uma palavra com 30 p's, 20 n's, 20 d's, e 15 q's. Tendo em conta as cartas idênticas, temos<math>\frac{85!}{30!.20!.20!.15!}</math> (b) Quando se contar o número de ‘punhados’ de 12 moedas, estamos apenas preocupados com o número de cada denominação escolhida. Por exemplo, poderíamos escolher 9 moedas de 1 centavos, 2 de 5 centavos, e uma de 25 centavos461325, ou podemos escolher três de cada denominação. Assim326145, o número de um ‘punhados’ de 12 moedas é igual ao número inteiro não negativo de soluções para a equação:<math>p+n+d+q = 12</math>onde P é o número de moedas de 1 centavo516243, n é o número de moedas de 5 centavos324165, d é o número de moedas de 10 centavos461235, e q é o número de 25 centavos. O número de soluções para esta equação é:<math>C(15324615,3) = 455462135</math>
'''EXEMPLO (E4, page 339)'''De quantas maneiras é possivel colocar 7 das 8 letras de “CHEMISTS” em uma fila?[[Exemplo 4.6.1 - Solução]]
'''Solução:'''
Existem dois padrões a serem considerados:'''Exemplo 4.6.2'''
(''Encontre a) 7 letras distintas são selecionados permutação de 1, 2, 3, 4, 5, 6 imediatamente após 263.541 em ordem lexicográfica. (ou seja, apenas um S é selecionadopág 345), e''
(b) os dois S serem selecionados[[Exemplo 4.6.2 - Solução]]
No primeiro teste padrão, existem 7! Maneiras de colocar as 7 letras distintas em uma fileira.
No segundo padrão, as sete letras selecionadas têm dois S’s, por isso há 7! / 2! Maneiras de colocar essas letras em uma fileira'''Exemplo 4. 6.3 '''
Adicionando os totais obtidos a partir dos dois casos, temos o número total de maneiras de colocar sete dos oito cartas em uma fileira:<math>7!+6.\frac{7!}{2!}</math> ===Exemplos adicionais relativas a Seção 4.6==='''EXEMPLO (E1, página 345)'''Coloque as seguintes permutações Encontre a permutação de 1, 2, 3, 4, 5, 6, na imediatamente antes de 261.345 em ordem lexicográfica : <math>461325, 326145, 516243, 324165, 461235, 324615, 462135</math>. (pág 345)''
[[Exemplo 4.6.3 - Solução: EXEMPLO (E1, página 345)]]
'''EXEMPLO (E2, página 345)'''
Encontre a permutação de 1, 2, 3, 4, 5, 6 imediatamente após 263.541 em ordem lexicográfica.
[[Solução: EXEMPLO (E2, página 345)]]'''Exemplo 4.6.4 '''
'''EXEMPLO (E3, página 345)'''Encontre a permutação Se as permutações de 1, 2, 3, 4, 5, 6 imediatamente antes de 261.345 forem colocadas em ordem lexicográfica, com 123.456 na posição 1, 123.465 na posição 2, etc., encontrar a permutação na posição 362. (pág 345)''
[[Exemplo 4.6.4 - Solução: EXEMPLO (E3, página 345)]]
'''EXEMPLO (E4, página 345)'''
Se as permutações de 1,2,3,4,5,6 forem colocadas em ordem lexicográfica, com 123.456 na posição 1, 123.465 na posição 2, etc., encontrar a permutação na posição 362.
[[Solução: EXEMPLO (E4, página 345)]]'''Exemplo 4.6.5 '''
'''EXEMPLO (E5, página 345)'''Se as permutações de 1,2,3,4,5 forem colocadas em ordem lexicográfica, em que posição estará a permutação 41253?(pág 345)''
[[Exemplo 4.6.5 - Solução: EXEMPLO (E5, página 345)]]