[obm-l] Combinatória e Formulas Fechadas

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Combinatória e Formulas Fechadas

Infelizmente, a belissima solucao do Shine nao funciona para todos os problemas desse tipo, e eu nao acredito que exista uma formula fechada para o problema geral.

No entanto, se voce soh ficar satisfeito com formulas fechadas, a matematica vai ser uma eterna fonte de insatisfacao. Exemplos disso sao o calculo de integrais indefinidas, a resolucao de equacoes diferenciais ou, em combinatoria, a determinacao do numero de maneiras de se distribuir os presentes num amigo oculto (amigo secreto em SP) com n pessoas de modo que ninguem de um presente para si mesmo nem haja uma troca mutua de presentes (ou seja, A presenteia B e B presenteia A). Em linguagem de gente grande, isso quer dizer numero de permutacoes de n elementos sem pontos fixos nem ciclos de ordem 2. Esse problema eh mencionado aqui na lista de tempos em tempos (normalmente pelo Rogerio Ponce), e nao se conhece uma formula fechada.
De uma olhada em: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A038205

Em combinatoria, a situacao piora ainda mais. Em boa parte dos problemas, nao temos sequer uma solucao na forma de funcoes geratrizes, como foi a minha, ou de uma soma de coeficientes binomiais, como foi a do Nicolau. Soh conhecemos alguma cota inferior ou superior para o numero desejado. Por exemplo, tome os numeros de Ramsey - objeto de um artigo na Eureka escrito pelo Gugu. Sobre estes numeros, Erdos uma vez disse: "se uma raca alienigena chegasse a Terra e ameacasse dizimar a raca humana a menos que, em 1 ano, determinassemos o valor de R(5,5), o melhor a fazer seria empregar todos os cerebros do planeta na resolucao desse problema. Por outro lado, se os alienigenas quisessem o valor de R(6,6), entao o melhor seria empregar todos os cerebros na criacao de armas que derrotassem os invasores".

Em suma, funcoes geratrizes nao sao tao ruins assim... 

[]s,
Claudio.

on 29.09.04 04:20, Faelccmm@aol.com at Faelccmm@aol.com wrote:

> Olá pessoal, 
>
> Agradeço a todos que tentaram responder e tiveram idéias bem criativas, mas faço das minhas palavras o que Domingos disse: "... é muito mais legal ter uma fórmula fechada! Será que existe? ..." 
>
> Acho até daria por achar esta fórmula por indução, mas o problema é como se dará a relação entre n, k, e b para estabelecermos a base da indução. Ex: 
>
> x[1] + x[2] + ... + x[n] = k (para algum b > 0 que será o limite máximo de quaisquer incógnitas) 
>
> Fazendo a base de indução em n 
>
> x[1] = 1 
> x[1] + x[2] = 1 
> x[1] + x[2] + x[3] = 1 
>
> (...) 
>
> Fazendo a base de indução em k 
>
> x[1] + x[2] = 1 
> x[1] + x[2] = 2 
> x[1] + x[2] = 3 
> x[1] + x[2] = 4 
>
> (...) 
>
> x[1] + x[2] + x[3] = 15 
>
> Para 
> b = 5 
> b = 6 
> b = 7 
> b = 8 
>
> (...) 
>
> É, meus amigos ! Achar uma fórmula fechada para isso é um quebra-cabeça e tanto ;-) ! 
>
>
>
> Em uma mensagem de 28/9/2004 17:12:42 Hora padrão leste da Am. Sul, dopikas@uol.com.br escreveu: 
>
>
> > A idéia de funções geradoras é legal, mas é muito mais legal ter uma 
> > fórmula fechada! Será que existe? E se formos menos ambiciosos e 
> > fixarmos um parâmetro (digamos os valores são dígitos e k e n são livres)? 
> >
> > [ ]'s 
> >
> > > Qual o coeficiente de t^27 no desenvolvimento de: 
> > > (1 + t + t^2 + t^3 + t^4 + t^5 + t^6 + t^7 + t^8 + t^9)^4 ? 
> > > Resposta (usando PARI-GP): 220. 
> > > 
> > > Minha pergunta pra voce: Por que isso tah certo?