90
edits
Changes
Jump to navigation
Jump to search
no edit summary
'''''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/flase 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);'''''
