DemonstraçõesDemonstração - Primeiro Lema de Kaplansky

Fórum de coletânea das melhores demonstrações de teoremas de matemática.
Se você quiser postar uma demonstração aqui, poste, inicialmente, no fórum correspondente utilizando o título "Demonstração Teorema X" e substitua com o nome do teorema/fórmula que você postou e, depois, envie o link para um moderador pedindo para sua mensagem ser movida para o fórum "Demonstrações". Somente moderadores poderão mover sua mensagem para este fórum.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
MateusQqMD
5 - Mestre
Mensagens: 2693
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 21-02-24
Localização: Fortaleza/CE
Set 2019 07 21:51

Demonstração - Primeiro Lema de Kaplansky

Mensagem não lida por MateusQqMD »

O objetivo do tópico é fornecer uma redação que possa ajudar em alguns problemas de contagem que exigem que determinadas escolhas sejam feitas de maneira que não haja elementos consecutivos.

De acordo com o Primeiro Lema de Kaplansky, o número de subconjuntos com [tex3]p[/tex3] elementos de [tex3]\{1, \, 2, \, 3, \, ... \, n \}[/tex3] nos quais não há dois elementos consecutivos é

[tex3]\binom{n-p+1}{p}[/tex3]
Demonstração:

Inicialmente, vamos considerar o seguinte caso:

Exemplo 1. (Petrobras/2014) Três filmes devem ser estreados em dias diferentes de uma determinada semana (7 dias). De quantos modos é possível escolher os dias de exibição de forma que não haja filmes estreando em dias consecutivos?

Por exemplo, algumas respostas que satisfazem o pedido do enunciado são as seguintes:

[tex3]\{ \text{segunda}, \, \text{quinta}, \, \text{sábado} \}, [/tex3]

[tex3]\{ \text{domingo}, \, \text{terça}, \, \text{quinta}, \},[/tex3]

[tex3]\{ \text{quarta}, \, \text{sexta}, \, \text{domingo} \}.[/tex3]

Para responder esse problema, formaremos subconjuntos em que os dias escolhidos serão marcados com sinal [tex3](+)[/tex3] e os dias não escolhidos serão marcados com sinais [tex3](-)[/tex3] . Esquematizando os exemplos acima, temos (considerando o domingo como sendo o primeiro dia da semana):

[tex3]\{ \text{segunda}, \, \text{quinta}, \, \text{sábado} \} \quad [/tex3] pode ser representado por [tex3]\quad - + - - + - +[/tex3]

[tex3]\{ \text{domingo}, \, \text{terça}, \, \text{quinta}, \} \quad[/tex3] pode ser representado por [tex3]\quad + - + - + - -[/tex3]

[tex3]\{ \text{domingo}, \, \text{quarta}, \, \text{sexta} \} \quad [/tex3] pode ser representado por [tex3]\quad + - - + - + -[/tex3]

Agora, é fácil ver que para contarmos todas as soluções do problema basta descobrirmos de quantas maneiras podemos colocar [tex3]7[/tex3] sinais em fila, [tex3]3 \,\,(+)\,\, \text{e} \,\, 4 \,\, (-),[/tex3] de modo que [tex3]2[/tex3] sinais [tex3](+)[/tex3] não fiquem juntos. Para fazer isso, devemos arrumar os sinais [tex3](-)[/tex3] em fila ([tex3]1[/tex3] modo):

[tex3]\begin{array}{ccccccccc}
& -& & - & & - & & - & & \\
& & & & & & & & & & \\
\end{array}[/tex3]
De sorte que os espaços assinalados correspondem aos locais possíveis para o sinais [tex3](+):[/tex3]

[tex3]\begin{array}{ccccccccc}
& -& & - & & - & & - & & \\
1 & & 2 & & 3 & & 4 & & 5 & & \\
\end{array}[/tex3]

Há [tex3]C_5^3 = \frac{5!}{3!2!} = 10[/tex3] modos de escolher os lugares para os sinais [tex3](+).[/tex3] Depois disso, é possível arrumá-los de apenas [tex3]1[/tex3] modo, pois eles são iguais entre si. Portanto, podemos escolher de [tex3]10[/tex3] modos os dias de exibição dos filmes.


Para um caso genérico teremos [tex3]p[/tex3] sinais [tex3](+),[/tex3] [tex3]n-p[/tex3] sinais [tex3](-)[/tex3] e [tex3](n-p+1)[/tex3] espaços disponíveis para sem postos os sinais [tex3](+).[/tex3] Logo, é suficiente escolhermos [tex3](n-p+1)[/tex3] lugares para os [tex3]p[/tex3] sinais [tex3](+):[/tex3]

[tex3]f(n,p) = C^p_{n-p+1} = \binom{n-p+1}{p}[/tex3]

Referência: MORGADO, Augusto C,. Análise Combinatória e Probabilidade. Coleção do Professor de Matemática, 10ª Ed. - SBM.


Algumas questões:

viewtopic.php?t=74266

viewtopic.php?f=2&t=76134

viewtopic.php?t=69964

Última edição: csmarcelo (Qui 12 Set, 2019 09:52). Total de 1 vez.
Razão: correção do numerador do número binomial


"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."

Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5114
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 17-04-23
Set 2019 12 09:12

Re: Demonstração - Primeiro Lema de Kaplansky

Mensagem não lida por csmarcelo »

Não seria [tex3]C^p_{n-p+1} = \binom{n-p+1}{p}[/tex3] ?

Última edição: csmarcelo (Qui 12 Set, 2019 09:14). Total de 2 vezes.



Avatar do usuário
Autor do Tópico
MateusQqMD
5 - Mestre
Mensagens: 2693
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 21-02-24
Localização: Fortaleza/CE
Set 2019 12 09:47

Re: Demonstração - Primeiro Lema de Kaplansky

Mensagem não lida por MateusQqMD »

Sim.. escrevi uma passagem certa e acabei trocando o sinal. Como eu copiei o código, o erro da última linha acabou aparecendo também no início..

Agradeço se você corrigir, Marcelo (não tenho permissão para editar o tópico).


"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."

Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5114
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 17-04-23
Set 2019 12 09:55

Re: Demonstração - Primeiro Lema de Kaplansky

Mensagem não lida por csmarcelo »

Feito, MateusQqMD.




Movido de IME / ITA para Demonstrações em Ter 17 Set, 2019 12:33 por ALDRIN

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Demonstrações”