Demonstração - Primeiro Lema de Kaplansky
Enviado: Sáb 07 Set, 2019 21:51
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 é
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):
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]
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
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]
& -& & - & & - & & - & & \\
& & & & & & & & & & \\
\end{array}[/tex3]
[tex3]\begin{array}{ccccccccc}
& -& & - & & - & & - & & \\
1 & & 2 & & 3 & & 4 & & 5 & & \\
\end{array}[/tex3]
& -& & - & & - & & - & & \\
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