Re: [obm-l] Contagem

["leonardo maia" <lpmaia@xxxxxxxxx>]

Caro Klaus,

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 <klausferraz@yahoo.com.br> wrote:

Quantas permutacoes de 7 letras A e 7 letras B, nas quais nao ha 3 letras A adjacentes, existem?

gab: 1016

Quantas 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.