Шадар гурван квадрат

Тавил:
4xN тэгш өнцөгтийг зурагт дүрсэлсэн хэлбэртэй 3 квадратаар (эргүүлж болно) илүү гаргалгүй, давхардуулалгүй, дунд нь нүд үлдээхгүй дүүргэх нийт боломжийн тоог ол.
Эх өгүүлбэр: Шадар гурван квадрат
Бодолт:
N mod 3 != 0 үед хариу нь 0 байх нь тодорхой.
N = 3*K гэвэл.

11111...
11111...
11111...
11111...

хэлбэртэй 4x3K хэмжээтэй дүрсийг

10
11

дүрсээр хувааж болох хувилбарын тоог F(n) гэе.

00111...
00111...
01111...
01111...

хэлбэртэй 4x3K+6 хэмжээтэй дүрсийг

10
11

дүрсээр хувааж болох хувилбарын тоог G(n) гэе.

Тэгвэл:
F(k) = 4*F(k-1) + 4*G(k-2) + 2*F(k-2);
G(k) = 2*F(k-1) + 6*G(k-1);

F(0) = 1; F(1) = 4;
G(0) = 0; G(1) = 2;
гэсэн рекурсив функц олдоно. Эндээc F(k) нь хариу болно.