====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.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]]
===== Exemplo 4.2.1 =====
'''Provar que em qualquer grupo de três números inteiros positivos, existem pelo menos dois, cuja a soma é par. (Pág. 314)'''
[[Exemplo 4.2.1 - Solução]]
===== Exemplo 4.2.2 =====
'''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 4.2.2 - Solução]]
===== Exemplo 4.2.3 =====
''Prove que em qualquer conjunto de 700 palavras em inglês, deve haver pelo menos duas que começam com o mesmo par de letras (na mesma ordem), por exemplo, ST OP e STAndard.(pág 314)'' [[Exemplo 4.2.3 - Solução]] ===== Exemplo 4.2.4 =====
[[Contagem: Exemplo 3 ''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)''
[[Exemplo 4.2.4 - Solução]]
===== Exemplo 4.2.5 ====='''EXEMPLO (E4, página 315)'''Cada tipo de peça de uma máquina feita em uma fábrica aluno é carimbada com classificado como um código do formulário membro de letter-digit-digituma das seguintes classes: Freshman, Sophomore, Junior, onde os dígitos podem Senior. Encontrar o número mínimo de estudantes que devem ser repetidos. Prove escolhidos de modo a garantir que, se 8000 peças são feitas, então, pelo menos, quatro delas devem ter o mesmo código carimbadasoito pertencem à mesma classe.(pág.315)''
'''Solução:'''O numero de codigos possiveis 26 x 10 x 10 = 2600[[Exemplo 4. Desde que,8000 > 3 x 2600,pelo menos 4 tenham o mesmo codigo2.5 - Solução]]
===Exemplos adicionais relativos a Seção 4.3===
'''EXEMPLO (E5, página 315)Exemplo 4.3.1'''Cada aluno é classificado como um membro de 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.
'''Solução:'''De um grupo de 28 estudantes podem ser 7 pertencentes a cada Uma classetem 30 alunos matriculados.Mas De quantas maneiras pode-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.: (pág 321)
Em outras palavras, nós estamos olhando ''(a) Colocar 4 alunos em uma fila para o número mínimo N tal que <math>|\frac{N}{4} | = 8</math>. O numero minimo é 29.uma foto?
===Exemplos adicionais relativas a Seção 4.3==='''EXEMPLO (E1, pág 321b)'''Uma classe tem Colocar todos os 30 alunos matriculados. De quantas maneiras pode-se:em uma fila para uma foto?
''(ac) Colocar 4 todos os 30 alunos em uma fila duas filas de 15 cada para uma foto?''
(b) Colocar todos os 30 alunos em uma fila para uma foto?[[Exemplo 4.3.1 - Solução]]
(c) Colocar todos os 30 alunos em duas filas de 15 cada para uma foto?'''Exemplo 4.3.2 '''
'''Solução:'''(Um certo tipo de botão de uma fechadura de porta exige que você insira um código antes que a) Precisamos preencher fechadura abra.O bloqueio tem 5 botoes, numerados de 1 a seguinte linha de quatro espaços em branco: 30 x 29 x 28 x 275. Este O bloqueio é o número de permutações programado para reconhecer seis códigos de 4 a partir dígitos diferentes, podendo repetir os algarismos de um conjunto cada código. Quantos conjuntos diferentes de 30, que é Pcódigos reconhecíveis existem?( 30 ,4 pág 324);''
(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 );[[Exemplo 4.3.2 - Solução]]
(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:
Podemos então, começar por preencher a linha de inferior, o que pode ser feito de 30 x 29 x 28 x … x 17 x 16 maneiras'''Exemplo 4. Em seguida, preencher linha superior, que pode ser feito de 15! = 15 x 14 x 13… x 2 x 1 maneiras3. Portanto a resposta é 3 (30 x 29 x 28 x … x 17 x 16pág 324) x (15 x 14 x 13 x … x 2 x 1) = 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.O bloqueio tem 5 botoes, numerados de 1 a 5.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:'''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)…[[Exemplo 4.3.3 - Solução]]
'''EXAMPLE (E4, page 324)Exemplo 4.3.4'''''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?(pág 324)''
'''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.4 - Solução]]
'''Exemplo 4.3.5 '''
'''EXEMPLO (E5, page 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.(pág 324)''
'''Solução:'''Note que, existem 10 inteiros ímpares e 9 inteiros pares em S[[Exemplo 4. 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(9,k). Portanto, pela regra da soma, a resposta é C(10, k) x C(9,k) + C(10, k) x C(9,k)5 - Solução]]
'''Exemplo 4.3.6 '''
''Encontre maneiras de dividir um baralho de 52 cartas, em:(pág 324)''
''a)Em 4 pilhas iguais, classificado em A,B,C,D;
'''EXEMPLO (E6b)Em 4 pilhas iguais, page 324)sem classificação;'''Encontre maneiras de dividir um baralho de 52 cartas, em:
a)Em [[Exemplo 4 pilhas iguais, classificado em A,B,C,D;.3.6 - Solução]]
b)Em '''Exemplo 4 pilhas iguais, sem classificação;.3.7 '''
'''Solução:'''a) Cada pilha deve conter 52/4 Suponha que S = 13 cartas. Na sequencia{1, empilharemos A2,em seguida B. . ., depois C, e finalmente D25} . Então teremos C(52,13) maneiras Encontre o numero de obter a pilha subconjuntos de Atamanho 5, 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 tal que T:C(52,13pág 324) x C(39,13) x C(26,13) x C(13,13) = <math>\frac{52!}{13!.29!} .\frac{39!}{13!.26!} .\frac{26!}{13!.13!} .\frac{13!}{13!.0!} = \frac{52!}{(13!)^4} </math>''
b) Se nas 4 pilhas não houver classificação,então podemos permutar as quatro pilhas em 4! Maneiras. Daí ''a resposta é a 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!)^4consista de 2 numeros impares e 3 numeros pares.4!}</math>
''b) consiste de exatamente três números primos.
'''EXEMPLO (E7c) tenha a soma dos seus elementos, page 324)'''menor que 20.
Supunha que S = {1''d) tem,2pelo menos, um número par na mesma. . ., 25} . Encontre o numero de subconjuntos de tamanho 5,tal que T:''
a) consista de 2 numeros impares e [[Exemplo 4.3 numeros pares.7 - Solução]]
b) consiste de exatamente três números primos===Exemplos adicionais relativas a Seção 4.4==='''Exemplo 4.4.1 '''
c''Escreva a expansão de (x+2y) tenha a soma dos seus elementos, menor que 20³.(pág 328)''
d) tem, pelo menos, um número par na mesma[[Exemplo 4.4.1 - Solução]]
'''Exemplo 4.4.2 '''
'''Solução:'''Encontre o coeficiente <math>a) Há 13 numeros impares; podemos escolher dois em C^{17}b^{23}</math> na expansão de <math>(13,23a-7b) maneiras^{40}</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'''Exemplo 4. Então é melhor neste caso, contar diretamente o conjunto de cinco números cuja soma é inferior a 20:1,2,3,4,5, 1,2,3,4,6, 1,2,3,4,7,1,2,3,4,8, 1,2,3,4,9, 1,.3,4,5,6.Assim, existem seis desses subconjuntos possiveis.'''
d) É mais fácil para contar o número total de subconjuntos de tamanho 5, e depois subtrair o número ''Escreva a expansão de subconjuntos sem números pares neles:<math>C(25, 5)x^2-C(13,5\frac{1}{x} ) = 51,843^8</math>. (pág 328)''
===Exemplos adicionais relativas a Seção [[Exemplo 4.4==='''EXEMPLO (E1, página 328)'''Escreva a expansão de (x+2y)³.3 - Solução]]
===Exemplos adicionais relativas a Seção 4.5==='''Solução:Exemplo 4.5.1 '''pelo teorema binomial:<math>(x+2y)^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>
'''EXEMPLO (E2Uma padaria vende quatro tipos de biscoitos: chocolate, geleia, açúcar, page 328)'''Encontre o coeficiente <math>manteiga de amendoim. Você pode comprar um saco com 30 biscoitos. Assumindo que a^{17}b^{23}</math> na expansão padaria tem pelo menos 30 de cada tipo de <math>biscoito, quantos sacos contendo 30 biscoitos você poderia comprar se você deve escolher: (3a-7bpág 338)^{40}</math>.''
'''Solução:'''Expandindo <math>(3a-7ba)^{40}</math> usando o teorema binomial, localizamos o termo com o produto <math>a^{17}b^{23}</math>, Ao menos 3 biscoitos de chocolate e então encontramos o coeficiente:pelo menos 6 biscoitos de manteiga de amendoim
<math>(3a-7b''b)^{40} = (3a+(-7b))^{40}</math>Exatamente 3 biscoitos de chocolate e exatamente 6 biscoitos de manteiga de amendoim
= <math>\cdots + \binom{40}{17} (3a''c)^{17}(-7b)^{23} + \cdots</math>= <math>\cdots + \binom{40}{17} 3^{17}(-7)^23a^{17}b^{23} + \cdots</math>No máximo 5 biscoitos de açúcar
Assim, o coeficiente ''d) Pelo menos um dos quatro tipos 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>biscoitos.''
'''EXEMPLO (E3, page 328)'''Escreva a expansão de <math>(x^2[[Exemplo 4.5.1 -\frac{1}{x} )^8</math>Solução]]
'''Solução:'''
Usa-se o teorema binomial. Em seguida, várias regras exponenciais para simplificar os termos.
<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^{'''Exemplo 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 4.5==='''EXEMPLO Quantos anagramas podem ser formados pela palavra DECEIVED? (E1, page 338pág 339)'''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 de chocolate e pelo menos 6 biscoitos de manteiga de amendoim[[Exemplo 4.5.2 - Solução]]
b) Exatamente 3 biscoitos de chocolate e exatamente 6 biscoitos de manteiga de amendoim
c) No máximo '''Exemplo 4.5 biscoitos de açúcar.3'''
d) Pelo menos um dos quatro tipos ''Um frasco contém 30 moedas de 1 centavo, 20 moedas de 5 centavos, 20 moedas de 10 centavos, e 15 moedas de 25 centavos. (As moedas de biscoitoscada denominação são consideradas idênticas.) (pág 339)''
Solução:''(a) Encontre o número de maneiras de colocar todas as 85 moedas em uma fileira.
'''EXEMPLO (E2, page 339b)Encontre o número de possíveis ‘punhados’ de 12 moedas.'''Quantos anagramas podem ser formados pela palavra DECEIVED?
'''Solução: '''Na palavra há dois ‘D’, três ‘E’, um ‘C’, um ‘I’ e um ‘V’[[Exemplo 4. Portanto, o número de permutações de DECEIVED é: <math>\frac{8!}{2!5.3!.1!.1!.1!} = \frac{8!}{2!.3!}</math>- Solução]]
'''EXEMPLO (E3, page 339)'''
Um frasco contém 30 moedas de 1 centavo, 20 moedas de 5 centavos, 20 moedas de 10 centavos, e 15 moedas de 25 centavos. (As moedas de cada denominação são consideradas idênticas.)
(a) Encontre o número de maneiras de colocar todas as 85 moedas em uma fileira'''Exemplo 4.5.4'''
''De quantas maneiras é possivel colocar 7 das 8 letras de “CHEMISTS” em uma fila? (bpág 339) 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[[Exemplo 4. Pense no problema como um de fazer uma palavra com 30 p's, 20 n's, 20 d's, e 15 q's5. Tendo em conta as cartas idênticas, temos<math>\frac{85!}{30!.20!.20!.15!}</math>4 - Solução]]
(b) Quando se contar o número de ‘punhados’ de 12 moedas, estamos apenas preocupados com o número de cada denominação escolhida===Exemplos adicionais relativas a Seção 4. Por exemplo, poderíamos escolher 9 moedas de 1 centavos, 2 de 5 centavos, e uma de 25 centavos, ou podemos escolher três de cada denominação. Assim, 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 6=== 12</math>onde P é o número de moedas de '''Exemplo 4.6.1 centavo, n é o número de moedas de 5 centavos, d é o número de moedas de 10 centavos, e q é o número de 25 centavos. O número de soluções para esta equação é:<math>C(15,3) = 455</math>'''
'''EXEMPLO Coloque as seguintes permutações de 1, 2, 3, 4, 5, 6, na ordem lexicográfica : (E4, page 339pág 345)'''De quantas maneiras é possivel colocar 7 das 8 letras de “CHEMISTS” em uma fila?
'''Solução:'''<math>461325, 326145, 516243, 324165, 461235, 324615, 462135</math>
Existem dois padrões a serem considerados:[[Exemplo 4.6.1 - Solução]]
(a) 7 letras distintas são selecionados (ou seja, apenas um S é selecionado), e
(b) os dois S serem selecionados'''Exemplo 4.6.2'''
No primeiro teste padrão''Encontre a permutação de 1, 2, 3, existem 7! Maneiras de colocar as 7 letras distintas 4, 5, 6 imediatamente após 263.541 em uma fileiraordem lexicográfica.(pág 345)''
No segundo padrão, as sete letras selecionadas têm dois S’s, por isso há 7! / [[Exemplo 4.6.2! Maneiras de colocar essas letras em uma fileira. - Solução]]
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 '''Exemplo 4.6===.3 '''EXEMPLO (E1, página 345)'''Coloque as seguintes permutações de 1, 2, 3, 4, 5, 6, na ordem lexicográfica :
<math>461325''Encontre a permutação de 1, 3261452, 5162433, 3241654, 4612355, 324615, 462135</math>6 imediatamente antes de 261.345 em ordem lexicográfica. (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)]]