Questão Q14500

(Adaptada) A formiguinha da OBMEP caminha do ponto A até o ponto B ao longo dos lados dos 10 quadradinhos da figura abaixo.

Ela só pode andar para a direita, para cima ou para baixo, sem passar por onde já passou. Para representar um caminho, ela inventou o seguinte código: para cada quadradinho, da esquerda para a direita, se ela passar por baixo, escreve 0 e se passar por cima, escreve 1. Na figura a seguir observamos o caminho representado por 0010100011.

De quantas maneiras diferentes a formiguinha pode ir de A até B?