Re: RES: [obm-l] Problema Subconjuntos
Olá Artur!!!
O 1° lema de Kaplansky diz que o número de p-subconjuntos (isto é, um
subconjunto com p elementos) de {1,2,...,n} nos quais não há números
consecutivos é:
f (n,p) = Combinação(n-p+1,p).
Para maiores detalhes consulte Análise Combinatória e Probabilidade de
Morgado, Pitombeira, P.C.Pinto Carvalho e Pedro Fernandez, da coleção do
Professor de Matemática.
Espero ter ajudado,um grande abraço,
Poncio
- Original Message -
From: Artur Costa Steiner <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Wednesday, July 21, 2004 8:14 PM
Subject: Re: RES: [obm-l] Problema Subconjuntos
> >C(n-2;3). Basta usar o primeiro lema de Kaplansky.
>
> Eu nunca ouvi falar deste lema (ignorancia minha). Alguem poderia
> enuncia-lo?
> Obrigado.
> Artur
>
>
> OPEN Internet
> @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @
>
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> =
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
Re: RES: [obm-l] Problema Subconjuntos
achei isso no arquivo da lista:
Kaplansky.
Primeiro lema:
O número de subconjuntos de tamanho p do conjunto {1,
2,..., n} no qual nao figuram numeros consecutivos eh
C(n-p+1, p)
Segundo lema:
Igual ao anterior, mas considerando 1 e n como
consecutivos. O numero de subconjuntos eh
[n/(n-p)]*C(n-p, p).
--- Artur Costa Steiner <[EMAIL PROTECTED]>
escreveu: > >C(n-2;3). Basta usar o primeiro lema de
Kaplansky.
>
> Eu nunca ouvi falar deste lema (ignorancia minha).
> Alguem poderia
> enuncia-lo?
> Obrigado.
> Artur
___
Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis!
http://br.info.mail.yahoo.com/
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
Re: RES: [obm-l] Problema Subconjuntos
>C(n-2;3). Basta usar o primeiro lema de Kaplansky. Eu nunca ouvi falar deste lema (ignorancia minha). Alguem poderia enuncia-lo? Obrigado. Artur OPEN Internet @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: RES: [obm-l] Problema Subconjuntos
Eh, eu fiz uma confusao ali
imagine que temos os subconjnutos de {1, 2, ..., n-3}
e
queremos adicionar os elementos n-1 e n-2 a esses
subconjuntos ao mesmo tempo, nesse caso só nao
poderemos adicionar n-1 e n-2 aos subconjuntos que tem
o elemento n-3,
entao teremos T[n-3] - T[n-4] subconjuntos com os
elementos n-1 e n-2:
X = T[n-3] - T[n-4]
T[n-3] - T[n-4] eh o numero de subconjuntos que tem o
elemento n-3. podemos adicionar n-1 e n-2 a todos os
outros subconjuntos, entao podemos adicionar n-1 e n-2
a T[n-3] - (T[n-3] - T[n-4]) = T[n-4]
entao X = T[n-4]
e T[n] = 2*T[n-1] - T[n-4]
--- "David M. Cardoso" <[EMAIL PROTECTED]>
escreveu: >
> Cara, muito obrigado..
> Sendo que ta dando trabalho pra eu entender algumas
> coisas,
> como "teremos T[n-3] - T[n-4] subconjuntos com os
> elementos n-1 e n-2"..
> hora eu penso que entendi, hora eu não entendo mais
> e fico tentando lembrar
> pq eu fico entendido antes, talvez seja o
> nervosismo, talvez seja apenas
> porque o raciocinio eh complicado demais pra mim..
>
> Outra duvida que tenho é se é possível transformar a
> recorrência num
> "polinomiozinho" em função de n ou se uma resposta
> desse tipo já esta
> completa o suficiente..
>
> []'s
> David
>
> > -Mensagem original-
> > De: [EMAIL PROTECTED]
> > [mailto:[EMAIL PROTECTED] Em nome de
> Helder Suzuki
> > Enviada em: terça-feira, 20 de julho de 2004 19:30
> > Para: [EMAIL PROTECTED]
> > Assunto: Re: [obm-l] Problema Subconjuntos
> >
> > vamos ver, seguindo a dica de usar recorrencia
> >
> > se T[n] for igual ao numero de subconjuntos do
> conjunto {1,
> > 2, ..., n} que nao contem 3 inteiros consecutivos.
> > temos que:
> > T[0] = 1
> > {}
> >
> > T[1] = 2
> > {} e {1}
> >
> > T[2] = 4
> > {}, {1},
> > {2} e {1, 2}
> >
> > T[3] = 7
> > {}, {1}, {2}, {1, 2},
> > {3}, {1, 3}, {2, 3}
> >
> > T[4] = 13
> > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4},
> {1, 4}, {2,
> > 4}, {3, 4}, {1, 2, 4}, {1, 3, 4}
> >
> > bom, suponha que sabemos o valor de T[n-1],
> T[n-2], ...,
> > T[1]; como podemos achar T[n] em funcao de T[n-1]?
> humm...
> > considere todos subconjuntos de {1, 2, 3, 4, ...,
> n-1} que
> > satisfazem a condicao do enunciado.
> > se adicionarmos um elemento n, em quais desses
> subconjuntos o
> > n pode entrar e quais ele nao pode(para manter a
> condicao do
> > enunciado)?
> > se n nao pode entrar em X subconjuntos, temos que
> T[n] =
> > T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o
> numero de
> > subconjuntos que tem os elementos
> > n-1 e n-2.
> >
> > imagine que temos os subconjnutos de {1, 2, ...,
> n-3} e
> > queremos adicionar os elementos n-1 e n-2 a esses
> > subconjuntos ao mesmo tempo, nesse caso só nao
> poderemos
> > adicionar n-1 e n-2 aos subconjuntos que tem o
> elemento n-3,
> > entao teremos T[n-3] - T[n-4] subconjuntos com os
> elementos n-1 e n-2:
> > X = T[n-3] - T[n-4]
> >
> > entao nossa recorrencia fica:
> > T[n] = 2*T[n-1] - T[n-3] + T[n-4]
> >
> > []'s,
> > Helder
> >
> > --- "David M. Cardoso" <[EMAIL PROTECTED]>
> > escreveu: >
> > >
> > > Olá,
> > >
> > > Alguem pode me ajudar? Não consegui resolver o
> seguinte problema:
> > >
> > > "Quantos subconjuntos o conjunto {1,2,3,...,n}
> tais que não contêm
> > > três inteiros consecutivos?"
> > >
> > > A dica dada na questão é: "Encontre uma
> recorrência."
> > Porém, qualquer
> > > solução (sem/com recorrência) vai ajudar.
> > >
> > > []'s
> > > David
> >
> >
> >
> >
> >
> >
>
___
> > Yahoo! Mail agora com 100MB, anti-spam e antivírus
> grátis!
> > http://br.info.mail.yahoo.com/
> >
>
==
> > ===
> > Instruções para entrar na lista, sair da lista e
> usar a lista
> > em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> >
>
==
> > ===
> >
>
>
>
=
> Instruções para entrar na lista, sair da lista e
> usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>
=
> bm-l.html
>
=
>
___
Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis!
http://br.info.mail.yahoo.com/
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
Re: RES: [obm-l] Problema Subconjuntos
C(n-2;3). Basta usar o primeiro lema de Kaplansky.
==
Mensagem enviada pelo CIP WebMAIL - Nova Geração - v. 2.1
CentroIn Internet Provider http://www.centroin.com.br
Tel: (21) 2542-4849, (21) 2295-3331Fax: (21) 2295-2978
Empresa 100% Brasileira - Desde 1992 prestando servicos online
-- Original Message ---
From: "David M. Cardoso" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Tue, 20 Jul 2004 20:57:24 -0300
Subject: RES: [obm-l] Problema Subconjuntos
> Cara, muito obrigado..
> Sendo que ta dando trabalho pra eu entender algumas coisas,
> como "teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2"..
> hora eu penso que entendi, hora eu não entendo mais e fico tentando lembrar
> pq eu fico entendido antes, talvez seja o nervosismo, talvez seja apenas
> porque o raciocinio eh complicado demais pra mim..
>
> Outra duvida que tenho é se é possível transformar a recorrência num
> "polinomiozinho" em função de n ou se uma resposta desse tipo já esta
> completa o suficiente..
>
> []'s
> David
>
> > -Mensagem original-
> > De: [EMAIL PROTECTED]
> > [mailto:[EMAIL PROTECTED] Em nome de Helder Suzuki
> > Enviada em: terça-feira, 20 de julho de 2004 19:30
> > Para: [EMAIL PROTECTED]
> > Assunto: Re: [obm-l] Problema Subconjuntos
> >
> > vamos ver, seguindo a dica de usar recorrencia
> >
> > se T[n] for igual ao numero de subconjuntos do conjunto {1,
> > 2, ..., n} que nao contem 3 inteiros consecutivos.
> > temos que:
> > T[0] = 1
> > {}
> >
> > T[1] = 2
> > {} e {1}
> >
> > T[2] = 4
> > {}, {1},
> > {2} e {1, 2}
> >
> > T[3] = 7
> > {}, {1}, {2}, {1, 2},
> > {3}, {1, 3}, {2, 3}
> >
> > T[4] = 13
> > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4}, {1, 4}, {2,
> > 4}, {3, 4}, {1, 2, 4}, {1, 3, 4}
> >
> > bom, suponha que sabemos o valor de T[n-1], T[n-2], ...,
> > T[1]; como podemos achar T[n] em funcao de T[n-1]? humm...
> > considere todos subconjuntos de {1, 2, 3, 4, ..., n-1} que
> > satisfazem a condicao do enunciado.
> > se adicionarmos um elemento n, em quais desses subconjuntos o
> > n pode entrar e quais ele nao pode(para manter a condicao do
> > enunciado)?
> > se n nao pode entrar em X subconjuntos, temos que T[n] =
> > T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o numero de
> > subconjuntos que tem os elementos
> > n-1 e n-2.
> >
> > imagine que temos os subconjnutos de {1, 2, ..., n-3} e
> > queremos adicionar os elementos n-1 e n-2 a esses
> > subconjuntos ao mesmo tempo, nesse caso só nao poderemos
> > adicionar n-1 e n-2 aos subconjuntos que tem o elemento n-3,
> > entao teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2:
> > X = T[n-3] - T[n-4]
> >
> > entao nossa recorrencia fica:
> > T[n] = 2*T[n-1] - T[n-3] + T[n-4]
> >
> > []'s,
> > Helder
> >
> > --- "David M. Cardoso" <[EMAIL PROTECTED]>
> > escreveu: >
> > >
> > > Olá,
> > >
> > > Alguem pode me ajudar? Não consegui resolver o seguinte problema:
> > >
> > > "Quantos subconjuntos o conjunto {1,2,3,...,n} tais que não contêm
> > > três inteiros consecutivos?"
> > >
> > > A dica dada na questão é: "Encontre uma recorrência."
> > Porém, qualquer
> > > solução (sem/com recorrência) vai ajudar.
> > >
> > > []'s
> > > David
> >
> >
> >
> >
> >
> > ___
> > Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis!
> > http://br.info.mail.yahoo.com/
> > ==
> > ===
> > Instruções para entrar na lista, sair da lista e usar a lista
> > em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> > ==
> > ===
> >
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> =
--- End of Original Message ---
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
RES: [obm-l] Problema Subconjuntos
Cara, muito obrigado..
Sendo que ta dando trabalho pra eu entender algumas coisas,
como "teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2"..
hora eu penso que entendi, hora eu não entendo mais e fico tentando lembrar
pq eu fico entendido antes, talvez seja o nervosismo, talvez seja apenas
porque o raciocinio eh complicado demais pra mim..
Outra duvida que tenho é se é possível transformar a recorrência num
"polinomiozinho" em função de n ou se uma resposta desse tipo já esta
completa o suficiente..
[]'s
David
> -Mensagem original-
> De: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] Em nome de Helder Suzuki
> Enviada em: terça-feira, 20 de julho de 2004 19:30
> Para: [EMAIL PROTECTED]
> Assunto: Re: [obm-l] Problema Subconjuntos
>
> vamos ver, seguindo a dica de usar recorrencia
>
> se T[n] for igual ao numero de subconjuntos do conjunto {1,
> 2, ..., n} que nao contem 3 inteiros consecutivos.
> temos que:
> T[0] = 1
> {}
>
> T[1] = 2
> {} e {1}
>
> T[2] = 4
> {}, {1},
> {2} e {1, 2}
>
> T[3] = 7
> {}, {1}, {2}, {1, 2},
> {3}, {1, 3}, {2, 3}
>
> T[4] = 13
> {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4}, {1, 4}, {2,
> 4}, {3, 4}, {1, 2, 4}, {1, 3, 4}
>
> bom, suponha que sabemos o valor de T[n-1], T[n-2], ...,
> T[1]; como podemos achar T[n] em funcao de T[n-1]? humm...
> considere todos subconjuntos de {1, 2, 3, 4, ..., n-1} que
> satisfazem a condicao do enunciado.
> se adicionarmos um elemento n, em quais desses subconjuntos o
> n pode entrar e quais ele nao pode(para manter a condicao do
> enunciado)?
> se n nao pode entrar em X subconjuntos, temos que T[n] =
> T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o numero de
> subconjuntos que tem os elementos
> n-1 e n-2.
>
> imagine que temos os subconjnutos de {1, 2, ..., n-3} e
> queremos adicionar os elementos n-1 e n-2 a esses
> subconjuntos ao mesmo tempo, nesse caso só nao poderemos
> adicionar n-1 e n-2 aos subconjuntos que tem o elemento n-3,
> entao teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2:
> X = T[n-3] - T[n-4]
>
> entao nossa recorrencia fica:
> T[n] = 2*T[n-1] - T[n-3] + T[n-4]
>
> []'s,
> Helder
>
> --- "David M. Cardoso" <[EMAIL PROTECTED]>
> escreveu: >
> >
> > Olá,
> >
> > Alguem pode me ajudar? Não consegui resolver o seguinte problema:
> >
> > "Quantos subconjuntos o conjunto {1,2,3,...,n} tais que não contêm
> > três inteiros consecutivos?"
> >
> > A dica dada na questão é: "Encontre uma recorrência."
> Porém, qualquer
> > solução (sem/com recorrência) vai ajudar.
> >
> > []'s
> > David
>
>
>
>
>
> ___
> Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis!
> http://br.info.mail.yahoo.com/
> ==
> ===
> Instruções para entrar na lista, sair da lista e usar a lista
> em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> ==
> ===
>
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
