Análise combinatória rudimentar – Parte 1

Pessoal, em alguns posts eu fui empregando diretamente certas fórmulas de combinações e permutas sem cerimônia, e como não gosto disso, pois (em minha opinião) equações devem ser deduzidas e discutidas independentemente sempre que possível, resolvi fazer este post. Ele é uma espécie de revisão mesclada com demonstrações e exemplos, sempre que possível em química. Minha referência principal para as demonstrações é o livro Probability Theory: A Concise Course do Y. A. Rozanov, traduzido do russo por Richard A. Silverman (1969). É um livro bastante interessante, difícil de ler (para um químico) mas, com certo esforço do leitor torna-se claro e objetivo. Diferente de muitos livros do gênero, ele mostra a raiz matemática de muitas equações e teoremas clássicos da estatística e teoria das probabilidades. Eu modifiquei a apresentação e algumas das provas de maneira a clarificar (no meu ponto de vista) seu entendimento. Ou seja, eu não copiei o livro, mas penso que usei bom senso o suficiente. Os exemplos em química são uma tentativa de mostrar que a contribuição destas fórmulas simples é maior do que pensamos, sendo o mais clássico deles o uso do triângulo de Pascal em intensidades relativas de picos de RMN.

Teorema 1a

Prova:
Podemos pensar que este conjunto de pontos (ai,bj) sejam coordenadas num plano cartesiano formado pelas variáveis x e y:

Prova 1a

O número de círculos é o número de pares (ai, bj), ou seja, n1 x n2. Uma outra maneira que gosto de visualizar neste tipo de caso é uma contagem dos pontos, considerando que ai pode ser a1, ou a2, … ou an1, e para cada uma destas escolhas há a possibilidade de que bi seja b1, ou b2, … ou bn2. Deste modo teríamos n1 x n2 pares novamente. Uma maneira mais fácil de observar isso, e que pretendo usar algumas vezes neste post, é a seguinte (os números entre parênteses representam uma contagem):

Prova 1b

Ex.: Um exemplo claro da aplicação deste teorema em química/estatística seria para o cálculo do número de experimentos a se fazer num planejamento fatorial 2^2 por exemplo, em que o expoente indica o número de variáveis em que os efeitos de dois níveis serão investigados, “+” e “-“ (seguindo a notação usual). Ora, sabemos que sem replicatas haveriam 4 experimentos, representando as seguintes combinações: (+,+), (+,-), (-,+) e (-,-). Fazendo a analogia com o teorema 1 acima apresentado, temos a1 e a2 equivalendo a “+” e “-“, ou seja, n1 = 2, e similarmente temos que b1 e b2 representam “+” e “–“, sendo n2 = 2. Desta forma o número de experimentos (sem replicatas) é n1 x n2 = 2 x 2 = 4. Reparem na semelhança entre a prova no plano cartesiano acima e os diagramas dos efeitos em diferentes níveis usados em planejamentos fatoriais:

Planejamento fatorial

Teorema 2a

Este é um caso mais geral, de modo que se r = 2, temos o caso apresentado no teorema 1. Para demonstrar esse é um pouco mais complicado. Francamente não me satisfiz muito com a dedução do livro de referência citado no início do blog. Mas ele dá um ponto de partida para o uso da indução matemática na demonstração, que vou continuar por conta própria. Por isso, matemáticos que verificarem imperfeições, agradeço se me corrigirem.
Antes de mais nada, acho que é meio intuitivo deduzir que o número de arranjos para este caso mais geral é n1 x n2 x … x nr pela própria “intuição” geométrica usada para demonstrar o teorema 1. Se temos, por exemplo, três conjuntos, com n1 elementos ‘a’, n2 elementos ‘b’ e n3 elementos ‘c’. Sabemos, pelo teorema 1, que temos n1 x n2 duplas considerando os elementos ‘a’ e ‘b’. Basta dizer que cada um destes pares (ai,bj) são na verdade elementos 1, 2, 3, …. , n1 x n2. Neste caso faz-se o pareamento dos n1 x n2 elementos de (ai,bj) com os n3 elementos de ‘c’, o que resulta em n1 x n2 x n3 (pelo teorema 1). Tento mostrar esta forma de pensar no esquema abaixo:

Prova 2e

Alguns livros de estatística mostram todas estas combinações em esquemas como este:

Prova 2b

Se este esquema não está claro o suficiente, podemos ainda usar mais uma dimensão além das duas usadas na prova do teorema 1, e construir um cubo onde os pontos correspondem a todos os arranjos possíveis dos elementos. No caso do quadrado, multiplicar o número de pontos de uma aresta (n1, por exemplo) pelo número de pontos da outra (n2) resulta no número total de pontos no plano cartesiano. O mesmo pode ser feito considerando mais uma aresta, de modo que o número de pontos no cubo (ao invés de no plano) é n1 x n2 x n3.
A transformação de três grupos ‘a’, ‘b’ e ‘c’ em dois, (ai,bj) e ck, também pode ser feita quando consideramos um quarto com n4 elementos, um grupo ‘d’ qualquer. Neste caso combinamos ‘a’, ‘b’ e ‘c’ em (ai, bj, ck) (com n1 x n2 x n3 elementos) e pareamos com os elementos do grupo ‘d’, resultando em n1 x n2 x n3 x n4 possíveis arranjos (ainda segundo o teorema 1). Obviamente este raciocínio pode ser estendido para r conjuntos ‘a’ (a1, a2, …, an1), ‘b’ (b1, b2, …, bn2), …, ‘x’ (x1, x2, …, xr), o número de possíveis arranjos sendo n1 x n2 x n3 x … x nr (enunciado do teorema 2). Esse número de arranjos, N, seria então:

N

Como disse antes, tentarei usar o princípio da indução finita para provar esta afirmação.

Prova:

A prova do teorema 1 mostra que N(r = 2), ou a proposição P(r = 2), equivale a n1 x n2, resultado a partir do qual inferimos a equação para N(r) acima. Basta provar que vale para qualquer inteiro positivo r. O valor de P(1) é simplesmente n1, pois só existe n1 formas de se escolher um único elemento do conjunto a1, a2, …, an1. Ou seja, ou é a1, ou a2, … ou an1. P(0) equivale a 1, pois só existe uma maneira de dispor nenhum elemento. P(3) foi provada pouco acima. Resumindo estas informações, temos que:

P0

Considere agora P(r). Neste caso temos que:

Pr

Confirmamos as proposições para pequenos valores de r:

P1P2P3

Mas como sabemos independentemente da veracidade de P(1) (embora P(2) e P(3) tenham sido provadas, elas serviram mais para dar mais confiança à intuição do resultado para qualquer r), P(r) é portanto válida para qualquer r inteiro positivo diferente de zero.

Ex. 1: Se os grupos ‘a’, ‘b’, …, ‘x’ possuem o mesmo número de elementos n, então o número de r-tuplos possíveis é tal que n1 = n2 = … = nr = n, de modo que:

Nr

Se ainda, por outro lado, os grupos não só possuem o mesmo número de elementos, mas na verdade são arranjos dos mesmos elementos numa sequência ai1, ai2, …, air – ou seja: a1 = b1 = … = x1; a2 = b2 = … = x2; …; an = bn = … = xn – então este sistema é análogo ao de amostragem com reposição. O número de arranjos é também n^r. Como exemplo simples suponha que jogamos um dado duas vezes (ou dois dados iguais). O primeiro valor pode ser 1, 2, 3, 4, 5 ou 6 assim como o valor para o segundo lance do dado. São os mesmos números nos dois grupos, no primeiro e no segundo lance (ou primeiro e segundo dados). Teríamos neste caso 6 x 6 = 36 pares de possíveis resultados (1,1), (1,2), … (1,6), …, (6,1), (6,2), …, (6,6). Suponhamos que tivéssemos dois dados, ambos com seis números, só que o segundo apresenta números 7, 8, 9, 10, 11 e 12 (por exemplo). Se computássemos os resultados do lance dos dois dados, o número de pares seria o mesmo (36), porém não teríamos um sistema análogo ao da amostragem com reposição. Esse termo, amostragem com reposição, evoca o exemplo de um sorteio, no qual retiramos de um saco com 6 bolas marcadas (cada uma com um número) uma bola aleatoriamente. A cada sorteio repomos a bola que tiramos anteriormente, de modo que o número total de possíveis pares de resultados no sorteio é 36. Este exemplo é análogo ao dos dois lances do mesmo dado.

Ex. 2: Se falo acima da amostragem com reposição, como seria a amostragem sem reposição? Bom, suponha que coletamos de um grupo ‘a’ (composto por n elementos: a1, a2, …, an) um dos elementos para ser ai1. Não repomos este elemento, de modo que, uma vez usado, não pode mais aparecer na série de r coletas ai1, ai2, …, air. Na segunda coleta para registrar quem é ai2, portanto, não haverão n elementos disponíveis, mas sim n-1. Na terceira haverão n-2 e assim sucessivamente, até air, que só terá n-r+1 elementos disponíveis para corresponder (isso porque são r sorteios, e de ai1 até air temos n-0, n-1, …, n – (r-1), já que o número que subtrai de n começa com 0 e não com 1, resultando nos últimos n-r+1). Ora, o número total de arranjos pode ser obtido supondo que o primeiro grupo ‘a’ contem n elementos, o segundo grupo, ‘b’, tem n-1, e assim sucessivamente, até o grupo ‘x’ com n – r + 1. Neste caso, usando o teorema 2, teríamos N arranjos possíveis calculados pelo seguinte produtório:

Permuta 1

Em termos de fatoriais, a expressão acima adquire a seguinte forma:

Permuta 2

É fácil verificar essa transformação:

Permuta 3

Essa equação reflete o número de permutas de n elementos tomados r a r. Na amostragem com reposição elementos iguais poderiam se repetir, como por exemplo, termos um para (a1, a1), ou ao jogar dois dados obter (6,6) como um dos possíveis resultados (análogo à amostragem com reposição). Mas em certos casos isso não ocorre, ou não é pertinente. Por exemplo, encontro uma gaveta com 4 reagentes, e quero saber qual o número total de misturas entre dois reagentes eu posso fazer. Misturar porções do mesmo reagente não interessa, obviamente. Vamos supor que a ordem que eu adiciono os reagentes importa (mais adiante, na parte 2 do blog, explicarei porque isso é relevante). Adicionar água em ácido sulfúrico, por exemplo, é relativamente perigoso, por isso recomenda-se a adição do ácido na água, e eu quero fazer um experimento (mesmo que mental) seguro. Então se rotulo os cinco reagentes de 1 a 4, e considerando que quando adiciono o reagente 1 no 2 rotulo este par de (1,2), todos os possíveis pares são:

(1,2),(2,1),(1,3),(3,1),(1,4),(4,1)
(2,3),(3,2),(2,4),(4,2)
(3,4),(4,3)

São portanto 12 experimentos. Esse resultado pode ser obtido considerando uma permuta de 4 elementos dois a dois, de modo que n!/(n-r)! = 4!/(4-2)! = 4 x 3 = 12. Observem que se considerarmos um número relativamente pequeno de reagentes, digamos 10, entre metais e líquidos, teríamos 10!/(10-2)! = 90 experimentos para realizar. Portanto antes de bancar o químico maluco sem estudar patavinas, e fazer misturas aleatoriamente para ver se resulta em algo, considere que o número de permutas é enorme dada a nossa acessibilidade a compostos químicos, de uso doméstico ou não. Estudar primeiro antes de misturar reagentes não só é bom para a saúde, como reflete um certo bom senso probabilístico.
A amostragem sem reposição que falei no começo reflete um caso específico da equação das permutas. Nela consideramos r = n, ou seja, todos os elementos sorteados são selecionados numa certa ordem (esta ordem ainda importa). No exemplo acima, como as combinações são aos pares, e o número de reagentes é superior a 2 (n = 4), sempre “sobravam” (n – r) reagentes (4 – 2 = 2) em cada experimento. Na mistura (1,2), por exemplo, sobravam os reagentes 3 e 4. Mas se eu tenho só dois reagentes na bancada, só existem dois casos possíveis, (1,2) e (2,1). A equação de permutas para n = r fica, portanto:

Permuta 4

No experimento com dois reagentes, temos 2! = 2 x 1 = 2 experimentos, (1,2) e (2,1). Essa equação pode ser usada, por exemplo, para saber quantos possíveis resultados existem num sorteio na loteria de 5 números, oriundos de bolas marcadas com 40 números. O número de permutas é 40!/35! = 40 x 39 x … x 35. O logarítimo na base 10 deste número é 9,44, e como log(10^x) = x, existem aproximadamente 1.000.000.000 de possíveis sequências. Eu consideraria este fato quando fosse apostar em loterias.
Num ponto de vista mais químico, cito um exemplo real que ocorreu comigo. Precisei fazer experimentos em diferentes potenciais elétricos numa ordem aleatória, porque se eles fossem feitos na crescente – 100 mV, 200 mV, …, 800 mV (de 100 em 100 mV) – eu poderia verificar algum efeito sistemático resultante deste crescimento inter-corridas de potencial. O mesmo se fosse na ordem decrescente, de 800 mV à 100 mV. Então tive que fazer um sorteio, escolhendo um potencial aleatoriamente, por exemplo, 200 mV, sendo este meu primeiro experimento. Então os próximos já não poderiam ser mais 200 mV (se não pretendia repetir a mesma medida), de modo que as possibilidades para o próximo experimento são 7 ao invés de 8. Qual a chance de eu fazer o sorteio e obter uma ordem crescente ou decrescente de potencial? Ora, só há uma maneira para cada situação, logo são duas. O número total de permutas é n! = 8!, que é aproximadamente igual a 10^5. Logo fazer um sorteio e obter uma sequência crescente ou decrescente era de 1 em 5000 (10000/2). Consequentemente esta era a última das minhas preocupações.

Advertisements
This entry was posted in Estatística, Físico-química, Geral, Química Analítica. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s