Considere um time de atletismo que terminou a temporada com uma campanha de
vitórias e
derrotas. Gostaríamos de examinar de perto as séries de vitórias e derrotas na esperança de entender melhor as disputas das quais a equipe participou e investigar se existiram disputas nas quais seria mais provável a vitória. Por séries de vitórias, queremos dizer sequências consecutivas de vitórias. A título de exemplo se
e
e a sequência de resultados fosse
então haveria quatro séries de vitórias, a primeira delas de tamanho 2 , a segunda de tamanho 3 , a terceira de tamanho 1 e a quarta de tamanho 4.
Supondo que o time venha de uma campanha de
vitórias e
derrotas gostaríamos de saber de quantos modos podemos ter uma série de
vitórias.
Supondo que o time venha de uma campanha de
Passo 1
Beleza, a questão diz que a gente tem uma sequência de tamanho
, com
vitórias (V) e
derrotas (D), e quer saber de quantos jeitos aparece ao menos uma série de
vitórias seguidas. Isso é combinatória pura: vamos precisar de
- Representar essas sequências como uma distribuição de vitórias entre as derrotas (blank between Ds),
- Usar “estrelas e barras” (stars and bars) pra contar todas as sequências,
- E aplicar a técnica de inclusão–exclusão pra garantir que apareça pelo menos um bloco de
vitórias.
Passo 2
Primeiro, como a gente conta todas as sequências de
V e
D?
Pensa assim: coloca as derrotas no chão, isso cria
“lacunas” (antes da primeira D, entre as Ds, depois da última D). Nas lacunas a gente vai pôr as vitórias. Se
são quantas vitórias vão em cada lacuna, então
Pensa assim: coloca as
com
. O número de soluções não-negativas dessa equação é, pelo stars and bars,
Então o total de sequências é
.
Passo 3
Agora, a gente quer só aquelas que têm pelo menos uma lacuna com
, ou seja, uma série de
vitórias seguidas. Em vez de contar direto, a gente vê o complementar: quantas soluções têm todas as
?
Para soluções com teto
em cada
, usamos inclusão–exclusão:
- Sem restrição de teto, já sabemos que são
. - Escolhe
lacunas onde “quebramos” a condição de . Há maneiras de escolher essas lacunas. - Em cada uma dessas lacunas forçamos que tenha pelo menos
vitórias: então já reservamos vitórias, sobrando distribuir vitórias livremente pelas lacunas (agora sem teto). O número de soluções para isso é
- Pelo princípio da inclusão–exclusão, o total de sequências sem nenhuma lacuna com
é
Passo 4
Finalmente, o número de sequências que têm ao menos uma série de
vitórias é
Isso vem de subtrair o complementar do total, ou seja
e reorganizar os termos.
e reorganizar os termos.
Resposta
O número de sequências de
vitórias e
derrotas que contêm pelo menos uma série de
vitórias seguidas é