• Anúncio Global
    Respostas
    Exibições
    Última mensagem

[Análise combinatória] dúvida

[Análise combinatória] dúvida

Mensagempor Tiego » Qua Mai 09, 2012 10:32

Olá pessoal, estou com dúvida na seguinte questão:

Utilizando um argumento combinatório, mostre que

Cn,k= Cn-1,k-1 + Cn-1,k

Dica: fixe um elemento do conjunto, e conte o total de subconjuntos de tamanho k que contém o elemento e o total de subconjuntos de tamanho k que não o contém.

R.: Eu mostrei usando valores numéricos mas não sei se pode ser assim:

C5,2 = C4,1 + C4,2

C5,2 = 5!/(3!.2!) = 10
C4,1 = 4!/(3!.1!) = 4
C4,2 = 4!/(2!.2!)= 6

Portanto: Cn,k= Cn-1,k-1 + Cn-1,k

será que está correto?
Tiego
Novo Usuário
Novo Usuário
 
Mensagens: 4
Registrado em: Ter Mai 08, 2012 23:48
Formação Escolar: GRADUAÇÃO
Área/Curso: licenciatura em matemática
Andamento: formado

Re: [Análise combinatória] dúvida

Mensagempor fraol » Qui Mai 10, 2012 22:41

Creio que a resposta que se quer para esse problema deva ser genérica, isto é deve-se usar argumentos genéricos e não um exemplo específico que é o que você apresentou. Assim uma possível resposta poderia ser a seguinte:


Utilizando um argumento combinatório, mostre que

Cn,k= Cn-1,k-1 + Cn-1,k

Dica: fixe um elemento do conjunto, e conte o total de subconjuntos de tamanho k que contém o elemento e o total de subconjuntos de tamanho k que não o contém.



C_{n,k} representa o número de subconjuntos distintos contendo k elementos de um total de n elementos.

Vamos fixar um elemento x dentre os n elementos.

O número de subconjuntos de k elementos em que x não aparece é igual a C_{n-1, k} ( veja que subtraímos 1 do total n pois é como-se combinássemos o conjunto sem o x ).

O número de subconjuntos de k elementos em que o x aparece é igual a C_{n-1, k-1} ( veja que subtraímos 1 do total n e do total de k pois como o x sempre aparece então restam n-1 elementos para serem combinados em subconjuntos de k-1 elementos cada ).

Em suma, o total de subconjuntos contendo k elementos é igual ao total de subconjuntos que não possuem um certo elemento somado com o total de subconjuntos que possuem esse certo elemento, isto é:

C_{n,k} = C_{n-1, k} + C_{n-1, k-1} .


.
fraol
Colaborador Voluntário
Colaborador Voluntário
 
Mensagens: 392
Registrado em: Dom Dez 11, 2011 20:08
Localização: Mogi das Cruzes-SP
Formação Escolar: GRADUAÇÃO
Área/Curso: Matemática
Andamento: formado

Re: [Análise combinatória] dúvida

Mensagempor joaofonseca » Qui Mai 17, 2012 08:32

Existe uma propriedade do triangulo de pascal que afirma:

\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}

A soma de dois termos consecutivos da mesma linha, k-1 e k respetivamente, é igual ao termo de ordem k da linha seguinte (n+1).

Seja n=p-1, logo:

\binom{p-1}{k}+\binom{p-1}{k-1}=\binom{p-1+1}{k}

\binom{p-1}{k}+\binom{p-1}{k-1}=\binom{p}{k}
joaofonseca
Colaborador Voluntário
Colaborador Voluntário
 
Mensagens: 196
Registrado em: Sáb Abr 30, 2011 12:25
Localização: Lisboa
Formação Escolar: GRADUAÇÃO
Área/Curso: Matemática
Andamento: cursando


Voltar para Estatística

 



  • Tópicos relacionados
    Respostas
    Exibições
    Última mensagem

Quem está online

Usuários navegando neste fórum: Nenhum usuário registrado e 14 visitantes

 



Assunto: (FGV) ... função novamente rs
Autor: my2009 - Qua Dez 08, 2010 21:48

Uma função polinomial f do 1° grau é tal que f(3) = 6 e f(4) = 8.Portanto o valor de f(10) é :


Assunto: (FGV) ... função novamente rs
Autor: Anonymous - Qui Dez 09, 2010 17:25

Uma função de 1º grau é dada por y=ax+b.
Temos que para x=3, y=6 e para x=4, y=8.
\begin{cases}6=3a+b\\8=4a+b\end{cases}
Ache o valor de a e b, monte a função e substitua x por 10.


Assunto: (FGV) ... função novamente rs
Autor: Pinho - Qui Dez 16, 2010 13:57

my2009 escreveu:Uma função polinomial f do 1° grau é tal que f(3) = 6 e f(4) = 8.Portanto o valor de f(10) é :



f(x)= 2.x
f(3)=2.3=6
f(4)=2.4=8
f(10)=2.10=20


Assunto: (FGV) ... função novamente rs
Autor: dagoth - Sex Dez 17, 2010 11:55

isso ai foi uma questao da FGV?

haahua to precisando trocar de faculdade.


Assunto: (FGV) ... função novamente rs
Autor: Thiago 86 - Qua Mar 06, 2013 23:11

Saudações! :-D
ví suaquestão e tentei resolver, depois você conta-me se eu acertei.
Uma função de 1º grau é dada por y=3a+b

Resposta :
3a+b=6 x(4)
4a+b=8 x(-3)
12a+4b=24
-12a-3b=-24
b=0
substituindo b na 1°, ttenho que: 3a+b=6
3a+0=6
a=2
substituindo em: y=3a+b
y=30+0
y=30
:coffee: