Grade 12 2021 Problem 4

Dana je ploča dimenzija $n \times n$ i po jedna pločica dimenzija $1 \times 1$, $1 \times 2$, \ldots, $1 \times n$.

Na koliko načina je moguće odabrati $\frac{1}{2}n(n + 1)$ polja ploče tako da odabrani dio bude moguće prekriti horizontalno postavljenim pločicama, ali također i vertikalno postavljenim pločicama?