Fernanda quer fazer un colar usando 8 contas vernelhas indistinguiveis e 32 contas azuis indistinguíveis de modo que haja pelo menos 2 contas azuis entre quaisquer 2 contas vermelhas. De quantas maneiras isto pode ser feito?
Passo 1
O enunciado pede o número de sequências lineares formadas por
contas vermelhas idênticas e
contas azuis idênticas de modo que entre quaisquer duas vermelhas haja pelo menos
azuis. O conteúdo principal aqui é usar a técnica de “stars and bars” (distribuição de bolas em caixas) para modelar as lacunas de contas azuis entre as vermelhas.
Passo 2
Vamos pensar na montagem como uma sequência com
vermelhas e
azuis. Entre cada par de vermelhas internas precisamos de pelo menos
azuis, mas nas extremidades (antes da primeira vermelha e depois da última) não há restrição mínima. Definimos:
número de azuis antes da
ª vermelha,
número de azuis após a
ª vermelha,
número de azuis entre a
-ésima e a
-ésima vermelhas, para
.
A condição “pelo menos
azuis” vale apenas para
, ou seja
e
com
Passo 3
Para eliminar a condição “
” nas variáveis
, fazemos a troca
de modo que
. Então
e a soma total vira
Passo 4
Agora temos
variáveis não negativas
somando
. Pelo teorema de stars and bars, o número de soluções inteiras não negativas de
é