Re: [obm-l] Probabilidade

["Paulo Santa Rita" <paulo.santarita@xxxxxxxxx>]

Ola Lucas,

E verdade, voce esta se referindo a 7 = 1+2+4. Vou dar uma olhada na
segunda linha linha do algoritmo e ver onde errei.

Obrigado pela observacao

Um Abraco
Paulo Santa Rita
6,1233,090B07

Em 09/11/07, Paulo Santa Rita<paulo.santarita@xxxxxxxxx> escreveu:
> Ola Lucas,
>
> A Matriz estava com um erro de digitacao e eu enviei uma mensagem para
> a lista corrigindo. Nao consigo ver erro no algoritmo, pois a sua
> observacao esta errada : O coeficiente de X^7 em p4 TEM QUE SER 1,
> pois, com parcelas DISTINTAS e, no maximo, iguais a 4, so ha uma
> maneira de particionar 7: 7 = 3 + 4
>
> Nao serve 1 + 6, por 6 > 4
> Nao serve 2 + 5 porque 5 > 4
> Nao serve 7 porque 7 > 4
>
> Que outra forma voce particiona 7 em parcelas distintas e no maximo iguais a 4 ?
>
> Quanto a sua segunda observacao, eu mostrei como calcular um
> coeficiente particular sem desenvolver o polinomio todo. Leia com
> atencao no final da mensagem que voce vai ver.
>
> Note que numa particao, a ordem e irrelevante, isto e, 3+4 = 4+3.
>
> Muito obrigado pelas observacoes
> Um abraco
> Paulo Santa Rita
> 6,122D,090B07
>
>
>
> Em 09/11/07, Lucas Pierezan<lucas.pierezan@xxxxxxxxx> escreveu:
> > Olá Paulo,
> >
> > Acredito que o seu algoritmo não esteja funcionando corretamente devido ao passo
> > 2 , onde você diz que
> >
> > 2) P(K,L) = 1 se K =< L =< (K*(K+1))/2
> >
> > é um erro muito sutil e eu não sou muito bom com explicações mas a
> > idéa é mais ou menos a seguinte:
> > o passo dois deveria corresponder aos coeficientes de p(k-1) que foram
> > multiplicados por x^k, logo eles foram transladados k posições para a
> > direita na matriz, porém você está transladando uma sequência de 1´s e
> > não os coeficientes de p(k-1).Esse passo estaria certo se não
> > ocorresem 1´s um acima do outro.
> >
> > Veja o coeficiente de x^7 em P4, ele deveria ser 2, pois o coeficiente
> > de x^3 em P3 é 2.
> >
> > Agora, uma outra observação é que não precisamos calcular o polinômio
> > inteiro para achar o número de partições de um número x com parcelas
> > distintas e menores ou iguais a y.
> > Para isso , pensando recursivamente
> > Part(x,0) = 1 se x=0 e 0 caso contrário.
> > Part(x,y) = Part(x-y,y-1) + Part(x,y-1)
> > o primeiro caso usando o número y na partição e no segundo não usando.
> > Ou olhando o polinômio Pk como uma função geradora.
> > Acho que a ordem de complexidade desse algoritmo é x*y.(usando uma
> > tabela para guardar valores já computado).
> > O máximo que eu consegui calcular foi Part(338,338) = 724399192576, se
> > não tiver nada errado =P.
> > É possível também fazer um programa pra listar as partições e fica
> > listPat(15,7) =
> > 7 + 6 + 2
> > 7 + 5 + 3
> > 7 + 5 + 2 + 1
> > 7 + 4 + 3 + 1
> > 6 + 5 + 4
> > 6 + 5 + 3 + 1
> > 6 + 4 + 3 + 2
> > 5 + 4 + 3 + 2 + 1
> >
> > []´s
> > Lucas Pierezan Magalhães
> >
> > On Nov 9, 2007 10:29 AM, Paulo Santa Rita <paulo.santarita@xxxxxxxxx> wrote:
> > > Ola Fernando Cores, Ronaldo Alonso
> > > e demais colegas desta lista ... OBM-L,
> > >
> > > A motivacao para esta mensagem e complementar a minha manifestacao
> > > anterior, apresentando um um algoritmo simples e eficiente para o
> > > calculo dos coeficientes dos polinomios Pi já definidos. Com este
> > > algoritmo ficara facil dar uma resposta rapida e exata para o problema
> > > de combinatoria proposto pelo Fernando Cores. Relembrando,  haviamos
> > > definido os polinomios Pi pela recorrencia :
> > >
> > > P0 = 1
> > > Pi = (1 + (X^i) )*Pi-1,   i = 1, 2, 3, ...
> > >
> > > Podemos olhar a segunda equacao na forma Pi = Pi-1 + (X^i)*Pi-1.
> > > Significa isso que cada Pi "aproveita" intactos todos os monomios de
> > > Pi-1 com grau inferior a "i", reduzindo a um único monomio os monomios
> > > de mesmo grau que existam em Pi-1 e (X^i)*Pi-1. Como Pk, para todo k,
> > > e claramente um polinomio completo com termo independente igual a 1, a
> > > observação anterior conduz a seguinte algoritmo de calculo dos
> > > coeficientes de Pi :
> > >
> > > ALGORITMO
> > >
> > > Seja C = (i*(1+i))/2. IMAGINE agora uma matrix P com "i" Linhas,
> > > numeradas de cima para baixo de 1 ate "i" e com "C+1" colunas,
> > > numeradas da esquerda para a direita de 0 ate "C". Seja tambem P(K,L)
> > > o valor numerico do cruzamento da linha K com a coluna L.
> > >
> > > A principio faca P(1,0) =1, P(1,1) = 1 e P(1,L)=0 para todo 1 <  L <
> > > C. Para todo linha K fixada, tal que 1< K =< i, faca :
> > >
> > > 1) P(K,L) = 0 se L < K
> > > 2) P(K,L) = 1 se K =< L =< (K*(K+1))/2
> > > 3) P(K,L) = 0 se  L >  (K*(K+1)) / 2
> > >
> > > após preencher as "i" linhas desta matrix segundo os criterios acima,
> > > a soma dos elementos de uma coluna L qualquer, 0 =< L =< C,  fornecera
> > > o coeficiente de X^L do polinomio Pi, vale dizer, fornecera o numero
> > > de maneira de particionar o inteiro positivo L em partes duas a duas
> > > distintas e toda menores ou iguais a "i".
> > >
> > > Vou dar um exemplo. IMAGINE as numeracoes das linhas e colunas
> > > conforme a descricao que dei acima
> > >
> > > EXEMPLO : Coeficientes de P7.
> > >
> > > 11000000000000000000000000000
> > > 00110000000000000000000000000
> > > 00011110000000000000000000000
> > > 00001111111000000000000000000
> > > 00000111111111100000000000000
> > > 00000011111111111111100000000
> > > 00000001111111111111111111111
> > >
> > > Somando as colunas teremos
> > > 11122344444333322222211111111
> > >
> > > Logo, o polinomio P7 sera :
> > >
> > > P7=1+X+(X^2)+2*(X^3)+2*(X^4)+3*(X^5)+4*(X^6)+4*(X^7)+4*(X^8)+4*(X^9)+4*(X^10)+3*(X^11)+
> > > 3*(X^12)+3*(X^13)+3*(X^14)+2*(X^15)+2*(X^16)+2*(X^17)+2*(X^18)+2*(X^19)+2*(X^20)+(X^21)+
> > > (X^22)+(X^23)+(X^24)+(X^25)+(X^26)+(X^27)+(X^28)
> > >
> > > So a titulo de exemplificacao, o coeficiente de X^15 e 2, vale dizer,
> > > so existem duas maneiras de particionar 15 em parcelas distintas e
> > > menores ou iguais a 7, a saber : 2+6+7 e 3+5+7.Veja tambem que este
> > > algoritmo que imaginei e muito simples e facilimo de ser implementado
> > > em qualquer boa linguagem de programacao. Como so usa substituicoes e
> > > adicoes, sera tambem eficiente. Assim, em termos operacionais, o
> > > problema combinatorio do Fernando Cores já esta resolvido.
> > >
> > > Nos porem somos orgulhosamente Matematicos ... Sim, Matematicos ! Para
> > > nos, em geral, os algoritmos são apenas escoras que nos devem levar a
> > > uma compreensao superior das coisas. Isto posto, considerando o
> > > algoritmo descrito acima, vamos buscar uma solucao completa e acabada
> > > da questao.
> > >
> > > Fixe o algoritmo em sua cabeca. Note agora para uma coluna L > 1
> > > qualquer, o primeiro 1 surge após um "boa" quantidade de zeros. Quem e
> > > essa quantidade de zeros que antecede o primeiro 1 ? E facil ver
> > > trata-se do maior K tal que (K*(K+1)) /2 < L. Se (K*(K+1))/2 >= L
> > > entao no polinomio Pk já surge o termo X^L, ou seja, já existe um
> > > numero 1 na linha K. Feito esta observação, o calculo exato e não
> > > operacional do coeficiente de X^L na sequencia de polinomio Pi segue
> > > facilmente, a saber :
> > >
> > >
> > > COEFICIENTE DE X^L NOS POLINOMIOS Pi
> > >
> > > Doravante, chamarei de C(L,i) o coeficiente de X^L no polinomio "i"
> > >
> > > 1 ) Seja K o maior inteiro k tal que [ k*(k+1) / 2 ] < L
> > > 2) Se i =< L faca C(L,i) = i – K, Se i > L faca C(L,i) = L – K
> > >
> > > EXEMPLO
> > >
> > > Qual o coeficiente de X^1007514 em P2007 ?
> > >
> > > 1) Maior inteiro K tal que ( K*(K+1) ) / 2 < 1007514
> > > Fazendo um calculo rapido achamos K = 1419.
> > >
> > > 2) Como 2007 < 1007514 fazemos C(1007517,2007) = 2007 – 1419 =  588
> > >
> > > Assim, o coeficiente de X^1007514 em P2007 e 588. em termos do
> > > problema combinatorio do Fernando Cores significa que existem 588
> > > maneiras de dividir o conjunto A={1,2,...,2007} em duas partes
> > > disjuntas B eC tais que a soma dos elementos de B seja igual a soma
> > > dos elementos de C.
> > >
> > >
> > > O CASO GERAL
> > >
> > > PROBLEMA : De quantas maneiras e possivel expressar o conjunto A = {1,
> > > 2, 3, ..., N }
> > > na forma A = B uniao C tal que :
> > >
> > > 1) B intersecao C = conjunto vazio
> > > 2) Soma dos Elementos de B = Soma dos Elementos de C
> > >
> > > Conforme já vimos na mensagem anterior, achamos L = (N*(N+1)) /4.
> > > Perguntamos entao "Qual o coeficiente de X^L em Pn ? ". Achamos entao
> > > o maior  inteiro positivo k tal que (k*(k+1))/2 < L . Seja K este
> > > valor. Se N < L fazemos C(L,N) = N – K. Se N >= L fazemos C(N,L) = L –
> > > K.
> > >
> > >
> > > OBSERVACOES FINAIS
> > >
> > > 1) E obvio ululante que voce pode pensar em dividir o conjunto A =
> > > {1,2,...,N} não em apenas dois conjunto disjuntos B e C com mesma soma
> > > de elementos. Voce pode aplicar esta mesma tecnica para 3, 4 ou mais
> > > conjuntos, desde de que a soma 1 + 2 + ... + N seja divisivel por 3, 4
> > > etc
> > >
> > > 2) Não achei necessario justificar que o ALGORITMO que descobri
> > > realmente calcula  os coeficientes de Pi porque ele me parece evidente
> > > em face da expressao da sequencia de polinomios Pi=Pi-1 + (X^i)*Pi-1 :
> > > ele e apenas uma maneira conveniente de registrar os calculos desta
> > > expressao.
> > >
> > > 3)  Se alguem desejar divulgar ou usar em outro paper este ALGORITMO
> > > ou as tecnicas aqui apresentadas não tem problemas . Basta citar que
> > > trata-se de uma producao de um membro da LISTA DE DISCUSSAO DE
> > > PROBLEMAS DE MATEMATICA da PUC-RJ ( Lista de discussao de Matematica
> > > do Nicolau )
> > >
> > > 4) Qualquer erro aqui a culpa e toda minha. Não me milindra qualquer
> > > correcao que algum colega queira fazer. Mas lembre-se que não dispomos
> > > de muito tempo para fazer uma re-leitura ou/e correcoes : as ideias
> > > vao surgindo e nos vamos escrevendo
> > >
> > > Um Abraco a Todos
> > > Paulo Santa Rita
> > > 6,0A29,090B07
> > >
> > > Em 07/11/07, fccores<fccores@xxxxxxxxxx> escreveu:
> > >
> > > > Prezado Paulo Santa Rita,
> > > >
> > > >           Primeiramente obrigado por sua detalhada e clara explicação do
> > > > problema, apesar de também ter chegado a esta conclusão, de que os casos
> > > > favoráveis correspondem justamente ao coeficiente de x^(502*2007). Fato este
> > > > que me levou a consultar várias fontes, inclusive "Introdução à análise
> > > > combinatória", do mesmo autor do compêndio ao qual você se refere, na busca
> > > > de assuntos que ajudassem como: funções geradoras e partições de um inteiro.
> > > >          Estudei, inclusive um outro problema correlato:
> > > >
> > > >      "Determinar o coeficiente de x^k, 0=<k=<n, no desenvovimento de [1 +
> > > > ax].[1 + (a^2)x]...[1 + (a^n)x]."
> > > >
> > > >          Em verdade, o problema se resume, agora, a determinar uma maneira
> > > > explícita (ou elementar) de calcular tal coeficiente, por isso esperava
> > > > (espero), talvez outras abordagens para aquele problema, já que o mesmo é um
> > > > problema olímpico, que me foi enviado por um amigo do Chile. Formulei
> > > > algumas outras conjecturas acerca do problema, como por exemplo que aquele
> > > > coeficiente é uma potência de 2, estou trabalhando na prova.
> > > >
> > > >          Enfim, mais uma vez agradeço a clara e precisa mensagem  e
> > > > parabenizo a todos pelas excelentes e frutíferas discussões desta lista, da
> > > > qual sou um leitor assíduo.
> > > >
> > > >                      Fernando Córes
> > > >
> > > >
> > > > > Ola Fernando e demais
> > > > > colegas desta lista ... OBM-L,
> > > > >
> > > > > Responder esta pergunta exige a solucao de um problema combinatorio
> > > > > previo, qual seja, o de determinar de quantas maneiras distintas
> > > > > podemos distribuir os elementos do conjunto A={ 1, 2, 3,..., 2007 } em
> > > > > dois outros conjuntos DISJUNTOS A e B de maneira que a soma dos
> > > > > elementos de B seja igual a soma dos elementos de C. Vou reformular
> > > > > este enunciado.
> > > > >
> > > > > Seja A = { 1, 2, 3, ..., 2007 }. Queremos saber de quantas maneiras
> > > > > distintas podemos exprimir A na forma A = B uniao C, onde :
> > > > >
> > > > > 1) B intersecao C = Conjunto Vazio
> > > > > 2) Soma dos elementos de B = Soma dos elementos de C
> > > > >
> > > > > Como 1 + 2 + 3 + ... + 2007 = (2007*(1+2007))/2 = 2015028 e claro que
> > > > > a soma dos elementos de B ( e, claro, de C também ) deverá ser 2015028
> > > > > / 2 = 1007514. E e igualmente claro que para um determinando conjunto
> > > > > B com elementos oriundos de A e cuja soma destes elementos seja
> > > > > 1007514, o correspondente conjunto C que atende as exigencias 1) e 2)
> > > > > acima fica automaticamente determinado, C = A - B. Assim, precisamos
> > > > > nos preocupar apenas em determinar
> > > > >
> > > > > ( PRIMEIRA REFORMULACAO DO PROBLEMA )
> > > > >
> > > > > ( ENUNCIADO1 ) Quantos conjuntos B podemos construir tais que os seus
> > > > > elementos sejam oriundos de A e que a soma destes elementos seja
> > > > > 1007514.
> > > > >
> > > > > Seja entao B = {b1, b2, b3, ..., bn } um destes conjuntos. Como
> > > > > 1007514 = b1+b2+...+bn e bi promana de A, vale dizer, bi e inteiro
> > > > > positivo, segue que "b1+b2+...+bn" e uma PARTICAO do numero 1007514.
> > > > > Ora, uma particao de um inteiro positivo N e uma soma de inteiros
> > > > > positivos, i1 + i2 + ... + in, distintos ou não, tais que N = i1 + i2
> > > > > + ... + in. Logo, os conjuntos B que estamos buscando são em verdade
> > > > > todas as particoes de 1007514 que atendam as seguintes restricoes :
> > > > >
> > > > > 1) As parcelas devem ser duas a duas distintas
> > > > > 2) Nenhuma parcela pode ser superior a 2007
> > > > >
> > > > > Esta ultima consideracao deixa claro que o que buscamos pode ser
> > > > > expresso assim :
> > > > >
> > > > > ( SEGUNDA REFORMULACAO DO PROBLEMA )
> > > > >
> > > > > ( ENUNCIADO2 ) Quantas particoes de 1007514 podemos construir tais que
> > > > > as parcelas de cada particao sejam duas a duas distintas e nenhuma
> > > > > delas seja superior a 2007.
> > > > >
> > > > > Vamos nos fixar aqui. A principio, definimos a sequencia de polinomios :
> > > > >
> > > > > P0 = 1
> > > > > Pi = ( 1 + (X^i) )*Pi-1, i = 1, 2, 3, ...
> > > > >
> > > > > Analisando a sequencia acima, e facil ver que
> > > > >
> > > > > 1) Todo Pi tem termo independente e coeficiente lider iguais a 1
> > > > > 2) Todo Pi e um polinomio completo cujo grau e (i(1+i))/2
> > > > >
> > > > > Um fenomeno notavel - facilmente observavel e simples de explicar - e
> > > > > que, para todo "n", um monomio com parte literal X^n surgira pela
> > > > > primeira vez na sequencia de polinomios no polinomio Pi tal que "i"
> > > > > seja o menor inteiro positivo tal que (i*(1+i))/2 >= n. Isso
> > > > > claramente decorre do fato de Pi ser completo e de grau (i*(1+i)) / 2
> > > > > . E igualmente facil de ver que, após surgir, o coeficiente de X^n
> > > > > cresce ate atingir o seu valor maximo no polinomio Pn.
> > > > >
> > > > > Os coeficientes de X^n nos polinomios Pi onde ele aparece fornece
> > > > > informacoes importantes sobre as particoes de "n" em parcelas duas a
> > > > > duas distintas ... com efeito, dado que Pi = (1+ X )*(1 + (X^2) )*(1 +
> > > > > (X^3) )*...*(1+ (X^i) ), ao efetuar as multiplicacoes indicadas, um
> > > > > produto de ate "i" monomios da forma X^e, 1 =< e =< i, vai contribuir
> > > > > para a formacao final do coeficiente de X^n se a soma dos seus
> > > > > expoentes for "n", vale dizer, o coeficiente de X^n em Pi, i =< n, e
> > > > > igual ao numero de particoes de "n" em parcelas duas a duas distintas,
> > > > > todas menores que i+1. Por esta razao, o que estamos buscando pode ser
> > > > > expresso assim :
> > > > >
> > > > > ( TERCEIRA REFORMULACAO DO PROBLEMA )
> > > > >
> > > > > ( ENUNCIADO3 ) Qual e o coeficiente de X^1007514 em P2007 ?
> > > > >
> > > > > Assim, fica claro a ligacao deste problema com a Teoria das Particoes.
> > > > > Este tema da teoria dos numeros e bastante amplo e antigo, com belas
> > > > > contribuicoes de Euler, Ramanujam e outros. O livro abaixo, elementar
> > > > > e introdutorio, trata desse tema :
> > > > >
> > > > > Introducao a Teoria dos Numeros
> > > > > Colecao Matematica Universitaria - IMPA
> > > > > Autor
> > > > >
> > > > > Voce tambem pode ver isso aqui :
> > > > >
> > > > > http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf
> > > > >
> > > > > Um Abraco a Todos
> > > > > Paulo Santa Rita
> > > > > 4,0738,070A07
> > >
> > > =========================================================================
> > > Instruções para entrar na lista, sair da lista e usar a lista em
> > > http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> > > =========================================================================
> > >
> >
> > =========================================================================
> > Instruções para entrar na lista, sair da lista e usar a lista em
> > http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> > =========================================================================
> >
>

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================