Ola carissimo Luis Lopes e demais
colegas desta lista ... OBM-L,
( escreverei sem acentos )
Vamos IMAGINAR que os possiveis totais acumulados apos o N-esimo lancamento
da moeda estao dispostos ao longo de uma coluna, numerados de cima para baixo,
de 1 ate 2^N. Represetaremos por Tn o total de resultados possiveis distintos;
por Tni um particular resultado.
Exemplos
1) coluna 1 : 0,1
T1=2, T11=0 e T12=1
2) coluna 2 : 0,1,0.5,2
T2=4, T21=0, T22=1, T23=0.5 e T24=2
3) coluna 3 : 0, 1, 0.5, 2, 0.25, 1.5, 1, 3
T3=7, T31=0,T32=1, T33=0.5, T34=2, T35=0.25, T36=1.5, T37=1 e T38=3
Note que estou convencionando que os Tni com i impar promanam da fortuna
acumulada anteriormente pela multiplicacao por 0.5; com i par, pela adicao
de 1.
Agora vou introduzir uma representacao para os possiveis totais acumulados
Representarei por A o ato de multiplicar por 0.5; O ato de somar 1 sera
representado por B. Os exemplos anteriores ficarao assim :
Exemplos
1) coluna 1 : A,B
T1=2, T11=A e T12=B
2) coluna 2 : AA,AB,BA,BB
T2=4, T21=AA, T22=AB, T23=BA e T24=BB
3) coluna 3 : AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBB
T3=7, T31=AAA,T32=AAB,...,T37=BBA e T38=BBB
E facilver que a N-esima coluna sera representada por TODOS os arranjos de
comprimento N que podemos fazer dispondo de 2 letras ... E igualmente
claro que metade dos arranjos da N-esima coluna iniciam com A, a outra metade
iniciando com B. Ora, e obvio que podemos descartar os A's iniciais
dos arranjos
iniciados com A, pois eles equivalem a multiplicar por 0.5 o valor inicial zero.
Exemplo
AABB = 0*(0.5)*(0.5) + 1 + 1 = 1 + 1 = BB
ABABB=(((0*(0.5)+1)*(0.5))+1)+1=1*(0.5)+1+1=BABB
Assim, se tomarmos todos os arranjos da coluna N iniciados com A ( a
metade superior
da coluna N ) e descartarmos o primeiro A de cada um, restara,
claramente, TODOS OS
ARRANJOS DA COLUNA n-1, cujo numero de elementos distintos ja
convencionamos designar
por Tn-1. portanto :
Tn = Tn-1 + VALORES INEDITOS DA METADE INFERIOR DA COLUNA N (1)
Os valores ineditos surgem na metade inferior da coluna N, sao todos
eles arranjos
iniciados com a letra B. Todavia, e claro que nem todo arranjo
iniciado com a letra
B representa um valor inetido. Por exemplo, na coluna 3 temos que T37=BBA=1 e um
valor que nao e inedito.
Vamos portanto introduzir um novo conceito. Para ver a motivacao para
ele considere
os exemplos abaixo :
Exemplos
1) BBA = (1+1)*(0.5)=2*(0.5)=1 = BBA=B
2) BBBA=(1+1+1)*(0.5) = 1*(0.5)+1 = 1.5 = BBBA=BAB
3) BABBA=((0.5)+2)*(0.5)=(0.25)+1 = 1.25 = BABBA=BAAB
Pensando um pouco sobre os exemplos acima e facil perceber que quando A ESQUERDA
DE ALGUM A HA DOIS OU MAIS B CONSECUTIVOS, o valor numerico
representado pelo
arranjo pode ser representado por um arranjo de comprimento menor. Isso motiva a
seguinte definicao :
DEFINICAO : Um arranjo e dito ser IRREDUTIVEL se a esquerda de qualquer de suas
letras A nao existe duas ou mais letras B consecutivas. Um arranjo que nao e
IRREDUTIVEL e dito ser REDUTIVEL
Os arranjos redutiveis, cujo valor numerico intrinseco pode ser
representado por um
arranjo de comprimento menor, nao nos interessam, pois, pela relacao
(1) deduzida acima,
eles ja foram computados. Interessa-nos os arranjos irredutiveis, pois
sao deles
que promanam valores ineditos. Ora, os arranjos irredutiveis iniciam sempre com
um unico B e a esqueda de qualquer A que porventura nele exista ha, no
maximo, um B.
Sao portanto exemplos de arranjos irretudiveis :
Exemplos :
1) BABABA, BAAA, BABAB, BAAABAABA, BB
Os arranjos irredutiveis permitem uma representacao mista interessante
: todos as
letras B que estao a direita da letra A mais a direita representam um
numero natural,
nomeadamente igual ao numero de letras B que lá existam; a parte
restante do arranjo
(a esquerda da letra A mais a direita, inclusive esta letra A )
representa um numero
binario decimal.
Exemplos
1) BABABBB = BABA + BBB = BABA + 3 = ((1*(0.5)+1)*0.5) + 3 = 3 + [0.11],
onde a parte entre colchetes e um numero real em sua representacao na base dois.
2) BAABA = (1*((0.5)^2)+1)*(0.5) = [0.101]
Assim, toda arranjo irredutivel R pode ser colocado na forma R = I +
[D], onde I e a
PARTE INTEIRA e D a PARTE DECIMAL - em base 2- da representacao
mista. Considerando
esta representacao mista, fica facil ver que :
LEMA 1 - Todo arranjo irredutivel representa um valor inedito, vale
dizer, um valor que
nao surgiu em qualquer das colunas anteriores
LEMA 2 - Dois arranjos irredutiveis distintos de mesmo comprimento
representam valores
distintos
Os fenomenos 1) e 2) acima nos permitem melhorar a relacao (1)
deduzida acima, colocando-a
como :
Tn = Tn-1 + TOTAL DE ARRANJOS IRREDUTIVEIS da coluna N (2)
Vejam que agora este despretencioso problema nos conduzia a
consideracao de um belo
problema de Analise Combinatoria, nomeadamente o calculo do numero de
arranjos irredutiveis
de comprimento N :
PROBLEMA : Usando duas letras, quantos arranjos distintos - de
comprimento N - podemos
fazer de maneira que
