É fácil perceber que, no caso de um reticulado n x n, qualquer caminho terá comprimento igual a 2n, com n movimentos para a direita e n movimentos para baixo. Como representar um caminho? Eu escolhi fazê-lo por meio de um vetor de comprimento 2n, com n elementos "D" e n elementos "B". Assim, no caso exemplificado na descrição (n = 2), os caminhos possíveis seriam:
- DDBB
- DBDB
- DBBD
- BDDB
- BDBD
- BBDD
Este é um problema combinatório de se contar anagramas. Para n arbitrário, a resposta é (2n)! / (n! * n!) - prove isso -, que é equivalente a produto(n+1, n+2, ..., 2n) / n!, e eu resolvi em uma linha, em R, da seguinte maneira:
Note que é fácil a conta dar overflow para n grande, ou pelo menos perda de precisão, no caso do R. Existem meios de contornar isso, mas prefiro utilizá-los apenas quando necessário. Por ora, fiquemos com um pouco de simplicidade.
Nenhum comentário:
Postar um comentário