View source for Contagem

A contagem é fundamental para o estudo da matemática discreta, a complexidade de algoritmos, combinatórios, e alguns ramos da álgebra tais como a teoria do grupo finito. Este capítulo apresenta uma variedade de técnicas que estão disponíveis no Maple para contar uma coleção diversa de objetos discretos, incluindo combinações e permutações de conjuntos finitos. Objetos podem ser contados usando fórmulas ou outros algoritmos, ou listando-os e observando diretamente o tamanho da lista. A última abordagem por um número de procedimentos Maple que pode ser usado para gerar estruturas combinatórias.

A maioria dos procedimentos Maple relevantes a este capítulo pertence em um ou dois pacotes. O pacote “combinat” é a parte padrão da versão da biblioteca 3Maple.

Um novo pacote “combstruct” está disponível como uma biblioteca compartilhada para MapleV, versão 3, e é um pacote padrão da versão 4. Você pode acessar os serviços oferecidos por qualquer um desses pacotes usando o comando “with” para carregá-lo na sua sessão Maple. (Se você está usando Maple V, versão 3, você também deve colocar with(share) antes de digitar with(combstruct)).

É útil saber que o pacote combstruct, enquanto provê uma grande variedade de procedimentos, organiza algumas das funções básicas em grupos relacionados a um objeto combinatório particular (como, por exemplo, combinações ou partições). Para muitos tipos de objetos combinatórios, existem procedimentos Maple para fazer as seguintes operações.
# Você pode construir todos os objetos daquele tipo associado a um inteiro dado. Ao procedimento para fazer isso é geralmente dado um nome refletindo o tipo de objeto. (Por exemplo, “permute” and “partitions”.)
# Você pode contar todos os objetos daquele tipo associado a um inteiro dado. Aqueles procedimentos geralmente começão com a string “numb” e são completados por uma abreviaçãodo tipo de objeto sendo contado. (Por exemplo, “numbperm” e “numbpart”.)
# Você pode gerar um objeto aleatório daquele tipo associado a um inteiro dado. Uma abreviação do tipo de objeto sendo gerado, prefixado com a string “rand” é como essas rotinas são normalmente nomeadas. (Por exemplo, “randperm” e “randpart”.)



Claro, também existem muitas outras funções que não se encaixam neste esquema.

==='''1. Funções Maple relevantes'''===

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

 '''''with(combinat);'''''

Existe outro pacote, ''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'' faz. O pacote ''combstruct'' fornece funções '''interstructs'''.

'''count'''         Para contar o número de objetos de um dado tamanho<br />
'''draw'''          Para gerar um objeto aleatório de um dado tamanho<br />
'''allstructs'''    Para gerar todos os objetos de um dado tamanho<br />
'''iterstructs'''   Para gerar a “próxima” estrutura de um dado tamanho<br />

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

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

 '''''with(combstruct);'''''

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

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

 '''''numbcomb([apple, orange, pear], 2);'''''

Aqui estão as possíveis escolhas:

 '''''choose([apple, orange, pear], 2);'''''

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

 '''''nops(%);'''''

E se tivermos duas maçãs e nenhuma pêra (um exemplo com elementos indistinguíveis):

 '''''numbcomb([apple, apple, orange],2);'''''

Com as escolhas:

 '''''choose([apple, apple, orange],2);'''''

Se nós não fornecemos o segundo argumento, todas as combinações possíveis de todos os tamanhos possíveis são consideradas.

 '''''numbcomb([apple, apple, orange]);<br />'''''
 '''''choose([apple, apple, orange]);'''''

Nós também podemos escolher combinações aleatórias.

 '''''randcomb([chocolate, vanilla, cookiedough],2);'''''<br />
 '''''randcomb(5,3);'''''

Neste exemplo, o '''5''' representa o conjunto '''''<math>{1, 2, 3, 4, 5}</math>'''''.

Usando ''combstruct'', nós resolveríamos os problemas acima da seguinte forma:

 '''''count(Combination([apple,orange,pear]),size=2);'''''<br />
 '''''allstructs(Combination([apple,orange,pear]), size=2);'''''<br />
 '''''draw(Combination([chocolate,vanilla,cookiedough]),size=2);'''''

Coeficientes binomiais podem ser calculados tanto chamando a função ''numbcomb'' como um inteiro como primeiro argumento,

 '''''numbcomb(10,5);'''''

ou nós podemos calcular '''''<math>C(n, r)</math>''''', usando a função ''binomial''. Então nós resolvemos o exemplo 7 na seção 4.3 da seguinte forma:

 '''''binomial(10,5);'''''

Quando '''n''' e '''r''' são inteiros não negativos e '''''<math>r \leq n</math>''''', ''binomial'' e ''numbcomb'' se comportam de forma idêntica. O procedimento ''binomial'' é mais geral, e expande a definição dos coeficientes binomiais. Não vamos discutir seu uso mais geral aqui.

==='''2. Mais funções combinatórias'''===

Nesta seção, vamos discutir algumas funções combinatórias, úteis na contagem, que surgem como coeficientes de certos polinomiais.

===='''2.1. Coeficientes binomiais'''====

Os coeficientes binomiais que são coeficientes do polinomial <math>(a+b)^n</math> quando este é expandido.

 '''''for n from 1 to 7 do'''''<br />
 '''''        sort(expand((a + b)^n));'''''<br />
 '''''od;''''''

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

 '''''for n from 1 to 7 do'''''<br />
 '''''        seq(binomial(n, k), k = 0..n);'''''<br />
 '''''od;'''''

O valor do binomial(n, k) é o coeficiente do termo binomial <math>a^kb^{n-k}</math> (que é igual ao coeficiente de <math>a^{n-k}b^k</math>) na expansão de <math>(a+b)^n</math>.
Dados argumentos numéricos, ''binomial'' resulta em um número.
	
 '''''binomial(100,53);'''''

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

 '''''n := 'n': # clear values'''''<br />
 '''''k := 'k': # from n and k'''''<br />
 '''''binomial(n, 9);'''''

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

 '''''expand(%);'''''

Entretanto, isso funciona apenas se no máximo um dos argumentos for simbólico.

 '''''binomial(n, k);'''''<br />
 '''''expand(%);'''''

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

 '''''convert(binomial(n, k), factorial);'''''

O procedimento ''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'', para uma equivalente expressada usando fatoriais. Devido a ''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'', é a página principal de ajuda para este comando, acessada digitando ''?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.

 '''''left := binomial(n, k);'''''<br />
 '''''right := binomial(n, n - k);'''''

Queremos provar a esquerda e a direita são iguais. Note que

 '''''evalb(left = right);'''''

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

 '''''left := convert(left, factorial);'''''<br />
 '''''right := convert(right, factorial);'''''<br />
 '''''evalb(left = right);'''''

Geralmente existe uma certa quantidade de adivinhação envolvida em coagir expressões simbólicas para a forma que é útil para um dado problema. Maple é designado para permitir que você facilmente experimente com expressões, para que você possa descobrir a forma certa para uma aplicação particular.

===='''2.2. Coeficientes multinomiais'''====

Para computar o números de permutações de um conjunto finito em que alguns membros são indistinguíveis do outros (tal conjunto é geralmente chamado um '''multiset'''), Maple fornece o procedimento ''multinomial'' no pacote ''combinat''. Ele calcula os coeficientes multinomiais, isto é, números da forma <math>\frac{n!}{n_1!n_2!n_3!\cdots n_k!}</math> em cada <math>n_1, n_2, n_3, \cdots n_k</math> existem inteiros não negativos cuja soma é '''n'''. O primeiro argumento para ''multinomial'' é o inteiro '''n''', enquanto os argumentos restantes são os números <math>n_1, n_2, \cdots n_k</math> do denominador.

Por exemplo, permita-nos computar o número de strings distintas obtidas pela permutação das letras da palavra “MISSISSIPPI” (um exemplo clássico). Aqui existe 1M, e existem 4 Is, 4 Ss, e 2 Ps. Isso dá um total de 11 caracteres. Portanto, o número de strings distintas é

 '''''combinat[multinomial](11, 1, 4, 4, 2);'''''

Observe que o primeiro argumento deve ser a soma dos argumentos restantes; caso contrário um erro é indicado.

 '''''combinat[multinomial](11, 1, 4, 4, 3);'''''

O coeficiente multinomial exibido acima é chamado coeficiente porque ele é o coeficiente do multinomial <math>x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}</math> na expansão do polinomial <math>(x_1+x_2+\cdots +x_k)^n</math>. Nós podemos ver alguns exemplos disso usando Maple. (Usaremos as variáveis a, b, c, e assim por diante, já que são mais fáceis de se ler que x1, x2, x3, etc.)

 '''''p := (a + b + c)^5;'''''<br />
 '''''p := expand(p);'''''

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

 '''''coeff(x^3 - 5*x^2 + 2, x^2);'''''<br />
 '''''coeff(x^3 - 5*x^2 + 2, x);'''''

Entretanto, isso apenas funciona com polinomiais invariáveis. Você pode, todavia, acessar os multinomiais individuais em um polinomial multivariado, usando o comando “op”.

 '''''op(3, p);'''''<br />
 '''''op(p);'''''

Isso, infelizmente, depende da ordenação dos multinomiais no polinomial '''p''' fazendo isso impossível de prever qual dentro dos multinomiais em '''p''' será extraída. Para contornar este problema, use o comando ''sort'' primeiro.
 
 '''''p := sort(p);'''''<br />
 '''''op(3, p);'''''<br />
 '''''terms := [op(p)];'''''

Os multinomiais são ordenados lexicograficamente . Para reparar a deficiência em ''coeff'' que o impede de manusear polinomiais multivariados, nós podemos escrever nossa própria rotina, ''mcoeff'' que faz esse trabalho para nós. Já que ''coeff'' é implementada no kernel Maple, não é possível para um usuário redefinir seu comportamento, então é necessária uma rotina separada. Para simplicidade, nosso procedimento ''mcoeff'' vai apenas lidar com polinomiais com coeficientes numéricos. O algoritmo usado aqui é o seguinte:

#insira um polinomial '''p''' e um termo multinomial ''term''.
#processe '''p''' da seguinte:
##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 := proc(p::polynom, term::polynom)'''''
   '''''local m, # list of multinomials'''''
         '''''t, # index into m'''''
         '''''x, # dummy variable'''''
         '''''q, # sorted input'''''
         '''''r; # multiset of multinomials and coefficients'''''
   '''''q := sort(p); r := [op(q)];'''''
   '''''m := map(x -> [coeffs(x), x / coeffs(x)], r);'''''
   '''''for t in m do'''''
     '''''if term = op(2, t) then RETURN(op(1, t)); fi;'''''
   '''''od;'''''
   '''''RETURN(0);'''''
 '''''end:'''''

Por exemplo, para alocar o coeficiente de no polinomial multivariado , podemos usar ''mcoeff'' da seguinte maneira:

 '''''p := (a + b + c)^5;'''''<br />
 '''''p := expand(p);'''''<br />
 '''''mcoeff(p, a^2 * b^3);'''''

Solicitar o coeficiente de um multinomial que não esteja no polinomial resulta em zero.

 '''''mcoeff(p, x^5);'''''

Se a entrada polinomial '''p''' é um polinomial em uma única variável, então a chamada ''mcoeff(p, x^n)'' é equivalente à chama ''coeff(p, x^n)'' ou ''coeff(p, x, n)''. (A sintaxe da chamada no último estilo não é suportada por ''mcoeff''.)

 '''''mcoeff(x^3 - 2*x^2 + 1, x^2);'''''<br />
 '''''coeff(x^3 - 2*x^2 + 1, x^2);'''''<br />
 '''''coeff(x^3 - 2*x^2 + 1, x, 2);'''''

A rotina ''mcoeff'' fornece outros meios em que nós podemos determinar coeficientes multinomiais. Por exemplo:

 '''''with(combinat):'''''<br />
 '''''multinomial(6, 1, 2, 3);'''''<br />
 '''''p := expand((a + b + c)^6);'''''<br />
 '''''mcoeff(p, a * b^2 * c^3);'''''

===='''2.3. Números Stirling====

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''' é definido por:

<math>S_n(x) = x.(x-1).(x-2).\cdots .(x-n+1)</math>

Quando expandido, <math>S_n(x)</math> tem a forma:

<math>S_n(x) = s(n, 1)x+s(n, 2)x^2+s(n, 3)x^3+\cdots +s(n, n)x^n</math>

Os coeficientes <math>S(n, k)</math>, para <math>1\leq k \leq n</math>, são chamados de números Stirling (do primeiro tipo).

Podemos usar Maple para gerar os polinomiais Stirling da seguinte forma.

 '''''n := 'n'; i := 'i';'''''
 '''''S(n) := product(x - i, i = 0..n-1);'''''

Essa expressão Maple insiste em exibir com o uso da função Gamma <math>\Gamma</math>.

A função Gamma é uma extensão contínua da função fatorial para números reais. Para um inteiro não negativo '''n''', nós temos <math>\Gamma (n+1) = n!</math>. Mas, para valores específicos de '''n''', podemos coagir Maple a representar os polinomiais de Stirling como polinomiais, usando ''simplify''.
 '''''subs(n = 9, S(n));'''''<br />
 '''''simplify(%);'''''<br />
 '''''expand(%);'''''<br />
 '''''sort(%);'''''<br />
 '''''coeffs(%);'''''<br />
 '''''[%];'''''
Portanto, nós temos uma lista de números Stirling <math>S(9, k)</math>, para <math>k = 1, 2, \cdots , 9</math>.
Você pode acessar os números de Stirling diretamente no Maple, usando a função ''stirling1'' no pacote ''combinat''.
 '''''with(combinat):'''''
 '''''for n from 1 to 7 do'''''
 '''''  seq(stirling1(n,i), i = 1..n);'''''
 '''''od;'''''

Existem alguns padrões interessantes no triângulo resultante. Tente computar mais números de Stirling e veja se você pode fazer quaisquer conjecturas sobre os padrões que você vê.

==='''3. Permutações'''===

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'', ''permute'' e ''randperm''. Já que todas estão no pacotes ''combinat'', devem ser carregadas antes de serem usadas.
 '''''with(combinat):'''''
 '''''numbperm([S,U,C,C,E,S,S]);'''''
 '''''permute([a,b,c]);'''''
 '''''randperm([S,U,C,C,E,S,S]);'''''
 '''''randperm(5);'''''
Usando o pacote ''combstruct'', esses exemplos são feitos da seguinte forma:
 '''''with(combstruct):'''''
 '''''count(Permutation([S,U,C,C,E,S,S]));'''''
 '''''allstructs(Permutation([a,b,c]));'''''
 '''''draw(Permutation(5));'''''

A função ''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'' retorna uma tabela que contém duas entradas. Uma é chamada ''nextvalue'', e é um procedimento para gerar a próxima combinação, e a outra é ''finished'', uma flag true/false que informa quando todas elas foram geradas.
 '''''S := combinat[subsets](a,b):'''''
 '''''while not S[finished] do'''''
 '''''  S[nextvalue]();'''''
 '''''od;'''''

Usando ''combstruct'', uma faz a mesma coisa usando a função ''iterstructs''. O procedimento ''iterstructs'' também retorna uma tabela, mas dessa vez usa as funções ''next'' e ''finished'' para iterar.
 '''''S := iterstructs(Subset(a,b)):'''''
 '''''while not finished(S) do'''''
 '''''  nextstruct(S);'''''
 '''''od;'''''
Usando ''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.
 '''''P := iterstructs(Permutation([a,b,b]), size=2):'''''
 '''''while not finished(P) do'''''
 '''''  nextstruct(P);'''''
 '''''od;'''''

Pelo fatos das função de permutação Maple poderem resolver problemas de permutação com elementos indistinguíveis tão facilmente quanto sem elementos indistinguíveis, alguns dos exercícios do texto se tornam triviais. Por exemplo, exercício 266 pergunta quantas strings diferentes podem ser formadas com as letras em MISSISSIPPI usando todas as letras.
A solução pode ser encontrada em um passo:
 '''''numbperm([M,I,S,S,I,S,S,I,P,P,I]);'''''
A questão 299 é similar, mas envolve alguns passos extras. Ela pergunta quantas strings diferentes podem ser feitas a partir das letras em ORONO, usando uma ou todas as letras. Para achar a solução, primeiramente calculamos o número de 1-permutações, depois com 2-permutações, etc.
 '''''total := 0:'''''
 '''''for i from 1 to 5 do'''''
 '''''     total := total + numbperm([O,R,O,N,O],i);'''''
 '''''od:'''''
 '''''total;'''''
Existem 633 strings possíveis usando uma ou todas as letras em ORONO. 644 se nós contarmos as string com 0 letras.
 '''''numbperm([O,R,O,N,O],0);'''''
Usando o pacote ''combstruct'', nós podemos achar a resposta em um passo.
 '''''with(combstruct):'''''
 '''''count(Permutation([O,R,O,N,O]), size='allsizes');'''''
Entretanto, a maior parte dessa sessão envolve pensar e entender a questão. Maple pode ajudar a calcular os números de permutações e combinações, mas cabe a você decidir que valores você precisa calcular para encontrar a resposta.

===='''3.1. Partições de Inteiros'''====
Também existem funções para fazer partições de inteiros. (Uma partição de inteiro é um modo de escrever um inteiro '''n''' como a soma de inteiros positivos, onde ordem não importa. Então <math>5=1+1+3</math> é uma partição de inteiro do 5.) Junto ao ''numbpart'', ''partition'' e ''randpart'', existem funções para gerar partições, uma por vez, baseada em uma dada ordem canônica. Todas estas funções são parte do pacote ''combinat'' que deve, consequentemente, ser carregado antes de você acessá-las.
 '''''with(combinat):'''''
O número de partições de um dado inteiro pode ser contado usando o procedimento ''numbpart''.
 '''''seq(numbpart(i), i = 1..20);'''''
As partições de um inteiro podem ser computadas usando a função ''partition''.
 '''''partition(5);'''''
Isso constrói as partições de seu argumento como uma lista de listas, cada sublista representando uma partição.

Como seu nome sugere, ''randpart'' simplesmente cria uma partição aleatória de um inteiro.
randpart(20);
Maple provê funções especiais para gerar a sequencia de todas as partições de um inteiro dado. Portanto, nós temos as rotinas ''firstpart'', ''nextpart'', ''prevpart'' e ''lastpart''.
 '''''firstpart(4);'''''
 '''''nextpart(%);'''''
 '''''nextpart(%);'''''
 '''''prevpart(%);'''''
 '''''nextpart(%%);'''''
 '''''lastpart(4);'''''

==='''4. Probabilidade discreta'''===

Para encontrar a probabilidade de um evento numa amostra de espaço finita, calcula-se o número de vezes que o evento ocorre, e divide-se pelo número total de resultados possíveis (o tamanho do espaço de amostra).

Como no exemplo 4, seção 4.4, nós calculamos a probabilidade de ganhar na loteria, onde precisamos escolher 6 números corretamente de 40 números possíveis. O número total de maneiras de escolher 6 números é:
 '''''numbcomb(40,6);'''''
e existe uma combinação vencedora. Portanto a probabilidade é
 '''''1/%;'''''
a qual nós podemos ver como uma aproximação de um número real usando a função ''evalf'' - avaliação como um número de ponto flutuante.
 '''''evalf(%);'''''

Nós também podemos forçar uma aproximação decimal do resultado usando 1.0, ou simplesmente 1., para mostrar que nós desejamos trabalhar com decimais em vez da representação racional exata. Por exemplo, se precisarmos escolher de 50 números, a probabilidade é:
 '''''1./numbcomb(50,6);'''''
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''' tentativas Bernoulli, cada uma com a probabilidade '''p''' de sucesso, é '''np'''. Nós usaremos '''EV''' para denotar o valor esperado em Maple. (Nós não podemos usar '''E''' porque aquele símbolo é reservado para a base do logaritmo natural.) Nós sabemos que
 '''''p(X=k) := binomial(n, k) * p^k * (1 - p)^(n - k);'''''
A partir da definição, nós temos
 '''''EV(X) := sum(k * p(X=k), k = 1..n);'''''
 '''''simplify(%);'''''

==='''5. Gerando combinações e permutações'''===

Aqui está uma implementação do algoritmo para gerar a próxima r-combinação (exemplo 5).
 '''''NextrCombination := proc(current, n, r)'''''
 '''''local next, i, j;'''''
faça uma cópia que possamos mudar
 '''''next := table(current);'''''
   '''''i := r;'''''
   '''''while next[i] = n - r + i do i := i -1 od;'''''
   '''''next[i] := next[i] + 1;'''''
   '''''for j from i+1 to r do'''''
     '''''next[j] := next[i] + j - i;'''''
   '''''od;'''''
   '''''[seq( next[i], i=1..r) ];  # return the answer'''''
 '''''end:'''''
Teste-a no exemplo.
 '''''NextrCombination([1,2,5,6], 6, 4);'''''
 '''''NextrCombination(%,6,4);'''''
 '''''NextrCombination(%,6,4);'''''
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''' 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.
 '''''pear, orange, apple;'''''
Mas ela sempre a mesma para uma lista.
 '''''[pear,orange,apple];'''''
O próximo problema é que você não pode, antes da versão 4 do Maple V, atribuir um elemento específico dentro de uma lista.
 '''''mylist := [a,b,c,d]:'''''
 '''''mylist[2] := e;'''''
Então, a primeira coisa que fazemos nesse algoritmo é fazer uma tabela que contém todos os elementos na combinação. Nós podemos atribuir na tabela, então nosso problema acaba.
 '''''mytable := table(mylist);'''''
 '''''mytable[2] := e;'''''
 '''''print(mytable);'''''
Com o pacote ''combstruct'', você pode criar um iterador que vai produzir todos os objetos de um certo tamanho, um por vez.
 '''''it := iterstructs(Combination(6),size=4):'''''
 '''''nextstruct(it);'''''
 '''''nextstruct(it);'''''
 '''''nextstruct(it);'''''
Chamando essa função algumas vezes mais, nos leva a:
 '''''nextstruct(it);'''''
onde a próxima 4-combinação é então:
 '''''nextstruct(it);'''''
pela qual nós podemos ver que esse iterador está usando a mesma lexicografia ordenando como usamos no algoritmo 3.

==='''6. Computações e explorações'''===

=====1. Dado um inteiro positivo ''n'', encontre a probabilidade de selecionar seis inteiros do conjunto {<math>1, \cdots , n</math>} que foram 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úmeros é <math>C(n, 6)</math>, que pode ser encontrado com o procedimento ''numbcomb'' no pacote ''combinat''. Isso nos dá o número total de possibilidades, onde apenas uma irá vencer.
 '''''Lottery := proc(n::posint) '''''
 '''''local total; '''''
 '''''   total := combinat[numbcomb](n, 6); '''''
 '''''   1.0 / total; '''''
 '''''end: '''''
 '''''Lottery(49); '''''
Se as regras da loteria mudarem, para que o número de números escolhidos seja algo diferente de 6, então nós devemos modificar o procedimento acima. (Por exemplo, talvez agora possamos escolher 5 números de 499, em vez de 6.) Nós podemos facilmente modificar nosso programa para nos deixar especificar quantos números nós queremos escolher adicionando outro parâmetro.
 '''''Lottery2 := proc(n::posint, k::posint) '''''
 '''''local total; '''''
 '''''     total := combinat[numbcomb](n,k); '''''
 '''''     1.0 / total;  '''''
 '''''end: '''''
 '''''Lottery2(49,6); '''''
 '''''Lottery(30,3); '''''

=====2. Dados inteiros positivos ''n'' e ''r'', liste todas as r-combinações, com repetições permitidas, do conjunto .=====
'''Solução'''

A função ''choose'' do Maple (no pacote ''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''' vezes.
 '''''RCombRepetition := proc(n::posint, r::posint) '''''
 '''''local repeatlist, i; '''''
 '''''    repeatlist := [ seq( i $ r, i=1..n) ]; '''''
 '''''    combinat[choose](repeatlist, r); '''''
 '''''end: '''''
 '''''RCombRepetition(3,2); '''''
 '''''RCombRepetition(4,3); '''''
(Notas sobre o procedimento: O '''i $ r''' significa repetir '''i r''' vezes.
 '''''1 $ 3; '''''
 '''''happy $ 4; '''''
Além disso, nós precisamos usar uma lista em vezes de um conjunto, já que o Maple automaticamente remove elementos repetidos em um conjunto e nós perderíamos todas as repetições.)
 '''''happylist := [ happy $ 4]; '''''
 '''''happyset := happy $ 4 ; '''''

=====3. Encontre o número de resultados possíveis em uma partida de dois times quando o vencedor é o primeiro time a ganhar 5 de 9, 6 de 11, 7 de 13 ou 8 de 15 jogos.=====
'''Solução'''

Nossa solução vai usar o procedimento Maple chamado ''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.
A implementação Maple dessa descrição é mostrada abaixo.
 '''''Tournaments:=proc(games::integer) '''''
 '''''  local i, one_wins, two_wins, Temp, S; '''''
Inicialize uma lista para garantir que o time 1 vença
 ''''' one_wins:=[seq(1, i=1..ceil(games/2))]; '''''
Inicialize uma lista para garantir que o time 2 vença
 ''''' two_wins:=[seq(2, i=1..ceil(games/2))]; '''''
 '''''  S:={}; '''''
Percorra até nós termos todos os jogos da série usados
 ''''' while nops(one_wins) <= games do '''''
Calcule os resultados possíveis que completam em jogos exatos
 '''''   Temp:=permute(one_wins); '''''
 '''''    for i from 1 to nops(Temp) do '''''
Garanta que nós realmente precisamos de todos os jogos (ou seja, o último jogo da série foi vencido pelo time 1)
 '''''      if Temp[i][nops(one_wins)] = 1 then '''''
 '''''         S:=S union Temp[i] '''''
 '''''      fi; '''''
 '''''    od; '''''
Calcule os resultados possíveis que completa em jogos exatos
 '''''   Temp:=permute(two_wins); '''''
 '''''    for i from 1 to nops(Temp) do '''''
Garanta que nós realmente precisamos de todos os jogos (ou seja, o último jogo da série foi vencido pelo time 2)
 '''''      if Temp[i][nops(two_wins)] = 2 then '''''
 '''''         S:=S union Temp[i] '''''
 '''''      fi; '''''
 '''''    od; '''''
Incremente o número de jogos, para que o time vencedor do torneio perca um jogo a mais.
 '''''   one_wins:=[op(one_wins), 2]; '''''
 '''''    two_wins:=[op(two_wins), 1]; '''''
 '''''  od; '''''
 '''''  S; '''''
 '''''end: '''''
Agora nós usamos esse procedimento recentemente criado em torneios que são o melhor de “3-de-5” e o melhor de “4-de-7” em número de jogos.
 '''''Tournaments(5); '''''
 '''''nops(%); '''''
 '''''nops(Tournaments(7)); '''''
Ao leitor é deixado explorar os casos restantes, e conjecturar uma fórmula no caso geral.

=====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'' cresce.=====

'''Solução'''

Primeiro tentaremos um exemplo, para ver o que exatamente desejamos fazer, e então escrever um programa.
 '''''c := binomial(6,3); '''''
Nós usamos a função ''ifactors'' (o '''i''' significa '''integer''') para fatorar '''c'''. Essa função é uma das várias do Maple que deve ser definida '''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.
 '''''readlib(ifactors): '''''
 '''''ifacts := ifactors(c); '''''
A página de ajuda para ''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.
 '''''facts := ifacts[2]; '''''
Isso nos dá uma lista de listas, onde o primeiro elemento em cada lista é o fator primo, e o segundo é a multiplicidade (o número de vezes que o fator aparece) daquele primo. Então nós queremos percorrer a lista e obter o segundo elemento de cada sublista.
 '''''powers := seq(x[2],x=facts); '''''
Então nós usamos a função ''max'' para encontrar o maior expoente.
 '''''max(powers); '''''
Se o maior exemplo é maior que 1, então <math>C(2n, n)</math> é divisível pelo quadrado de um primo. Nesse caso, o maior exemplo 2 é, de fato, maior que 1, e <math>C(6, 3)</math> sem dúvida é divisível por <math>5^2</math>.
Combinando esses passos, agora nós escrevemos um programa que dado '''n''', retorna o maior expoente na fatorização de <math>C(2n, n)</math>.
 '''''LargestExpon := proc(n) '''''
 '''''local c, ifacts, x; '''''
 '''''    c := binomial(2*n,n); '''''
 '''''    ifacts := ifactors(c); '''''
 '''''    max(seq(x[2],x=ifacts[2])); '''''
 '''''end: '''''
 '''''LargestExpon(6); '''''
Agora nós vamos escrever outra rotina que vai calcular o maior expoente para muitos valores de '''n''', e armazenar os resultados numa tabela.
 '''''Manyn := proc(maxn) '''''
 '''''local results, i; '''''
 '''''  for i to maxn do '''''
 '''''      results[i] := LargestExpon(i); '''''
 '''''      if results[i] = 1 then '''''
 '''''         printf(`Hurray! A counterexample! %d`, i); '''''
 '''''      fi; '''''
 '''''  od; '''''
 '''''  eval(results); '''''
 '''''end: '''''
Rode o programa e veja o que acontece.
 '''''Manyn(10): '''''
Parece que 1, 2 e 4 são valores de '''n''' tais que <math>C(2n, n)</math> não é divisível pelo quadrado de um primo.
 '''''binomial(8,4); '''''
 '''''ifactors(%); '''''
Agora deixe o programa rodar por muito mais tempo, e veja se nós podemos encontrar algo mais.
 '''''vals := Manyn(200): '''''
Vamos olhar para o crescimento do expoente máximo representando graficamente os resultados.
 '''''plot([ seq([i,vals[i]],i=1..200)],style=POINT, '''''
 '''''title=`Growth of Largest Exponents`); '''''
Para comparar, tente novamente com ainda mais valores de '''n'''.
 '''''vals := Manyn(300): '''''
Dessa vez, plote com os pontos que participaram, para ver que diferença isso faz.
 '''''plot([ seq([i,vals[i]],i=1..300)], '''''
 '''''title=`Growth of Largest Exponents 2`); '''''
É difícil encontrar quaisquer conclusões desses dois gráficos, além de que não parece ser um limite para o tamanho. O tempo de cálculo está se tornando longo, mas ainda podemos olhada para alguns exemplos maiores.
 '''''LargestExpon(500); '''''
 '''''LargestExpon(1001); '''''
 '''''LargestExpon(1005); '''''
 '''''LargestExpon(1007); '''''
 '''''LargestExpon(1009); '''''

=====5 . Estime a probabilidade que dois inteiros escolhidos aleatoriamente sejam relativamente primos testando um grande números de pares de inteiros aleatoriamente selecionados. Observe o teorema que dá essa probabilidade e compare seus resultados com a probabilidade correta.=====

'''Solução'''

Para resolver esse problema, três coisas devem ser feitas.
#Crie um método para gerar pares de inteiros aleatórios.
#Produza um grande número desses pares, testando se eles são relativamente primos, e observe a probabilidade estimada baseada nessa amostra.
#Observe o teorema mencionado em questão.


Naturalmente, nós deixaremos a parte 3 inteiramente para o leitor.
Uma simples aproximação é usar o procedimento do Maple ''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'' em um segundo loop. Nós implementamos esses dois loops em um novo procedimento Maple chamado ''RandPairs'':
 '''''RandPairs := proc(list_size::integer) '''''
 '''''  local i, tmp, randnums, count; '''''
 '''''  randnums := NULL; '''''
Gera a lista de inteiros aleatórios
 ''''' for i from 1 to list_size do '''''
 '''''    tmp := rand(); '''''
 '''''    randnums := randnums, tmp(); '''''
 '''''  od; '''''
 '''''  randnums := [randnums]; '''''
Conta o números de pares que são coprimos
 ''''' count := 0; '''''
 '''''  for i from 1 by 2 to list_size-1 do '''''
 '''''    if igcd(randnums[i], randnums[i + 1]) = 1 then '''''
 '''''      count := count + 1; '''''
 '''''    fi; '''''
 '''''  od; '''''
 '''''  count; '''''
 '''''end: '''''
Podemos agora executar esse procedimento em 1000 pares de inteiros, como a seguir:
 '''''RandPairs(200); '''''
Então, podemos determinar a porcentagem de pares coprimos usando esse resultado.
 '''''evalf(RandPairs(200)/100); '''''
Observe que repetindo a computação idêntica pode muito bem levar a um resultado de certa forma diferente já que a lista de inteiros que usamos foi gerada aleatoriamente. Você deve tentar isso como uma amostra de tamanho muito maior, digamos 10000 pares de inteiros.

=====6. Determine o número de pessoas necessárias para assegurar que a probabilidade de apenas duas delas terem o mesmo dia do ano como seu aniversário é pelo menos 700 porcento, pelo menos 800 porcento, pelo menos 900 porcento, pelo menos 955 porcento, pelo menos 988 porcento, e pelo menos 999 por cento.=====
'''Solução'''

Dado que sabemos a fórmula para a probabilidade de duas pessoas fazerem aniversário no mesmo dia, nós podemos usar Maple para percorrer uma variedade de número de pessoas possíveis, até que alcancemos a probabilidade maior que a probabilidade desejada.

Se considerarmos a probabilidade que nenhuma dupla de pessoas possuem o mesmo aniversário como '''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''', 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>.
Agora nós representamos e combinamos essa informação num procedimento Maple chamado “Birthdays”.
 '''''Birthdays := proc(percentage::float) '''''
 '''''  local num_people, cur_prob; '''''
Inicializa
 ''''' cur_prob := 0; num_people:=0; '''''
Percorre enquanto houver pessoas
 ''''' while cur_prob < percentage do '''''
 '''''    num_people := num_people + 1; '''''
 '''''    cur_prob := 1  '''''
 '''''       -(numbperm(365,num_people) / 365^num_people); '''''
 '''''  od; '''''
 '''''  RETURN(num_people); '''''
 '''''end: '''''
Esse procedimento retorna o número de pessoas requeridas para atingir a probabilidade dada de que duas pessoas tenho o mesmo aniversário. Agora nós executamos nosso procedimento em alguns casos de teste, para probabilidades de 0.70, 0.80 e 0.90;
 '''''Birthdays(.70); '''''
 '''''Birthdays(.80); '''''      
 '''''Birthdays(.90); '''''

==='''7. Exercícios/Projetos'''===
1. Use Maple para gerar várias filas do triângulo de Pascal, veja se você pode formular algumas conjecturas satisfeitas pelos coeficientes binomiais C(n,k).

2. Use o Maple para determinar quantas palavras diferentes podem ser feitas com a palavra PAPARRAZZI quando todas as letras forem usadas; quando algum número de letras forem usadas; quando todas as letras forem usadas e a palavra começa e termina com a letra Z; quando todas as letras são usadas e os três A’s são consecutivos. 

3. Use o Princípio da casa dos pombos para projetar e então implementar um procedimento Maple que encontre a subsequência crescente máxima de uma dada sequência de números. (Veja a página 2455, et seq no seu texto.)

4. Suponha que um certo Departamento de Matemática possui “m” professores e “f” professoras. Escreva um procedimento maple para encontrar todos os comitês com 2000 membros em que ambos os sexos são representados igualmente.

5. Use Maple para provar a identidade <math>\binom{n+1}{k} = (n+1)\binom{n}{k-1}/k</math>, para inteiros positivos n e k com <math>k \leq n</math>.

6. Use Maple para provar a identidade de Pascal: <math>C(n+1, k) = C(n, k-1)+C(n, k)</math>, para todos os inteiros positivos n e k com <math>k \geq n</math>.

7. Use Maple para determinar o inteiro k ao qual as chances de se pegar seis números corretamente em uma loteria dos primeiros k inteiros positivo é menor que
#1 em 1000 milhões,
#1 em um bilhão (10^9),
#1 em 100 bilhões,
#1 em 1000 bilhões, e
#1 em um trilhão (10¹²).

8. Use Maple para contar e listar todas as soluções para a equação <math>x_1+x_2+x_3+x_4 =25</math> onde <math>x_1</math>, <math>x_2</math>, <math>x_31</math> e <math>x_4</math> são inteiros não negativos.

9. Gere um grande triângulo de números Stirling e procure por padrões que sugerem identidades entre os números Stirling. (Um pequeno triângulo foi mostrado na seção 4.22.) Você pode fazer quaisquer conjecturas sobre a relação entre os números de Stirling e os coeficientes binomiais?

10. Escreva uma função Maple que recebe como entrada três inteiros positivos  n, k e i, e returna o i-ésimo multinomial, em ordem lexicográfica, do polinomial <math>(x_1+x_2+\cdots +x_k)^n</math>. Escreva seu inverso; isto é, dado um multinomial, o inverso deve retornar seu índice (posição) no polinomial ordenado.

11. Escreva um programa Maple para computar a expansão de Cantor de um inteiro. (Veja página 2988 do livro.)

12. Implemente, em Maple, o algoritmo para gerar o conjunto de todas as permutações dos primeiros “n” inteiros, usando a bijeção da coleção de todas as permutações do conjunto {<math>1, 2, \cdots , n</math>} para o conjunto {<math>1, 2, \cdots , n!</math>} descrito anteriormente no exercício 100 na página 2988 do livro.

13. Escreva um procedimento Maple para gerar permutações aleatórias como descritas no exercício 144 da página 2988 do livro.


=='''Exemplos Extras'''==

===Exemplos extras da seção 4.1===
====Exemplo 4.1.1====
''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]]

====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 
inicio 
    de j=1 ate n  
         print  hello  
    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 
inicio 
    de j=1 ate n  
         print  hello  
    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 quantas possibilidades pode ser formada a fila.

''(b) 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). 

[[Exemplo 4.1.6 - Solução]]

====Exemplo 4.1.7====
''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 :

[[Exemplo 4.1.7 - Solução]]

===Exemplos da Seção 4.2===

===== 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)''

[[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 =====

''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.(pág. 315)''

[[Exemplo 4.2.4 - Solução]]

===== 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 devem ser escolhidos de modo a garantir que, pelo menos, oito pertencem à mesma classe.(pág. 315)''

[[Exemplo 4.2.5 - Solução]]

===Exemplos adicionais relativos a Seção 4.3===

'''Exemplo 4.3.1'''

''Uma classe tem 30 alunos matriculados. De quantas maneiras pode-se: (pág 321)

''(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?''

[[Exemplo 4.3.1 - Solução]]

'''Exemplo 4.3.2 '''

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

[[Exemplo 4.3.2 - Solução]]


'''Exemplo 4.3.3 (pág 324)'''

...

[[Exemplo 4.3.3 - Solução]]

'''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)''

[[Exemplo 4.3.4 - Solução]]

'''Exemplo 4.3.5 '''

''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)''

[[Exemplo 4.3.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;

''b)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 numero de subconjuntos de tamanho 5,tal que T:(pág 324)''

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

[[Exemplo 4.3.7 - Solução]]

===Exemplos adicionais relativas a Seção 4.4===
'''Exemplo 4.4.1 '''

''Escreva a expansão de (x+2y)³. (pág 328)''

[[Exemplo 4.4.1 - Solução]]

'''Exemplo 4.4.2 '''

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

[[Exemplo 4.4.2 - Solução]]

'''Exemplo 4.4.3 '''

''Escreva a expansão de <math>(x^2-\frac{1}{x} )^8</math>. (pág 328)''

[[Exemplo 4.4.3 - Solução]]

===Exemplos adicionais relativas a Seção 4.5===
'''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 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.) (pág 339)''

''(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.''

[[Exemplo 4.5.3 - Solução]]


'''Exemplo 4.5.4'''

''De quantas maneiras é possivel colocar 7 das 8 letras de “CHEMISTS” em uma fila? (pág 339)''

[[Exemplo 4.5.4 - Solução]]

===Exemplos adicionais relativas a Seção 4.6===
'''Exemplo 4.6.1'''

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

<math>461325, 326145, 516243, 324165, 461235, 324615, 462135</math>

[[Exemplo 4.6.1 - Solução]]


'''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 '''

''Encontre a permutação de 1, 2, 3, 4, 5, 6 imediatamente antes de 261.345 em ordem lexicográfica. (pág 345)''

[[Exemplo 4.6.3 - Solução]] 


'''Exemplo 4.6.4 '''

''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. (pág 345)''

[[Exemplo 4.6.4 - Solução]]


'''Exemplo 4.6.5 '''

''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]]