считать лень честно говоря, но просто визуально чё-то вроде 6*3^(n-1). Из соображений на шаге n=1 вроде как 6 возможных путей (хотя может обсчитался), на каждом дальнейшем шаге на каждый имеющийся маршрут пораждается три доп.варианта.

кое откуда и 2 пути так что там все сложнее

Наверно, так:

a 0 = 3
a n = 3 * a (n - 1) + 2 * b (n - 1)

b 0 = 1
b n = a (n - 1) + b (n - 1)

-- > take 10 $ map a [0 ..]
-- [3,11,41,153,571,2131,7953,29681,110771,413403]

потом решить рекуррентную систему.

S[1]=3*3+2 S[i+1]=S*3+2

Это 12 * 3 ^ (n - 1) - 1 - неправильно.

Задача на возведение матрицы 2x2 в n-ю степень. Бе.

состояние 3 числа левая часть робма верху[0] 1, посерёдке_слева[1] 1(точка S) внизу[2] 1. это нулевое состояние S0[1,1,1]

n итераций i от 1 до n

S=[S[0]+S[1],S[0]+S[1]+S[2],S[1]+S[2]]

ответ сделай ещё раз итерацию и выдай S[1]

можно конечно начать оптимизировать различать только середину и край:

S0 is [1,1] следующее S is [S[0]+S[1],2*S[0]+S[1]]

не интересно так решать = совсем не думаете а распознали и шлёп патерн.

Не распарсил.

S[0]=1;S[1]=3;S[n_]:=4 S[n-1]-S[n-2]

S[n_]:={{1, 3}}.MatrixPower[{{0,-1},{1,4}},n]

S[n_]:=Sum[2^k Binomial[2(n+1),2k],{k, 0, n}]

Примерно как фибоначчи (наверняка на википедии есть как коэф-ы подбирать, лень расписывать): легко получается рекурсивная ф-ия Sn = 4S(n-1) - S(n-2)

Интересная задача

Я джва года ждал такую задачу.

Комбинаторное решение в удаленных сообщениях

1