Re: [obm-l] Problema Combinatória

["Ralph Teixeira" <ralphct@xxxxxxxxx>]

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 <peterdirichlet2003@xxxxxxxxx>:
> 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<mauz.matematica@xxxxxxxxx> 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
=========================================================================