- Suponha que
carros estão em fila para entrar em um estacionamento que possui
vagas, lado a lado. Se o
carro pode escolher qualquer vaga e cada um dos outros carros ao estacionar deve justapor-se a um carro já estacionado, quantos são os modos possíveis dos carros ocuparem as
vagas?
- De quantos modos 15 jogadores podem ser divididos em 3 times de basquetebol de 5 jogadores cada, denominados Esperança, Confiança e Vitória?
Passo 1
Questão
: temos
carros em fila (carros numerados por ordem de chegada:
) e
vagas em linha, lado a lado. O enunciado diz: o
carro pode escolher qualquer vaga; cada um dos outros carros, quando for estacionar, deve justapor‑se (ou seja, ocupar uma vaga imediatamente à esquerda ou à direita) a um carro já estacionado. A pergunta é: de quantos modos possíveis os carros podem ocupar as
vagas, isto é, de quantas formas finais (associação carro ↔ vaga) obedecendo a essa regra existem?
Questão
: temos
jogadores e queremos dividi‑los em
times de basquetebol, cada time com
jogadores, sendo os times denominados (isto é, os times são distintos: Esperança, Confiança e Vitória). A pergunta é: de quantos modos podemos formar esses três times (considerando que a ordem dentro de cada time não importa, só quem pertence a qual time)?
Passo 2
Vamos atacar a Questão
. Primeiro, vou traduzir a regra para algo mais manejável: ao longo do processo de entrada, os carros sempre formam um “bloco” contíguo de vagas ocupadas — porquê? porque o primeiro carro ocupa uma vaga isolada e todo carro seguinte tem que estacionar em uma vaga imediatamente adjacente a alguma vaga já ocupada; isso faz com que as vagas ocupadas nunca fiquem com buracos no meio: o conjunto ocupado é sempre um intervalo contíguo na reta das vagas. É importante entender bem esse ponto antes de contar.
Passo 3
Vamos ver exemplos pequenos para sentir o padrão.
-
Para
: só existe uma vaga e um carro; modos possíveis . -
Para
: o carro escolhe uma das vagas; o carro tem uma única vaga adjacente restante. Modos possíveis . -
Para
: considere as três vagas numeradas da esquerda para a direita. Se o carro escolhe a vaga do meio, o carro pode escolher esquerda ou direita (2 opções) e o fica na última vaga; se o carro escolhe uma das vagas de extremidade, as escolhas são forçadas. Contando todos os casos obtemos modos. Observe a sequência para — já dá pista de uma potência de .
Passo 4
Intuição do procedimento: cada carro, no momento em que entra, estaciona numa das duas extremidades do bloco já existente (extremidade esquerda ou extremidade direita). Quando um carro estaciona numa extremidade, ele pode depois deixar essa extremidade disponível para que outro carro venha colar mais para o lado (ou não). Um ponto-chave para contar é ver que, no final, se removermos os carros na ordem inversa (isto é, começamos tirando o último carro que entrou e vamos voltando até o primeiro), em cada etapa o carro removido estará numa extremidade do bloco atual — por quê? porque quando o carro entrou, ele entrou numa extremidade do bloco existente; removendo carros em ordem inversa garantimos que o carro que entrou por último continua sendo uma extremidade (não existem carros posteriores que o tenham envolvido), e assim sucessivamente. Isso garante uma correspondência entre cada configuração final e uma sequência de escolhas “esquerda/direita” feitas nos
momentos em que os carros
entraram.
Passo 5
Formalizando a correspondência (bastante usada em combinatória para esse tipo de problema): para cada configuração final válida podemos reconstruir unicamente, lendo os carros da última entrada para a primeira, uma sequência de escolhas onde cada entrada (exceto a primeira) foi feita numa das duas extremidades; essa sequência tem comprimento
e cada termo é “L” (esquerda) ou “R” (direita). A reconstrução é única porque, na etapa de remoção inversa, o carro a ser removido tem que estar numa extremidade — então sabemos se, no momento em que entrou, ele escolheu a extremidade esquerda ou a direita do bloco. Assim existe uma bijeção entre:
- configurações finais válidas, e
- sequências de
escolhas binárias (L ou R).
Passo 6
Contagem: o número de sequências binárias de comprimento
é
. Pela bijeção do passo anterior, o número de configurações finais (isto é, modos possíveis dos carros ocuparem as
vagas seguindo a regra) é exatamente
Vou reforçar a ideia com uma lembrete intuitivo: o primeiro carro não tem “lado” a escolher (é o primeiro), e cada dos
carros seguintes, ao entrar, efetivamente escolhe um dos dois lados do bloco já existente — por isso a potência de
.
Passo 7
Agora a Questão
. Vou explicitar o modelo: temos um conjunto de
jogadores distintos. Queremos formar três times distintos (nomes diferentes), cada time com exatamente
jogadores. Dentro de cada time a ordem não importa — só importa quem está no time.
Passo 8
Método direto (sequencial com binomiais): primeiro escolho os
jogadores que irão para o time Esperança. O número de escolhas para isso é
Depois, dos
jogadores restantes, escolho os
que irão para o time Confiança:
Os
restantes irão automaticamente para o time Vitória:
Pelo princípio multiplicativo, o total de divisões é
Passo 9
Simplificação usando fatoriais (fórmula do binomial): lembrando que
multiplicando obtemos
Observação rápida: se os times não fossem denominados (ou seja, se fossem indistintos), teríamos que dividir ainda por
porque permutar os nomes dos três times não mudaria a divisão. Mas aqui os times têm nomes (Esperança, Confiança e Vitória), então não dividimos por
.
Passo 10
Recapitulando de forma bem direta: para
a contagem é feita pela correspondência com sequências de decisões “esquerda/direita” de comprimento
e dá
. Para
usamos escolhas sucessivas com coeficientes binomiais e obtemos
.