Consider an n by n grid. How many ways can I place k 2×2 squares in the grid? The squares don't have to be aligned with each other, as long as they are aligned with the grid. Squares can't overlap and can't be split.
For example: For n=4, k=3, the configuration below is valid! (Letters represent squares, I can't post pictures yet, sorry)
A A – –
A A B B
C C B B
C C – –
A simpler version of this problem would be the number of ways to place k 1×2 rectangles on a 1 by n grid
Best Answer
Nice question. I followed the suggestion of Greg Martin and wrote a tiny program to get the first values of the sequence. Then plugging this sequence in the OEIS you get
T(n,k) = number of ways to place k nonattacking kings on an n X n board (https://oeis.org/A193580)
This is, I think, an equivalent way to describe your problem (you have to consider the "dual" grid and place the kings at intersections to obtain yours).
Bottom line is that this is a known problem but there doesn't seem to be a closed formula answer.