2013/7/12 Marcos Martinelli <[email protected]> > Seja {A_n} a quantidade de seqüências com 4 números escolhidos de 1 a n > tais que a diferença positiva seja maior ou igual a 2 (n>=4). > > Seja {B_n} a quantidade de seqüências com 3 números escolhidos de 1 a n > tais que a diferença positiva seja maior ou igual a 2 (n>=3). > > Seja {C_n} a quantidade de seqüências com 2 números escolhidos de 1 a n > tais que a diferença positiva seja maior ou igual a 2 (n>=2). > > Para sabermos quanto vale A_(n+1), devemos dividir nossa contagem em duas > partes: > > i) escolher 4 números dentre os que vão de 1 a n tais que a diferença > positiva seja maior ou igual a 2. Isto pode ser feito de A_n maneiras. > > ii) escolher o (n+1) como um número obrigatório a constar no nosso > conjunto de 4. Após isso, escolher 3 números entre os que vão de 1 a (n-1), > cuja diferença positiva seja maior ou igual a 2. Isto pode ser feito de > B_(n-1) maneiras. > > Podemos escrever: A_(n+1) = A_n + B_(n-1) (n>=4). > > Analogamente teremos: B_(n+1) = B_n + C_(n-1) (n>=3). > > Pensando de maneira similar, temos também: C_(n+1) = C_n + (n-1) (n>=2). > > Temos três séries telescópicas. Resolvendo e lembrando que a soma das > colunas do triângulo de Pascal é o número binomial localizado na diagonal à > direita do último elemento do somatório, obteremos: > > C_n = binomial (n-1,2) = (n-1).(n-2)/2! > > B_n = binomial (n-2,3) = (n-2)(n-3)(n-4)/3! > > A_n = binomial (n-3,4) = (n-3)(n-4)(n-5)(n-6)/4! > > Interessante a solução, ela me faz pensar o seguinte: há uma bijeção entre uma escolha (x1, x2, x3, x4) em números de 1 a n com a restrição, e uma escolha (x1, x2-1, x3-2, x4-3) para números de 1 a n-3 sem a restrição. Como este último pode ser escolhido de binomial(n-3, 4) formas, então o primeiro também poderia.
-- []'s Lucas -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
