Fiz mais um pequeno progresso. Resolvi um sub-problema. De quantas formas é possível colocar 15 As nas 60 posições de modo que 2 As não ocupem posições adjacentes.
Há 4 casos (exaustivos e mutuamente exclusivos) a considerar: 1) A primeira e a última posição são ocupadas por As: Nesse caso, uma vez colocados todos os As, sobrarão, entre eles, 14 "espaços" com comprimentos variados. Chamando de x(k) o comprimento do k-ésimo espaço, teremos as condições: x(k) >= 1, para 1 <= k <= 14. e x(1) + x(2) + ... + x(14) = 45 (*) Logo, o número de maneiras de colocar os As neste caso é igual ao número de soluções inteiras positivas de (*): C(44,13) 2) Um A ocupa a primeira posição mas a última posição está vazia. A equação, neste caso, é: x(1) + x(2) + ... + x(15) = 45 com todos os x(k) >= 1 ==> C(44,14). 3) Um A ocupa a última posição mas a primeira está vazia: Por simetria, C(44,14) 4) A primeira e a última posições estão vazias: A equação é x(1) + ... + x(16) = 45 (x(k) >= 1) ==> C(44,15). Logo, o número de maneiras de colocar 15 As em 60 posições de modo que não fiquem dois As adjacentes é igual a: C(44,13) + 2*C(44,14) + C(44,15) Infelizmente, isso abre um monte de sub-casos chatos pra colocação dos Bs, de modo que não sei se é um caminho promissor. Provavelmente não. []s, Claudio. On Tue, Nov 6, 2018 at 4:01 PM Claudio Buffara <claudio.buff...@gmail.com> wrote: > O número de casos possíveis é C(60,15)*C(45,15)*C(30,15)*C(15,15) = > 60!/(15!)^4 > (das 60 posições da sequencia, escolhe 15 para colocar os As; das 45 > restantes, escolhe mais 15 pra colocar os Bs; etc...) > > O número de casos favoráveis é mais chatinho. > Eu sugiro olhar prum caso menor pra ver se aparece algum padrão. > Por exemplo, 8 questões, com 2 respostas A, 2 B, 2 C e 2 D. > Esse sai por inclusão-exclusão, mas com uma expressão meio feia e que não > me parece o melhor caminho pro caso do problema. > Talvez dê pra achar alguma recorrência ou função geradora. > > []s, > Claudio. > > > > On Tue, Nov 6, 2018 at 1:04 PM Paulo Rodrigues <teor...@gmail.com> wrote: > >> Pessoal, alguém pode dar uma mão na seguinte situação: >> >> Um gabarito é formado por uma sequência de 60 letras A, B, C e D sendo 15 >> de cada tipo. >> Qual a probabilidade de não existirem duas letras iguais vizinhas? >> >> Paulo Rodrigues >> >> >> -- >> Esta mensagem foi verificada pelo sistema de antivírus e >> acredita-se estar livre de perigo. > > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
