Оценка сверху количества перестановок

[AHOHbIMHO]

Jilian писал(а):

весьма благодарна за посты, но реккурентные соотношения я уже вывела, прогу сдала. Попросили просто числом оценить число таких укладок для N
K(i,0,0,0)=K(i-1,1,1,1).
K(i,1,0,0)=K(i-1,0,1,1)
K(i,0,1,0)=K(i-1,1,0,1)
K(i,0,0,1)=K(i-1,1,1,0)
K(i,1,0,1)=K(i-1,0,1,0)
K(i,1,1,0)=K(i-1,1,1,1) +K(i-1,1,0,1) +K(i-1,0,0,1)
K(i,0,1,1)=K(i-1,1,1,1) +K(i-1,1,0,0) +K(i-1,1,0,1)
K(i,1,1,1)=K(i-1,0,0,1)+K(i,1,0,0) +K(i-1,0,0,0)+K(i-1,0,0,0)+K(i-1,0,0,0)

Так Вам же maxal дал(а) конкретное значение числа укладок для четных N
$\frac{4\cdot 6^{N/2} + 1}{5}$. Чем оно Вас не устраивает?
Забавно, что заодно доказали, что ${4\cdot 6^n + 1}$ делится на 5 для любого натурального n. Может для математиков это очевидно, но для меня - нет.Хотя по индукции просто доказывается, почти что очевидно

[Руст]

Это очевидно 6=1(mod 5), 4=-1(mod 5).

[Jilian]

Большое всем спасибо за решение. Персонально mahal'у. задачу сдала!