Considere um time de atletismo que terminou a temporada com uma campanha de n vitórias e m 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 n=10 e m=6 e a sequência de resultados fosse
V V D D V V V D V D D D V V V V
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 n vitórias e m derrotas gostaríamos de saber de quantos modos podemos ter uma série de r vitórias.

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 X0 + X1 + cdots + Xm = n, V e binomn + (m+1) -1(m+1)-1 =binomn+mm =binomn+mn 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
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 sumj=0^lfloor n/rrfloor(-1)^j binomm+1j binomn - jr + mm , 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:
  1. Sem restrição de teto, já sabemos que são .
  2. Escolhe lacunas onde “quebramos” a condição de . Há maneiras de escolher essas lacunas.
  3. 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 é
  4. 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 boxed sumj=1^lfloor n/rrfloor(-1)^,j-1, binomm+1j, binomn - j,r + mm vitórias é
Isso vem de subtrair o complementar do total, ou seja

e reorganizar os termos.

Resposta

O número de sequências de sumj=1^lfloor n/rrfloor(-1)^,j-1, binomm+1j, binomn - j,r + mm vitórias e derrotas que contêm pelo menos uma série de vitórias seguidas é

Exercícios relacionados