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.

1. 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”.)
2. 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”.)
3. 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
draw Para gerar um objeto aleatório de um dado tamanho
allstructs Para gerar todos os objetos de um dado tamanho
iterstructs Para gerar a “próxima” estrutura de um dado tamanho

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]);

choose([apple, apple, orange]);

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

randcomb([chocolate, vanilla, cookiedough],2);

randcomb(5,3);

Neste exemplo, o 5 representa o conjunto ${1,2,3,4,5}$.

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

count(Combination([apple,orange,pear]),size=2);

allstructs(Combination([apple,orange,pear]), size=2);

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 $C(n,r)$, 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 $r\leq n$, 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 $(a+b)^{n}$ quando este é expandido.

for n from 1 to 7 do

        sort(expand((a + b)^n));

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

        seq(binomial(n, k), k = 0..n);

od;

O valor do binomial(n, k) é o coeficiente do termo binomial $a^{k}b^{n-k}$ (que é igual ao coeficiente de $a^{n-k}b^{k}$) na expansão de $(a+b)^{n}$. 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

k := 'k': # from n and k

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

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 ${\binom {n}{k}}={\binom {n}{n-k}}$ pode ser provada da seguinte forma.

left := binomial(n, k);

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

right := convert(right, factorial);

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 ${\frac {n!}{n_{1}!n_{2}!n_{3}!\cdots n_{k}!}}$ em cada $n_{1},n_{2},n_{3},\cdots n_{k}$ 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 $n_{1},n_{2},\cdots n_{k}$ 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 $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{k}^{n_{k}}$ na expansão do polinomial $(x_{1}+x_{2}+\cdots +x_{k})^{n}$. 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;

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

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

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

op(3, p);

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:

1. insira um polinomial “p” e um termo multinomial term.
2. processe p da seguinte:
   1. ordene p em q
   2. crie uma lista r de termos multinomiais em q.
   3. 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.)
3. 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;

p := expand(p);

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

coeff(x^3 - 2*x^2 + 1, x^2);

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

multinomial(6, 1, 2, 3);

p := expand((a + b + c)^6);

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:

$S_{n}(x)=x.(x-1).(x-2).\cdots .(x-n+1)$

Quando expandido, $S_{n}(x)$ tem a forma:

$S_{n}(x)=s(n,1)x+s(n,2)x^{2}+s(n,3)x^{3}+\cdots +s(n,n)x^{n}$

Os coeficientes $S(n,k)$, para $1\leq k\leq n$, 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 $\Gamma$.

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 $\Gamma (n+1)=n!$. 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));

simplify(%);

expand(%);

sort(%);

coeffs(%);

[%];

Portanto, nós temos uma lista de números Stirling $S(9,k)$, para $k=1,2,\cdots ,9$. 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 $5=1+1+3$ é 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.