Re: RES: problema

[Carlos Maçaranduba <soh_lamento@xxxxxxxxxxxx>]

ok,mas poderia explicar -me como eu resolvo por
funções  geratrizes???fui procurar mais sobre isso e
encontrei alguns problemas de contagem sendo
resolvidos por estas tecnicas como abaixo:

ache o números de soluções de x_1 + x_2 + x_3 = 17
tais que 2<= x_1 <=5 , 3 <= x_2 <= 6 e 4 <= x_3 <= 7 e
x_1 ,x_2 e x_3 são naturais.

Simplesmente ele faz:


(x^2 + x^3 + x^4 + x^5)(x^3+ x^4 + x^5 + x^6)(x^4 +
x^5 + x^6 + x^7) e acha o coeficiente de x^17 que é
igual a 3 ,  que é a resposta do problema...

   QUE MÁGICA É ESSA????

E O PIOR DE TUDO QUE AINDA HÁ GENTE QUE PREFERE
BIOLOGIA........


--- "M. A. A. Cohen" <mcohen@iis.com.br> escreveu: >
Como vc nao disse nada sobre qtos tipos de cada
> operador vc tem vou supor
> que os operadores e os operandos estao fixos, e seu
> objetivo eh descobrir de
> qtos maneiras pode colocar parenteses pra realizar
> essa operacao (se vc
> quiser mudar as ordens dos operadores ou inserir
> diferentes tipo de
> operando, o problema nao muda mto. o dificil acho
> que serah exatamente esse
> problema final).
> Esse, se nao me engano, eh um problema famoso. A
> resposta eh o q se costuma
> chamar de n-o numero de Catalan (vale
> [Binomial(2n,n)]/(n+1).
> Uma maneira de se provar isso eh considerar a funcao
> geratriz F cujo
> coeficiente de x^n eh a resposta do problema para
> cada n. Ai vc nota que
> sempre existe exatamente UM operando fora de todos
> os parenteses (que serve
> para ligar duas contas grandes). entao, C_n = C_0 *
> C_n-1 + C_1 * C_n-2 +
> ... + C_n-1 * C0  (q notacao horrivel!).
> Enfim, vc pediu uma dica neh :)
> Vc consegue achar uma equacao do segundo grau em
> F(x) e resolvendo e usando
> binomio de Newton vc encontra finalmente que o
> coeficiente de x_n eh sempre
> aquele numero la de cima.
> Tem um jeito de resolver esse problema sem usar
> funcoes geratrizes. Eu li
> uma vez no livro "Matematica Concreta", mas nao
> lembro agora como se faz...
> Abracos,
> Marcio
> 
> -----Mensagem original-----
> De: owner-obm-l@sucuri.mat.puc-rio.br
> [mailto:owner-obm-l@sucuri.mat.puc-rio.br]Em nome de
> Carlos Maçaranduba
> Enviada em: quarta-feira, 14 de novembro de 2001
> 17:44
> Para: obm-l@mat.puc-rio.br
> Assunto: problema
> 
> 
> Quem não conseguir fazer pelo menos diga uma
> idéia.Esta forma é a chamada forma infixa(forma no
> qual nós escrevemos) , mas existem as formas prefixa
> e
> posfixa(esta última usada em expressoes algébricas
> em
> compiladores pois se trata de uma forma mais
> eficiente
> de interpretar uma expressão algébrica).Depois digo
> como é a forma posfixa.Mas por favor tentem resolver
> essa questào para mim.
> 
> 
> Seja uma sequencia de operandos e operadores
> mostrados
> como abaixo:
> 
> A+B.C;
> 
> Separando por parenteses poderiamos obter duas
> expressões algébricas: (A+B).C ou A+(B.C);
> Repare que temos três operandos e dois
> operadores(multiplicação e soma).Dada uma sequencia
> de
> n operandos e n-1 operadores ,de quantas formas
> diferentes se pode formar expressões algébricas
> separadas por parenteses???
> 
> obs:Obviamente que a sequencia começa por um
> operando
> e termina com outro operando.
> 
>
____________________________________________________________________________
> ___________________
> Yahoo! GeoCities
> Tenha seu lugar na Web. Construa hoje mesmo sua home
> page no Yahoo!
> GeoCities. É fácil e grátis!
> http://br.geocities.yahoo.com/
>  

_______________________________________________________________________________________________
Yahoo! GeoCities
Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo! GeoCities. É fácil e grátis!
http://br.geocities.yahoo.com/