comecemos pela segunda questão. Ande de trás para frente: há 3 números que podem ocupar a última casa, n, n-1 ou n-2. O mesmo ocorre com a penúltima casa, pois embora um dos números mencionados acima tenha sido escolhido para ocupar a última casa, há uma nova possibilidade: n-3. Sucessivamente, vc perde uma opção, mas ganha outra. Isso só não ocorre com a casa 2 (só há duas opções, pois vc perde uma opção mas não ganha outra) e com a casa 1 (só resta uma opção). Pelo princípio multiplicativo, acabou.
Agora, a primeira questão. Como ela (e a anterior) são do livro do Morgado e colaboradores, presumo que vc o tenha e já saiba calcular o número de soluções de uma eq. cujas variáveis são inteiros não negativos, mesmo quando há restrições (por exemplo, quando uma variável precisa ser >=1). Vou admitir esse fato para apresentar duas soluções, uma baseada só nas técnicas daquele livro e outra baseada em funções geradoras (ver Introd. à Anál. Comb., de Santos, Mello & Murari, Ed. Unicamp). Talvez haja alguma solução + simples, as edições + recentes do Morgado et al trazem as soluções dos problemas (minha edição é bem antiga).
1a. solução: um pouco braçal, se o problema fosse "maior", complicaria; prefiro o segundo método, mas mostro esta solução para vc poder resolver o problema sem precisar de outro livro.
i) primeira possível configuração
_A_A_A_A_A_A_A_
Há 8 espaços em branco, que devem ser preenchidos pelos B's. Se x1 for a qtdade de B's no 1o. espaço em branco, por exemplo, então queremos saber qtas são as soluções de
x1+...+x8 = 7, sendo x1>=0, x8>=0, mas xi>=1, com i=2,...,7
que é o mesmo número de soluções de
y1+...+y8=1, com yi>=0 para todo i, que é C(8,7).
ii) segunda possível configuração
_AA_A_A_A_A_A_
Há 7 espaços em branco, que devem ser preenchidos pelos B's. Queremos saber qtas são as soluções de
x1+...+x7 = 7, sendo x1>=0, x7>=0, mas xi>=1, com i=2,...,6
que é o mesmo número de soluções de
y1+...+y7=2, com yi>=0 para todo i, que é C(8,6), mas há C(6,1) formas de posicionar o bloco AA.
iii) terceira possível configuração
_AA_A_A_AA_A_
Há 6 espaços em branco, que devem ser preenchidos pelos B's. Queremos saber qtas são as soluções de
x1+...+x6 = 7, sendo x1>=0, x6>=0, mas xi>=1, com i=2,...,5
que é o mesmo número de soluções de
y1+...+y6=3, com yi>=0 para todo i, que é C(8,5), mas há C(5,2) formas de posicionar os blocos AA.
iv) quarta e última possível configuração
_AA_AA_AA_A_
Há 5 espaços em branco, que devem ser preenchidos pelos B's. Queremos saber qtas são as soluções de
x1+...+x5 = 7, sendo x1>=0, x5>=0, mas xi>=1, com i=2,3,4
que é o mesmo número de soluções de
y1+...+y5=4, com yi>=0 para todo i, que é C(8,4), mas há C(4,3) formas de posicionar os blocos AA.
v) FECHANDO: C(7,0).C(8,7) + C(6,1).C(8,6) + C(5,2).C(8,5) + C(4,3).C(8,4) = 1016.
2a. solução: só o esboço, pq não dá explicar aqui, veja o livro citado
a configuração geral dos B's é
_B_B_B_B_B_B_B_
onde os espaços vazios devem ser preenchidos pelos A's. Se x1, por exemplo, for a qtdade de A's no 1o. espaço em branco,
x1+...+x8=7, com xi = 0, 1 ou 2, no máximo, para i=1,...,8.
Dada a função geratriz g(x) = (1+x+x^2)^8 = [(1-x^3)^8].[(1-x)^(-8)] , o coeficiente de x^7 na expansão de Taylor de g(x) é a solução procurada.
Espero ter sido claro (com exceção do último trecho...).
Abraços,
Leo.
On 4/25/06, Klaus Ferraz <[EMAIL PROTECTED]> wrote:
Quantas permutacoes de 7 letras A e 7 letras B, nas quais nao ha 3 letras A adjacentes, existem?gab: 1016Quantas sao as permutacoes simples dos numeros 1,2,....,n nas quais o elemento que ocupa a k-esima posicao é maior que k-3, para todo k?gab:2.3^(n-2)Quem puder me ajudar agradeco.
Yahoo! Messenger com voz - Instale agora e faça ligações de graça.