Европейская математическая олимпиада среди девочек (EGMO). 2015 год. Беларусь

Домино — это плитка размера $2 \times 1$ или $1 \times 2$. Определите количество различных способов расположить ровно $n^{2}$ плиток домино без наложений на шахматной доске размера $2 n \times 2 n$ так, что каждый квадрат размера $2 \times 2$ содержит по крайней мере две пустых клетки, которые находятся в одной и той же строке или одном и том же столбце.