Contagem

\usepackage{amsmath} 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.