Seja G(m,n) o número de maneiras de escolher m livros não consecutivos a partir de um conjunto com n livros (supomos que eles são todos diferentes e estão em fila na estante). onde m,n>=1.
Condições de contorno: G(1,n)=n (pois há n maneiras de escolher 1 livro dentre n deles); por outro lado, para m>1, temos G(m,1)=G(m,2)=0 (não dá para escolher 2 ou mais livros não-consecutivos num conjunto com apenas 1 ou 2 livros). A partir daí, tenho uma recorrência: para escolher m livros de n, você tem duas opções: a) Incluir o livro 1; então você não pode incluir o livro 2, e, assim, ainda tem que escolher m-1 dos n-2 livros restantes. Assim, há aqui G(m-1,n-2) maneiras de fazer isto. b) Não incluir o livro 1; então você tem que escolher m dos n-1 restantes; há G(m,n-1) maneiras de fazer isto. Como as maneiras em (a) e (b) são disjuntas, temos a recorrência: G(m,n)=G(m,n-1)+G(m-1,n-2) Então juntando tudo: G(m,n)=G(m,n-1)+G(m-1,n-2) para m>=2 e n>=3 G(1,n)=n para n>=1 G(m,1)=G(m,2)=0 para m>=1 Bom, joguei isto no Calc do OpenOffice... e estou vendo uma espécie de Triângulo de Pascal deformado... Hmmmm... Ah, já sei. Seja f(x,y)=G(m,n) onde m=x-y e n=2x-y-1 (ou, se você preferir, x=n-m+1 e y=n-2m+1). A recorrência e as condiçõaes de contorno acima tranformam-se em condições em f que são idênticas àquelas que definem o triângulo de Pascal, isto é, f(x,y)=C(x,y). Então a resposta é que G(m,n)=C(n-m+1,n-2m+1). Ou, se você preferir, mostre por indução que esta última fórmula vale... Desculpa o final curto e meio grosso, mas acabou meu tempo. :) Eu ainda queria ver se tinha alguma solução verdadeiramente combinatória que levasse à reposta, mas fica para depois. Ah, e, se eu não errei nada, a resposta à pergunta original é G(5,24)=C(20,15)=15504 -- há 15504 maneiras de escolher 5 livros não consecutivos a partir de uma fila com 24. Perdão, sem tempo de checar tudo, espero não ter escrito besteiras homéricas. Abraço, Ralph 2008/3/27 Johann Peter Gustav Lejeune Dirichlet <[EMAIL PROTECTED]>: > São 24 livros de assuntos distintos? E os livros estão grudados na > estante (se o de Teoria da Computação está do lado de Linguagens > Formais, eles sempre estarão lado a lado?) > Bem, seria algo como escolher cinco números não-consecutivos do conjunto > {1,2,3,4\ldots,24}. > Acho que dá pra usar alguma recursão. > Vou pensar um pouco antes de continuar... > > Em 26/03/08, MauZ<[EMAIL PROTECTED]> escreveu: > > Olá a todos! > > > > Numa estante com 24 livros, de quantas maneiras posso retirar 5 livros sem > > ter nenhum consecutivo? E no caso de n livros, quantas maneiras retiro p > > livros sem ter nenhum consecutivo? > > > > > > > > Pra completar vou colocar parte da minha tentativa de solução, preciso de > > ajuda pra saber se está certo até onde fiz e como finalizar pois empaquei. > > > > Fiz dessa forma: Todas Combinações - Combinações c/ Consecutivos > > > > Todas: 24!/5!19! > > Consecutivos: 23!/4!19! + 22!/3!19! + 21!/2!19! + 20!/1!19! > > > > Fiz uma formula geral com n e p e deu o seguinte: > > > > n!/p!(n-p!) - [(n-1)!/(p-1)!(n-p)! + > > (n-2)!/(p-2)!(n-p)!+...+(n-p+1)!/(n-p)!] > > > > Fatorando deu: > > > > (1/(n-p)!)[n!/p!-(n-1)!/(p-1)!-(n-2)!/(p-2)-...-(n-p+1)!/(n-p)!] > > > > Dae empaquei de vez... Não consegui continuar! > > Quem souber fazer por favor me dê a luz! Ou simplesmente indique o erro no > > meu raciocínio. > > > > Agradeço antecipadamente, > > Maurizio > > > > > > > -- > Ideas are bulletproof. > > V > > ========================================================================= > 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 =========================================================================