90
edits
Changes
no edit summary
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.
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 é:
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 />'''''<br />
'''''choose([apple, apple, orange]);'''''
Nós também podemos escolher combinações aleatórias.
'''''randcomb([chocolate, vanilla, cookiedough],2);'''''<br />
'''''randcomb(5,3);'''''
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);'''''
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.