Changes

O pacote “combinat” ''combinat'' contém muitas funções pertinentes à contagem e geração de estruturas combinatórias. A lista de funções neste pacote é:

Existe outro pacote, “combstruct”''combstruct'', disponível no Maple V, versão 4, que também lida com estruturas combinatórias. A maior parte do que este pacote faz está além do escopo deste livro, mas algumas de suas funções expandem o que o pacote “combinat” ''combinat'' faz. O pacote “combstruct” ''combstruct'' fornece funções “interstructs”'''interstructs'''.

As estruturas relevantes que “combstruct” ''combstruct'' pode lidar são permutação, combinação/subconjunto, partição.

Para acessar os serviços fornecidos pelo pacote “combstruct”''combstruct'', digite:

Se você estiver usando a versão 3 do Maple, primeiramente você terá que utilizar o comando “with''with(share)”'', já que o pacote “combstruct” ''combstruct'' é parte da biblioteca na versão 3.

As funções no pacote “combinat” ''combinat'' para combinações são “numbcomb”''numbcomb'', “choose”''choose'', e “randcomb”''randcomb''. Este é o número de formas de escolher duas frutas a partir de uma maçã, uma laranja e uma pera.

A função “numbcomb” ''numbcomb'' conta o número de combinações (ou r-combinações) de um conjunto. A função “choose” ''choose'' lista as combinações. Portanto sempre existirão elementos “numbcomb” ''numbcomb'' listados por “choose”''choose''.

Esses números podem ser acessados diretamente no Maple usando a função “binomial” ''binomial'' da biblioteca Maple.

Dados argumentos numéricos, “binomial” ''binomial'' resulta em um número.

Entretanto, se é dado um argumento simbólico, “binomial” ''binomial'' retorna indeterminado.

Você pode expressar isso como uma função racional da variável “n” '''n''' chamando “expand”''expand''.

Para determinar a definição, nos termos de fatoriais, você pode usar o comando multifacetado “convert”''convert''.

O procedimento “convert” ''convert'' é uma utilidade de conversão de propósito geral que pode ser usado para transformar expressões de uma forma para outra, equivalente. Aqui, transforma uma instrução simbólica envolvendo a chamada do procedimento “binomial”''binomial'', para uma equivalente expressada usando fatoriais. Devido a “convert” ''convert'' aceitar uma grande variedade de tipos de argumentos, sua documentação é espalhada sobre muitas das páginas de ajuda online.Mas um bom lugar para começar a encontrar mais sobre “convert”''convert'', é a página principal de ajuda para este comando, acessada digitando “''?convert”convert''. Essa facilidade pode ser usada para provar identidades combinatórias envolvendo os coeficientes binomiais. Um pouco de cuidado é necessário, entretanto, para levar em conta o grau de avaliação que é realizado a cada passo, deixa coisas que são iguais não serem reconhecidas como tais. Por exemplo, essa identidade famosa <math>\binom{n}{k} = \binom{n}{n-k}</math> pode ser provada da seguinte forma.

isso ocorre porque esquerda e direita foram avaliadas de forma insuficiente até o momento. Para superar esta falta de reconhecimento, nós usamos “convert”''convert''.

Existe uma função “coeff” ''coeff'' que extrai o coeficiente de uma variável num polinomial.

#insira um polinomial “p” '''p''' e um termo multinomial ''term''.

##ordene '''p ''' em '''q'''##crie uma lista '''r ''' de termos multinomiais em '''q'''.##crie um multiset '''m ''' consistido de multinomiais em '''q ''' com multiplicidade igual ao coeficiente. (Note que isso não é um multiset verdade, como o coeficiente pode ser negativo ou não integral.)#procure a lista '''m ''' para uma entrada combinando '''term ''' e, se encontrada, retorne o coeficiente. Caso contrário, retorne 0.

Aqui, então, está o código Maple para “mcoeff”''mcoeff''.

Outro conjunto combinatório de números significante que surge como o conjunto de coeficientes de polinomiais especiais é o conjunto de números Stirling. O polinomial Stirling de grau “n” '''n''' é definido por:

Nós já mostramos como contar e gerar combinações usando Maple. Podemos agora introduzir recursos análogos do Maple para trabalhar com permutações. As funções Maple correspondentes para permutações são “numbperm”''numbperm'', “permute” ''permute'' e “randperm”''randperm''. Já que todas estão no pacotes “combinat”''combinat'', devem ser carregadas antes de serem usadas.

Usando o pacote “combstruct”''combstruct'', esses exemplos são feitos da seguinte forma:

A função “subsets” ''subsets'' permite gerar todos os subconjuntos de um conjunto dado. Já que os subconjuntos e combinações são apenas diferentes nomes para a mesma coisa, você pode usar essa função para gerar combinações. A função “subsets” ''subsets'' retorna uma tabela que contém duas entradas. Uma é chamada “nextvalue”''nextvalue'', e é um procedimento para gerar a próxima combinação, e a outra é “finished”''finished'', uma flag true/flase false que informa quando todas elas foram geradas.

Usando “combstruct”''combstruct'', uma faz a mesma coisa usando a função “iterstructs”''iterstructs''. O procedimento “iterstructs” ''iterstructs'' também retorna uma tabela, mas dessa vez usa as funções “next” ''next'' e “finished” ''finished'' para iterar.

Usando “iterstructs”''iterstructs'', podemos também iterar sobre permutações e tradições. Em adição, nós podemos especificar que tamanho de objeto nós queremos ver.

'''''numbperm([M,I,S,S,I,S,S,I,P,P,I]);'''''

'''''numbperm([O,R,O,N,O],0);'''''Usando o pacote “combstruct”''combstruct'', nós podemos achar a resposta em um passo.

O número de partições de um dado inteiro pode ser contado usando o procedimento “numbpart”''numbpart''.

As partições de um inteiro podem ser computadas usando a função “partition”''partition''.

a qual nós podemos ver como uma aproximação de um número real usando a função “evalf” ''evalf'' - avaliação como um número de ponto flutuante.

Para outro exemplo do uso do Maple no estudo da probabilidade discreta, permita-nos usar Maple para verificar a asserção no exemplo 144 na página 278 do texto. A afirmação é que o valor esperado do número de sucessos para “n” '''n''' tentativas Bernoulli, cada uma com a probabilidade “p” '''p''' de sucesso, é “np”'''np'''. Nós usaremos “EV” '''EV''' para denotar o valor esperado em Maple. (Nós não podemos usar “E” '''E''' porque aquele símbolo é reservado para a base do logaritmo natural.) Nós sabemos que

Alguma explicação é necessária. Primeiro, a combinação atual é uma lista, não um conjunto. Isso é porque a lista é ordenada, mas um conjunto é desordenado. Para encontrar a “next” '''next''' combinação, nós precisamos saber a ordem dos elementos na combinação atual. Mas no Maple, a ordem que digitamos um conjunto e a ordem que aparece dentro do Maple não são necessariamente a mesma coisa.

Com o pacote “combstruct”''combstruct'', você pode criar um iterador que vai produzir todos os objetos de um certo tamanho, um por vez.

=====1. Dado um inteiro positivo “n”''n'', encontre a probabilidade de selecionar seis inteiros do conjunto {<math>1, \cdots , n</math>} que foram mecânicamente mecanicamente selecionados em uma loteria. ====='''Solução''' Nós seguiremos o exemplo 4 no texto. O número total de maneiras de escolher 6 números de “n” '''n''' números é <math>C(n, 6)</math>, que pode ser encontrado com o procedimento “numbcomb” ''numbcomb'' no pacote “combinat”''combinat''. Isso nos dá o número total de possibilidades, onde apenas uma irá vencer.

 =====2. Dados inteiros positivos “n” ''n'' e “r”''r'', liste todas as r-combinações, com repetições permitidas, do conjunto .====='''Solução''' A função “choose” ''choose'' do Maple (no pacote “combinat”''combinat''), vai listar todas as r-combinações de, mas sem repetições. Portanto nós não podemos usá-la diretamente. Entretanto, digamos que queremos todas as 2-combinações de, com repetições. Isso quer dizer que junto com , e , nós também queremos incluir, e . Nós queremos ser capazes de escolher cada número até 2 vezes. (Nós dizemos que podemos repetir um elemento qualquer número de vezes, mas na prática, já que nós apenas podemos escolher 2 coisas no total, nós só precisamos permitir cada número aparecer no máximo 2 vezes.) Então outra forma de olhar o problema é dizer que queremos todas as 2-combinações, sem repetição, do conjunto. Em geral, então, nós podemos encontrar todas as r-combinações de com repetição pedindo por todas as r-combinações, onde cada elemento aparece “r” '''r''' vezes.

(Notas sobre o procedimento: O “i '''i $ r” r''' significa repetir “i” '''i r ''' vezes.

'''Solução''' Nossa solução vai usar o procedimento Maple chamado “permute” ''permute'' para computar o número total de maneiras que um torneio de jogos pode ser jogado. Vamos começar construindo duas listas que observa como cada um dos dois times pode ganhar. Nós iremos atribuir as duas do time 1 vencendo o torneio sem nenhuma derrota, e o time 2 vencendo o torneio sem nenhuma derrota. A cada iteração do loop principal do algoritmo, vamos computar as permutações possíveis de jogos a serem jogados, notando que a ordem de vitórias é importante para nós. Após essas permutações serem calculadas, nós vamos aumentar o número de jogos que o torneio dura (ou seja, permite o eventual time perdedor do torneio a vencer um jogo adicional). Isso é equivalente a usar um diagrama de árvore para computar os resultados possíveis. O loop externo (''while'') corresponde ao nível de vértices na árvore, e o loop interior (for) itera sobre todos os jogos naquele nível.

 =====4. Nós queremos olhar para os coeficientes binomiais <math>C(2n, n)</math>. Especificamente, para muitos exemplos, nós queremos determinar se <math>C(2n, n)</math> é divisível pelo quadrado de um primo, e se o maior expoente na fatorização do primo cresce sem limites enquanto “n” ''n'' cresce.===== '''Solução''' 

Nós usamos a função “ifactors” ''ifactors'' (o “i” '''i''' significa “integer”'''integer''') para fatorar “c”'''c'''. Essa função é uma das várias do Maple que deve ser definida “readlib” '''readlib''' antes que possamos usá-la. Isso significa que pedimos para o Maple encontrar a função na sua biblioteca, e carregá-la na sessão atual.

A página de ajuda para “ifactors” ''ifactors'' explica o que este resultado significa. Ela diz que <math>20 = 1.2^2.5^1</math>. Nós estamos interessados nos expoentes dos primos. Primeiro, pegamos o segundo elemento da lista, para obter a lista dos primos e expoentes.

Então nós usamos a função “max” ''max'' para encontrar o maior expoente.

Combinando esses passos, agora nós escrevemos um programa que dado “n”'''n''', retorna o maior expoente na fatorização de <math>C(2n, n)</math>.

Agora nós vamos escrever outra rotina que vai calcular o maior expoente para muitos valores de “n”'''n''', e armazenar os resultados numa tabela.

Parece que 1, 2 e 4 são valores de “n” '''n''' tais que <math>C(2n, n)</math> não é divisível pelo quadrado de um primo.

Para comparar, tente novamente com ainda mais valores de “n”'''n'''.

 '''Solução''' 

Uma simples aproximação é usar o procedimento do Maple “rand” ''rand'' para gerar uma lista de inteiros aleatórios. Então, tendo gerado tal lista nós podemos testar a coprimalidade de seus membros em pares usando o procedimento Maple “igcd” ''igcd'' em um segundo loop. Nós implementamos esses dois loops em um novo procedimento Maple chamado “RandPairs”''RandPairs'':

'''Solução''' 

Se considerarmos a probabilidade que nenhuma dupla de pessoas possuem o mesmo aniversário como “p”'''p''', nós podemos determinar a probabilidade de que apenas duas pessoas nasceram no mesmo dia do ano como <math>1-p</math>. Para determinar o que é “p”'''p''', observamos que se nós temos k pessoas, a primeira pessoa possui a probabilidade de 1 que ter o mesmo aniversário que ela mesma. A segunda pessoa tem 364 outros dias de 365 para escolher para que ela não faça aniversário no mesmo dia que a primeira pessoa. Similarmente para a pessoa <math>3, 4, \cdots , k</math>, onde a k-gésima pessoa tem <math>365-k</math> escolhas. Tomando o produto dessas probabilidades, concluímos que <math>p=P(365,k)/365^k</math>, que nos permite facilmente computar <math>1-p</math>.

==='''Exemplos extras da seção 4.1'''=======Exemplo 4.1.1===='''EXEMPLO (E1, pag 302)'''Há 3 voos disponiveis de Indianapolis para St.Louis e, independentemente de quais desses voos será escolhidos, há 5 voos disponiveis de St.Louis para Dallas.De quantas maneiras uma pessoa pode voar de Indianapolis para St.Louis para Dallas?(pág 302)''

[[Exemplo 4.1.1 - Solução: Uma vez que existe 3 maneiras para fazer a primeira parte da viajem e 5 maneiras de continuar com a segunda parte da viagem, independentemente de qual vôo for feita para a primeira etapa da viagem, pela regra do produto há 3 x 5 =15 maneiras de fazer toda a viagem.]]

====Exemplo 4.1.2===='''EXAMPLE (E2, pag 302)'''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?Solução: Precisa-se preencher os espaços em branco,mas cada espaço deve ser preenchido com inteiros diferentes de 1 a 5.Usando a regra do produto pode ser aplicado 5! = 5x4x3x2x1 = 120 maneiras. ''

[[Exemplo 4.1.2 - Solução]] ====Exemplo 4.1.3===='''EXAMPLE (E3, page 302)'''Conte os numeros de instruções de impressão nesse algoritmo:<nowiki>

fim </nowiki>''

Solução: Para cada valor de i,tanto o laço do 'j' como o do 'k' sao executados[[Exemplo 4. Assim a cada i, o número de declarações de impressão executado é 2Xn .Portanto o numero total de instruções de impressao executados é 2xn² 1.3 - Solução]]

====Exemplo 4.1.4===='''EXEMPLO (E4, page 302)'''Conte os numeros de instruções de impressão nesse algoritmo:<nowiki>

fim </nowiki>''

Solução: Para cada valor de i,tanto o laço do 'j' como o do 'k' sao executados[[Exemplo 4. Assim a cada laço do i, o número de declarações de impressão executado é i no primeiro laço mais n-i no segundo laço1. Portanto para cada i, o numero de impressoes é i + (n4 -i) = n.Solução]]

====Exemplo 4.1.5===='''EXEMPLO (E5, pag 306)'''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.''

Solução: para resolver o problema é ter em mente uma fila de dez espaços em branco :''(a) Cada um dos 10 espaços em branco da cadeia deve conter 1 das 21 consoantes,sem repeti-las.Pela regra do produto: 21 X 20 X 19 X 18 X ... X 12que não tenha vogais.''

''(b)Existem 5 possibilidades da primeira letra ser que começam com uma vogal.Se a vogal for colocada no primeiro espaço em branco existem 25 maneiras para preencher no segundo espaço,24 maneiras de preencher o terceiro espaço,etc . 5 x 25 x 24 x 23 x ... x 18 x 17.''

''(c)Primeiramente contamos o número de maneiras de preencher os 10 espaços começando com que tenha C e terminando com V,o numero de manerias de preencher as oito letras restantes é 24 x 23 x ... x 18 x 17; C _ _ _ _ _ _ _ _ V Da mesma forma,o número de palavras,porem agora,começando com V e terminado com C, 24 x 23 x ... x 18 x 17; V _ _ _ _ _ _ _ _ CLogo,pela regra da soma : nas extremidades (24 x 23 x ... x 18 x 17em qualquer ordem) + (24 x 23 x ... x 18 x 17) = = 2 x (24 x 23 x ... x 18 x 17)

''(d) Primeiramente vamos contar o número de maneiras de colocar as vogais nos dois primeiros espaços em branco.Podemos escolher qualquer uma das 5 vogais para a primeiro espaço e das 4 vogais restantes para o 2 espaço : 5 x 4=20 maneiras de colocar duas que tenha vogais nas duas primeiras posições. Em seguida, vamos preencher os 8 espaços restantes com 24 letras que faltam.Sendo feito da seguinte forma : 24 x 23 x ... x 18 x 17 maneiras.

Portanto, o número de maneiras de colocar vogais nois dois primeiros espaços e oito letras nos restantes dos espaços é: 5 x 25 x 24 x 23 x [[Exemplo 4.1.. x 18 x 175 - Solução]]

'''EXAMPLE (E6, page 306)'''10 homens e 10 mulheres estão em uma fila:(a) 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 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). Solução:a)Há 20 pessoas;Portanto eles podem ser colocados em uma fila: 20 x 19 x 18 x....x 1 = 20! b)se duas pessoas do mesmo sexo não podem ficar lado a lado;Entao há dois padroes possiveis, usando M para Masulino e F para Feminino: MFMFMFMFMFMFMFMFMFMF e FMFMFMFMFMFMFMFMFMFM.Se contar o numero de maneiras de se obter a primeira possibilidade, dobramos ela para chegarmos ao resultado final.O Primeiro homem pode ser escolhido em 10 maneiras, a Primeira mulher pode ser escolhida de 10 Maneiras, o homem Segundo pode ser escolhido de 9 maneiras, etc.Assim,pela regra do produto temos :10 x 10 x 9 x 9 x ... x 2 x 2 x 1 x 1 ou (10!)² maneiras.

''(c)Considerando primeiro os arranjos onde Beryl,Carol e Darryl ficam um ao lado do outro,nessa ordem.Colocando as outras 17 pessoas na fileira.o que Encontre quantas possibilidades pode ser feito em 17! Maneiras.Nao importa como as 17 pessoas sao colocadas na formada a fila,se Beryl,Carol , e Darrylquerem ficar juntas nesta sequencia (Carol,pode ser inseridoBeryl,nessa ordemand Darryl; ou Darryl,entre duas das 17Beryl, ou então colocado em uma das duas extremidadese Carol).

No entanto, uma vez que escolher um local para colocar Beryl, Carol, e Darryl, existem 3! = [[Exemplo 4.1.6 maneiras de colocar Beryl, Carol, e Darryl nesse ponto --- BCD, BDC, CBD, CDB, DBC, DCB. Portanto, a resposta é obtida colocando os outros 17 em uma fileira; escolher um dos 18 pontos para Beryl, Carol, e Darryl; e organizar os três em um local (em 3! maneiras). Assim, a resposta é: 17! x 3!Solução]]

====Exemplo 4.1.7===='''EXEMPLO (E7, página 308)'''Encontre o número de palavras 10 letras :(a) não contenha vogais.(b) começar com uma vogal.(c) ter vogais nas duas primeiras posições.(d) começar com C e terminam com V.(e) começar com C ou terminar com V.

para resolver o problema é ter em mente uma fila de dez espaços em branco :''(a) Cada um dos 10 espaços em branco da cadeia deve conter 1 das 21 consoantes,como podemos repeti-lasNão contenha vogais.Pela regra do produto: 21 X 21 X 21 X 21 X ... X 21 = 21^10 ;  ''(b)Há cinco opções para Começar com uma vogal ser colocada na primeira posição, e não há restrições sobre os outros nove letras,por isso : 5 x 26^9 . ''(c)Se essas Ter vogais devem estar nas duas primeiras posições e as letras podem ser repetidas, obtém-se o produto: 5² x 26^8 . ''(d)Se a palavra tem a forma : Começar com C....e terminam com V existem 26 maneiras para preencher cada uma dos oito espaços. Portanto, há 26^8 palavras desta forma. ''(e)Precisa-se usar o princípio da inclusão-exclusão para evitar a dupla contagem.Sendo A¹ o conjunto de todas as palavras Começar com 10 letras que começam C ou terminar com C e A² V. ''Para resolver o conjunto problema é ter em mente uma fila de todas as palavras com 10 letras que terminam com Vdez espaços em branco : A¹ U A² = |A¹|+|A²| - |A¹ n A²| = 26^9 + 26^9  [[Exemplo 4.1.7 - (26^8);Solução]]

Solução:Considere dois compartimentos, classificado em Par e Ímpar===== Exemplo 4. Se três inteiros positivos são colocados nestes compartimentos, um deles deve ter pelo menos dois inteiros (digamos A e B) no mesmo compartimento. Assim, A e B são ou ambos par ou impar. Em ambos os casos, A + B é PAR2.1 =====

'''EXEMPLO Provar que em qualquer grupo de três números inteiros positivos, existem pelo menos dois, cuja a soma é par. (E2, pág Pág. 314)'''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.

Solução:Para que A e B serem congruentes módulo 6, temos de ter a mod 6 = b mod 6[[Exemplo 4. Mas existem 6 possibilidades para x mod 6: 0, 1, 2, 3, 4, ou 5. Portanto, 7 inteiros positivos devem ser escolhidos de modo a garantir que, pelo menos, dois sejam congruentes módulo 6.1 - Solução]]

'''EXEMPLO (E3, página 314)'''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.Solução: O número de possíveis pares de letras que podem aparecer nas duas primeiras posições é 26 x 26=676==== Exemplo 4.Assim, qualquer conjunto de 677 ou mais palavras deve ter pelo menos duas palavras com o mesmo par de letras no início da palavra2.2 =====

(OBS:. Na realidade''Se forem escolhidos inteiros positivos aleatoriamente, qual é o número 700 pode ser substituída com um número muito menor, uma vez mínimo que muitas combinações de letras não aparecem como as duas primeiras letras de uma palavra, por exemplo, não há palavras inglesas podemos garantir que começam com NQ, RR, ou TZdois dos números escolhidos sejam congruentes módulo 6. (pág 314).''

'''EXEMPLO (E4, página 315)'''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===== Exemplo 4. Prove que, se 8000 peças são feitas, então, pelo menos, quatro delas devem ter o mesmo código carimbadas2.Solução: O numero de codigos possiveis 26 x 10 x 10 3 ===== 2600. Desde que,8000 > 3 x 2600,pelo menos 4 tenham o mesmo codigo.

'''EXEMPLO (E5, página 315)'''Cada aluno é classificado como um membro de uma das seguintes classes: Freshman, Sophomore, Junior, Senior[[Exemplo 4. Encontrar o número mínimo de estudantes que devem ser escolhidos de modo a garantir que, pelo menos, oito pertencem à mesma classe2.3 - Solução: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 é 292.4 =====

===Exemplos adicionais relativas a Seção 4.3==='''EXEMPLO 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.(E1, pág 321. 315)'''Uma classe tem 30 alunos matriculados. De quantas maneiras pode-se:(a) Colocar 4 alunos em uma fila para uma foto?(b) Colocar todos os 30 alunos em uma fila para uma foto?(c) Colocar todos os 30 alunos em duas filas de 15 cada para uma foto?

Solução:(a) Precisamos preencher a seguinte linha de quatro espaços em branco: 30 x 29 x 28 x 27[[Exemplo 4.2. Este é o número de permutações de 4 a partir de um conjunto de 30, que é P( 30 ,4 );- Solução]]

b)A resposta pode ser visualizado ===== 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 maneiras para preencher uma fila com 30 lacunas com os 30 estudantesque devem ser escolhidos de modo a garantir que, que é 30! pelo menos, ou Poito pertencem à mesma classe.( 30, 30 pág. 315);''

Podemos então, começar por preencher ===Exemplos adicionais relativos a linha de inferior, o que pode ser feito de 30 x 29 x 28 x … x 17 x 16 maneirasSeção 4. Em seguida, preencher linha superior, que pode ser feito de 15! 3== 15 x 14 x 13… x 2 x 1 maneiras. Portanto a resposta é (30 x 29 x 28 x … x 17 x 16) x (15 x 14 x 13 x … x 2 x 1) = 30!

'''EXEMPLO (E2, página 324)Exemplo 4.3.1'''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''Uma classe tem 30 alunos matriculados. De quantas maneiras pode-se:Há 5⁴=625 possíveis códigos com quatro dígitos. Portanto, há C(625,6pág 321) conjuntos diferentes de códigos reconhecíveis.EXEMPLO (E3, página 324)…..

'''EXAMPLE (E4, page 324a)'''Quantas maneiras existem de escolher Colocar 4 alunos em uma fila para uma comissão de cinco pessoas consistindo de três mulheres e dois homens de um grupo de dez mulheres e sete homensfoto?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).Usando a regra do produto para escolher três mulheres e dois homens é C( 10,3 ) x C(7,2) = 2,520.

'''EXEMPLO (E5, page 324c)Colocar todos os 30 alunos em duas filas de 15 cada para uma foto?'''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[[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)1 - Solução]]

Solução:a) Cada pilha deve conter 52/'''Exemplo 4 = 13 cartas. Na sequencia, empilharemos A,em seguida B, depois C, e finalmente D. Então teremos C(52,13) maneiras de obter a pilha de A, 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!.29!} 3.\frac{39!}{13!.26!} .\frac{26!}{13!.13!} .\frac{13!}{13!.0!} = \frac{52!}{3 (13!pág 324)^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!)^4.4!}</math>

'''EXEMPLO 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?(E7, page pág 324)'''

Supunha que S = {1,2, [[Exemplo 4. . ., 25} . Encontre o numero de subconjuntos de tamanho 5,tal que T:a) consista de 2 numeros impares e 3 numeros pares.b) consiste de exatamente três números primos.c) tenha a soma dos seus elementos, menor que 20.d) tem, pelo menos, um número par na mesma.4 - Solução]]

Solução:a) Há 13 numeros impares; podemos escolher dois em C(13''Sendo o conjunto S = {1,2) maneiras,3,...Há 12 numeros pares; podemos escolher 3 em C(12,3) maneiras19}. Usando a regra do produto para encontrar Encontre o número de subconjuntos T, temos subconjuntos.b) Os de S com numeros primos em S são 2,3,5,7,11,13,17,19, and 23, então temos C(9,3) maneiras iguais de selecionar 3 desses numerosinteiros pares e impares.Mas também precisa selecionar 2 dos 16 números compostos para fazer T ter tamanho cinco;então C(16,2) maneiras para isso.Portanto pela regra do produto temos C(9,3pág 324) x C(16,2)=10.080 subconjuntos possiveis T.''

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.- Solução]]

d'''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; ''b) É mais fácil para contar Em 4 pilhas iguais, sem classificação;'' [[Exemplo 4.3.6 - Solução]] '''Exemplo 4.3.7 ''' ''Suponha que S = {1,2, . . ., 25} . Encontre o número total numero de subconjuntos de tamanho 5, tal que T:(pág 324)'' ''a) consista de 2 numeros impares e depois subtrair o número 3 numeros pares. ''b) consiste de subconjuntos sem exatamente três números pares neles:primos. <math>C(25''c) tenha a soma dos seus elementos, 5menor que 20. ''d)-C(13tem,5) = 51pelo menos,843</math>um número par na mesma.'' [[Exemplo 4.3.7 - Solução]]

'''EXEMPLO (E1, página 328)Exemplo 4.4.1 '''Escreva a expansão de (x+2y)³.

Solução:pelo teorema binomial:<math>''Escreva a expansão de (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³. (2ypág 328)^3 = x^3+6x^2y+12xy^2+8y^3</math>''

'''EXEMPLO (E2, page 328)'''Encontre o coeficiente <math>a^{17}b^{23}</math> na expansão de <math>(3a[[Exemplo 4.4.1 -7b)^{40}</math>.Solução]]

''Encontre o coeficiente <math>(3a-7b)a^{17}b^{4023} = </math> na expansão de <math>(3a+(-7b))^{40}</math>. (pág 328)''

= <math>\cdots + \binom{40}{17} (3a)^{17}([[Exemplo 4.4.2 -7b)^{23} + \cdots</math>= <math>\cdots + \binom{40}{17} 3^{17}(-7)^23a^{17}b^{23} + \cdots</math>Solução]]

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} '''Exemplo 4.4.3^{17}(-7)^{23}</math>.'''

'''EXEMPLO (E3, page 328)'''Escreva a expansão de <math>(x^2-\frac{1}{x} )^8</math>. (pág 328)''Solução:Usa-se o teorema binomial[[Exemplo 4. Em seguida, várias regras exponenciais para simplificar os termos4.3 - Solução]]

'''EXEMPLO (E1, page 338)Exemplo 4.5.1 ''' ''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:(pág 338)'' ''a) Ao menos 3 biscoitos de chocolate e pelo menos 6 biscoitos de manteiga de amendoim ''b) Exatamente 3 biscoitos de chocolate e exatamente 6 biscoitos de manteiga de amendoim ''c) No máximo 5 biscoitos de açúcar ''d) Pelo menos um dos quatro tipos de biscoitos.'' [[Exemplo 4.5.1 - Solução]]  '''Exemplo 4.5.2 ''' ''Quantos anagramas podem ser formados pela palavra DECEIVED? (pág 339)''

[[Exemplo 4.5.2 - Solução:]]

'''EXEMPLO (E3, page 339)Exemplo 4.5.3'''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.(b) Encontre o número de possíveis ‘punhados’ de 12 moedas.

Solução: A resposta não é 85! uma vez que as ''Um frasco contém 30 moedas não são todos distintos. Pense no problema como um de fazer uma palavra com 30 p's1 centavo, 20 n'smoedas de 5 centavos, 20 d'smoedas de 10 centavos, e 15 q'smoedas de 25 centavos. Tendo em conta as cartas (As moedas de cada denominação são consideradas idênticas, temos<math>\frac{85!}{30!.20!.20!.15!}</math>) (pág 339)''

''(ba) Quando se contar Encontre o número de ‘punhados’ de 12 moedas, estamos apenas preocupados com o número maneiras de cada denominação escolhida. Por exemplo, poderíamos escolher 9 colocar todas as 85 moedas de 1 centavos, 2 de 5 centavos, e em uma de 25 centavos, ou podemos escolher três de cada denominaçãofileira. 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 = 12</math>onde P é o número de moedas de 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 (E4, page 339b)Encontre o número de possíveis ‘punhados’ de 12 moedas.'''De quantas maneiras é possivel colocar 7 das 8 letras de “CHEMISTS” em uma fila?Solução:Existem dois padrões a serem considerados:

No primeiro teste padrão, existem 7! Maneiras de colocar as 7 letras distintas em uma fileira'''Exemplo 4.5.4'''

No segundo padrão, as sete ''De quantas maneiras é possivel colocar 7 das 8 letras selecionadas têm dois S’s, por isso há 7! / 2! Maneiras de colocar essas letras “CHEMISTS” em uma fileira. fila? (pág 339)''

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[[Exemplo 4.\frac{7!}{2!}</math>5.4 - Solução]]

'''EXEMPLO (E1, página 345)Exemplo 4.6.1''' ''Coloque as seguintes permutações de 1, 2, 3, 4, 5, 6, na ordem lexicográfica :(pág 345)'' 

[[Exemplo 4.6.1 - Solução]]  '''EXEMPLO (E2, página 345)Exemplo 4.6.2''' ''Encontre a permutação de 1, 2, 3, 4, 5, 6 imediatamente após 263.541 em ordem lexicográfica.(pág 345)'' [[Exemplo 4.6.2 - Solução:]]  '''Exemplo 4.6.3 ''' Os dígitos 5''Encontre a permutação de 1, 2, 3, 4, 1 estão 5, 6 imediatamente antes de 261.345 em ordem decrescentelexicográfica. (pág 345)'' [[Exemplo 4.6.3 - Solução]]   '''Exemplo 4.6.4 ''' ''Se as permutações de 1, por isso precisamos aumentar o dígito seguinte2, 3. Substitui-lo por ,4 e, em seguida5, colocar os dígitos restantes 6 forem colocadas em ordem crescentelexicográfica, com 123.456 na posição 1, temos 264123.1355465 na posição 2, etc., encontrar a permutação na posição 362. (pág 345)''

'''EXEMPLO (E3, página 345)'''Encontre a permutação de 1, 2, 3, [[Exemplo 4, 5, .6 imediatamente antes de 261.345 em ordem lexicográfica.4 - Solução:Uma vez que os quatro últimos dígitos, 1345, estão em ordem crescente, a permutação que vem imediatamente antes deste deve ter um “5” na segunda posição e os quatro dígitos após o “5”, em ordem decrescente. Assim, o antecessor de 261.345 é 256.431.]]

Solução:Existem 6! = 720 permutações de 1, 2, 3, '''Exemplo 4, 5, .6. O primeiro 120 (isto é, as permutações em posições de 1 a 120) começa com um “1”, o segundo 120 (nas posições 121 a 240) começar com “2”, etc. Assim, a primeira permutação começando com “4”, 412,356, é na posição 361. Assim , a próxima permutação, 412.365, vai estar na posição 362.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)''

Solução:Existem 4! = 24 permutações de 1, 2, 3, [[Exemplo 4, 5 que começam com 1; estas permutações estão em posições de 1 a 24. Da mesma forma, as permutações em posições 25 a 48 começam com 2 e as permutações em posições 49 através de 72 começam com 3 . Assim, a primeira permutação começando com 4, 41235, está na posição 73. Por conseguinte 41253 está na posição 746.5 - Solução]]